Reference no: EM132291038
Design and Analysis of Algorithms Homework -
Question 1 - In the following, let f and g be positive increasing functions. Answer each question and briefly justify your answers. You get no points if you do not give a justification.
(a) Given that f(n) = O(g(n)), is it possible that f(n) = Θ(g(n))? Is it always true that f(n) = Θ(g(n))?
(b) Given that f(n) = ω(g(n)), is it possible that f(n) = Ω(g(n))? Is it always true that f(n) = Ω(g(n))?
(c) Given that f(n) = O(g(n)), is it possible that f (n) = o(g(n))? Is it always true that f (n) = o(g(n))?
(d) Is it possible that f (n) = ω(g(n)) and also f(n) = O(g(n))?
(e) Is it possible that f (n) + g(n) = O(min(f(n), g(n)))? Is it always true that f (n) + g(n) = O(min(f(n), g(n)))?
Question 2 - Give two asymptotically different functions, each of which belongs to both ω(n) and o(n2). Briefly justify your answers.
Question 3 - Problem 3-2 of the Textbook (p.61), (c) - (f). Note that "A is O of B" means A = O(B), and similarly for other notations (o, Ω, ω, Θ). In your write up, copy and fill up the table with "Yes" or "No" in each table entry; after the table, briefly justify your answer for each sub-question. You get no points if you do not give a justification.
Question 4 - Let S1(n) = k=1∑n k, S2(n) = k=1∑n k2 and S3(n) = k=1∑n k3. In class, we already showed how to calculate S1(n) and S2(n). Your task here is to apply similar methods for S3(n).
(a) Without calculating the closed form, use rough estimations to derive a lower bound and an upper bound for S3(n), so that you can use them to express S3(n) in the Θ() notation. Give this Θ() notation in the simplest form (e.g., Θ(n) is in the simplest form but Θ(2n) is not).
(b) Use the perturbation method (as discussed in class) to derive the closed form for S3(n).
(Background Information: You would need the formula of S1(n) and S2(n), which we already know: S1(n) = n(n + 1)/2 and S2(n) = n(n + 1)(2n + 1)/6.)
Question 5 - Given a sequence of it unordered real numbers, design and analyze an algorithm that finds both the smallest and the second smallest numbers among them using at most 3⌊n/2⌋ comparisons. Your algorithm should describe what to do when n is even and when n is odd. You need to show that your algorithm gives the correct answers, and that it uses at most 3⌊n/2⌋ comparisons.