CSOR W4246 – Fall, 2019
HW1 – Theoretical part (110 points)
Out: Friday, September 6, 2019
Due: 11:59pm, Friday, September 20, 2019
You should always describe your algorithm clearly in English. You should always give pseudocode for all algorithms that you design.
For all deterministic algorithms you design, you must prove correctness and give the best upper bound that you can for the running time. You are also encouraged to analyze the space required by your algorithm.
For all randomized algorithms that you design, you must figure out whether they always terminate with the correct answer (as Randomized-Quicksort does) or not. In the latter case, you must analyze their success probability, that is, the probability they terminate with the correct answer. The problem statements will guide you to do so. You should always give the best upper bound that you can for the running time of your algorithms.
You must submit your assignment as a pdf file. Other file formats will not be graded, and will automatically receive a score of 0.
I recommend you type your solutions using LaTeX. For every theoretical assignment, you will earn 5 extra credit points if you type your solutions. If you do not type your solutions, make sure that your hand-writing is very neat, your scan is high-quality and your name and UNI are clearly written on your homework.
You should write up the solutions entirely on your own. Collaboration is limited to discussion of ideas only (see also 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.
1. (20 points) Suppose we want to evaluate the polynomial p(x) = a0 + a1x + a2x2 + . . . + anxn at point x.
(a) Show that the following simple routine, known as Horner’s rule, solves this problem and stores the solution in z. How many additions and multiplications does this routine use, as a function of n?
z = an
for i=n−1downto0do
z = zx + ai end for
(b) Can you find a polynomial for which an alternative algorithm runs substantially faster?
2. (15points) Consider the following recursive algorithm. On input a list of distinct numbers, the algo- rithm runs in three phases. In the first phase, the first ⌈2/3⌉ 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 ⌈2/3⌉ elements are sorted recursively. Finally, in the third phase, the first ⌈2/3⌉ 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?
3. (25 points) In the table below, indicate the relationship between functions f and g for each pair (f, g) by writing “yes” or “no” in each box. For example, if f = O(g) then write “yes” in the first box. Here logb x = (log2 x)b.
f
g
O
o
Ω
ω
Θ
n log2 n
6n2 log n
√
log n
(log log n)3
4logn
nlog4n
n3/5
√
nlogn
√
5 n+logn
√
2n
5n n8
n5 4n
√n2n
2n/2+log n
nlog2n
n2 log n
n!
2n
log n!
log nn
4. (20 points) In this problem, you 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 ∈ S uniformly at random
2: rank=1
3: forj=1tondo
4: if aj
if |S−|=k−1 then return ai
// ai is the k-th smallest item
else if |S−| ≥ k then
k-th order statistic (S−,k)
// the k-th smallest item lies in S− 10: else // the k-th smallest item lies in S+
more than n3j+1 items. 4
4
Upper bound the expected time of k-th order statistic on a subproblem of type j, excluding the time spent on recursive calls. Equivalently, upper bound the expected time until an item ai is selected such that 1/4 of the input can be thrown out (thus the input shrinks by a factor of 3/4). Next obtain an upper bound to the expected running time of the entire algorithm by summing up the expected time spent on every subproblem.
Recommended OPTIONAL exercises: do not return, they will NOT be graded!
1. Use the Master theorem to give tight asymptotic bounds for the following recurrences.
• T(n) = 4T(n/2) + n2. • T(n) = 8T(n/2) + n3. • T(n) = 11T(n/4) + n2. • T(n) = 7T(n/3) + n.