COMP3600/6466 — Algorithms – MidTerm Exercise
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
COMP3600/6466 — Algorithms – MidTerm Exercise
1. [20 pts]
(a) [5 pts] If f (n) ≤ g(n) for all positive values of n, then there are cases where f (n) = Θ(g(n)) and f (n) 丰 Θ(g(n)). Please provide an example for each case, i.e., one example for f (n) = Θ(g(n)) and one example f (n) 丰 Θ(g(n)).
(b) [5 pts] Is the following statement f(n) × g(n) = O(max(f(n), g(n))) always True? Please provide an explanation to support your answer.
(c) [5 pts] Is the following statement f(n) + g(n) = O(min(f(n), g(n)) True or False? Please provide an explanation to support your answer.
(d) [5 pts] Is the following statement f (n) = Θ(f (2n)) True or False? Please provide an explanation to support your answer.
2. [20 pts] Please rank the following function by increasing order of growth and explain your answer.
• f1 (n) = log(n!)
• f2 (n) = en
• f3 (n) = 8log(n)
• f4 (n) = 2log(n)
• f5 (n) = x
1 (3 + 2i)
3. [15 pts] Given the following recurrence, please answer the questions below
T(n) = { T(1)(n − c) + Θ(c) + log(n) n(n) 
1(1)
where c is a positive constant.
(a) [5 pt] Can Master Theorem be used to solve this recurrence?
(b) [10 pt] Please find a tight asymptotic bound (i.e., Θ) to the solution of the above recurrence.
4. [15 pts] Please solve the recurrence T(n) = 5T( 
) + n2 √n
Solution: We can use Master Theorem. Here, a = 5 , b = 2 , f(n) = n2 √n = n2.5 . This means nlogba = nlog2 5 ≈ n2.32 , which means f(n) = Ωnlogba , and hence case-3 applied. Therefore, T(n) = Θ(n2 √
n).
5. [10 pts] As a programmer in a start-up company, you have been tasked to write a general sorting program (i.e., one that sort any type of data given a comparison function) that runs in Ø(n) time, where n is the number of data to be sorted. Is this task feasible? Please explain.
6. [20 pts] Mr OCD has a small library of k books in his home. Each of his books has been labelled with a unique number indicating the book ID, and he would like to sort the books in ascending order based on their IDs. The difficulty is that since the book collection grew over time, different books may have IDs with different number of digits. However, since Mr OCD keeps a record of all of his books, along with their IDs, he knows that the total numbers of digits of the book IDs, across all the k books, is n. He then told you he can sort his books in worst case O(n) time. Is a sorting mechanism with such a time complexity possible? If it is possible, please provide the algorithm and show that the time complexity of the algorithm is indeed O(n). Otherwise, please explain why your house-mate argument is impossible.
2022-09-20