Assignment 2 on Units 3 and 4 of Course Materials

Instructions to students:

1. The assessment covers the topics in Units 3 and 4 of course materials.
2. The total marks for Assignment 2 is 100 and contributes 25% to the total grade.
3. Submit your assignment to the Online Assignment Submission System (OAS). Submission of assignments in hard copy will not be accepted. Marks will be awarded for quality content and presentation.
4. Times New Roman 12pt font should be used for all writing. Answer all questions in English.
5. Students are required to attach the Assignment declaration (T-DF) form as the front cover of their assignments. No duplication of work will be tolerated. Any plagiarism or collusion may result in disciplinary action to all parties involved.
6. Please check the WawasanLearn for submission deadline.

Question 1 (20 marks)

Suppose you just recently joined WOW enterprise. The company has over 1000 staffs from across the globe. You are attending the company’s annual meeting for the first time. The Chief Executive Officer (CEO)’s son, James is also attending the meeting this time. James does not know anyone in the meeting, but everyone attending the meeting knows James. You want to get to know James. You are allowed to ask only one question DoYouKnow(X, Y), i.e. you can ask only one question to X that do you know Y. In this case to Y would be James. X will answer the question yes or no.

Explain clearly how you can find James using only DoYouKnow(X, Y). Then, justify the complexity of your solution using the Big-Oh notation.

Guidelines: You may include illustrative diagram(s) with description to explain your solution, if necessary. Provide the necessary examples. You will be judged based on:

• Clarity of the solution (e.g. reproducible in programming form etc. by the reader)
• Efficiency of the solution (refer to Unit 4 on Algorithm Complexity). Hints: Can you use a stack?

Question 2 (40 marks)

Suppose Touch ’n Go eWallet is running a program to reward its customers for using the apps. The top log n customers, based on the amount of money spent for each month, where n is the total number of customers for the month will be rewarded RM99 cashback. Suggest TWO (2) algorithms that can retrieve the top log n customers in:

(a) O(n log n) time
(b) O(n) time

Guidelines: Your algorithm can be given in the form of pseudo code or Java program. You will be judged based on:

•  Clarity of the solution (e.g. reproducible in programming form etc. by the reader)
• The solution must reflect the required algorithm complexity. Justify your answer.

Question 3 (40 marks)

Two ordered trees T1 and T2 are called isomorphic if one of the following conditions holds true:

• Both T1 and T2 are empty.
• Both T1 and T2 comprises a single node.
• Both T1 and T2 have the same number of k 1 of subtrees, and the i-th subtree of T1 is isomorphic to the i-th subtree Ti for i = 1, 2, ..., k.

Design an algorithm to test if two given ordered trees are isomorphic. What is the running time of your algorithm?

Guidelines: Your algorithm can be given in the form of pseudo code or Java program. Provide examples to demonstrate the correctness of your algorithm.