CSOR W4246–Summer, 2021 Eleni Drinea
Homework Instructions.
Homework 1 (120 points)
Out: Friday, May 7, 2021
Due: 11:59pm, Friday, May 14, 2021
1. For all algorithms that you are asked to “give” or “design”, you should
• Describe your algorithm clearly in English.
• Give pseudocode.
• Argue correctness, even if you don’t give an entirely formal proof. • Give the best upper bound that you can for the running time.
You are also encouraged to analyze the space required by your algorithm but we will not remove marks if you don’t, unless the problem explicitly asks you to analyze space complexity.
2. You should submit your assignment as a pdf file on Gradescope. Other file formats will not be graded, and will automatically receive a score of 0.
3. I recommend you type your solutions using LaTeX. For every assignment, you will earn 5 extra credit points if you type your solutions using LaTeX or other software that prints equations and algorithms neatly. If you do not type your solutions, make sure that your hand-writing is very clear and that your scan is high quality.
4. You should write up the solutions entirely on your own. Collaboration is limited to discussion of ideas only. You should adhere to the department’s academic honesty policy (see the course syllabus). Similarity between your solutions and solutions of your classmates or solutions posted online will result in receiving a 0 in this assignment, and possibly further disciplinary actions. There will be no exception to this policy and it may be applied retro- actively if we have reasons to re-evaluate this homework.
Homework Problems
1. (20 points) Consider the following recursive algorithm. On input a list of distinct numbers, the algorithm runs in three phases. In the first phase, the first d2/3e elements of the list are sorted recursively; when the list has size 2, return the list if ordered, otherwise swap. In the second phase, the last d2/3e elements are sorted recursively. Finally, in the third phase, the first d2/3e elements are sorted recursively again.
Give pseudocode for this algorithm, prove its correctness and derive a recurrence for its running time. Use the recurrence to bound its asymptotic running time. Would you use this algorithm in your next application to sort?
2. (30 points) In this problem, we will analyze an algorithm that finds an item close enough to the median item of a set S = {a1, . . . , an} of n distinct numbers. Specifically, the algorithm finds an item ai such that at least n/4 items are smaller than ai and at least n/4 items are greater than ai.
Algorithm 1
Randomized Approximate Median(S)
1: Select an item ai 2 S uniformly at random
2: rank=1
3: forj=1tondo
4: if aj
(a) (6 points) Show that Fn 2n/2, n 6.
(b) Assume that the cost of adding, subtracting, or multiplying two integers is O(1), inde- pendent of the size of the integers.
i) (6 points) Give an algorithm that computes Fn based on the recursive definition above. Develop a recurrence for the running time of your algorithm and give an asymptotic lower bound for it.
ii) (8 points) Give a non-recursive algorithm that asymptotically performs fewer addi- tions than the recursive algorithm. Discuss the running time of the new algorithm.
iii) (20 points) Given an algorithm to compute Fn in O(log n) time using only integer
additions and multiplications. (Hint: Observe that
Can you build on this to compute Fn?)
RECOMMENDED EXERCISES (do NOT submit, they will not be graded)
1. Give tight asymptotic bounds for the following recurrences.
• T(n)=4T(n/2)+n3 1. • T(n)=8T(n/2)+n2.
• T(n) = 6T(n/3) + n.
• T(n)=T(pn)+1.
2. Showthat,if isapositiverealnumber,thenf(n)=1+ + 2+…+ n is
(a) ⇥(1)if <1. (b) ⇥(n)if =1.
(c) ⇥( n) if > 1.
Therefore, in big-⇥ notation, the sum of a geometric series is simply the first term if the series is strictly decreasing, the last term if the series is strictly increasing, or the number of terms if the series is unchanging.
“F2#=”1 1#·”F1#. F1 10F0