IMPORTANT NOTES (PLEASE READ BEFORE WORKING ON THE SOLUTION):
- Please read the entire of this question sheet before starting to work on the solution.
- Your assignment should consist of a single .pdf, named A2-[studentID].pdf and a single .cpp/.java ﬁle, named
A2-[studentID].cpp or A2-[studentID].java. You should zip these two ﬁles together into a single ﬁle, named the
.zip ﬁle A2-[studentID].zip and submit via Wattle before the due date.
- We provide 13 hours grace period. This means, there will be no penalty if you submit before the grace period
ends. However, we will NOT accept assignment submission beyond this time (i.e., late penalty after the grace
period ends is 100%).
– You can update your assignment until the grace period ends.
- Assignment marking:
- – The total mark you can get in this assignment is 100 points.
– This assignment will contribute 20% to your overall mark.
– In each question, you need to provide a convincing argument (including mathematical derivation) that
supports your answer. The argument is worth 80% of the marks, while the solution alone is 20%.
- Discussion with your colleagues are allowed and encouraged. However, you need to work on the assignment
on your own AND write the names you discussed this assignment with.
In all the questions below, you can assume that all n are positive integers.
[30 pts] Part A
1. [10 pt] Given the following recurrence, please answer the questions below
where c is a positive constant.
(a) [2.5 pt] Can Master Theorem be used to solve this recurrence?
(b) [7.5 pt] Please ﬁnd a tight asymptotic bound (i.e., ) to the solution of the above recurrence.