Due Friday, June 2 (11:59 p.m.)

Instructions

• Answer each question on a separate page.

• Submit your homework as a single pdf file to Gradescope. It can be either a scanned copy of your written solutions or photos joined into a pdf; your solution should be readable. You are also encouraged to typeset the solutions in TEX or MS Word. Gradescope will ask you to mark where each answer is - please make sure to do this - points will be deducted otherwise.

•  For each question where you are required to design an algorithm, you need to clearly explain the algorithm and prove the running time complexity as asked in the question.

• You are encouraged to discuss with your peers/consult supplementary material if neces- sary, but the final written solutions must be your own.

–  For each solution that you discussed or looked at extra materials for hints, you are required to mention it in your solution. This will not incur any penalty, but if noticed otherwise by the graders it may bright into question your academic integrity and there will be more serious repercussions. Writing down solutions or answers from some source without citing the source or without understanding how what you have written is correct is cheating and will be treated as such.

Question 0: List all your collaborators and sources: (–∞ points if left blank)

You must enter the names of your collaborators or other sources as a response to Question 0. Do NOT leave this blank; if you worked on the homework entirely on your own, please write “None”here. Even though collaborations in groups of up to 3 people are encouraged, you are  required to write your own solution.

Question 1: (1+5+2+2 =10 points points)

Prove the following by induction on n: For a fixed real number r 丰 1, for all integers n ≥ 0,

0      1      2               n rn+1 – 1

r – 1   .

1. Check the base case (n = 0).

2.  Prove the inductive step.

3.  Use (1) to evaluate and simplify the sum  . What is the limit of the result as n → ∞ ? log2 (n)

4.  Use (1) to evaluate and simplify the sum x 2k . Also, express the result as Θ(f(n)) for a "simple" function f(n) (i.e., f(n) has only one term and no constant factors).

Question 2: (1+2+2+3+2=10 points)

f = O (g) is defined for functions f and g (both from N to N)1 to mean that there exist positive constants n0 and C such that:

f(n) ≤ C · g(n)  for all n ≥ n0 .

For each of the following statements either prove the statement if it is true or otherwise provide a counter-example and justify why your counterexample is indeed a counter-example:

1.  If f = O (g) then g = O (f).

2.  If f = O (g) and g = O (h) then f = O (h).

3.  If f = O (g) and g = O (f) and V n, f(n) > g(n) then f – g = O(1).

4.  If f = O (g) and g = O (f) then  = O(1).

5.  If f = O (g) and h = O (g) then f = O (h).

Question 3: (5 points)

Rank the following functions by order of growth (You need not prove the correctness of your

ranking). That is, find an order fa , fb, fc . . . fe so that fa = O (fb), fb = O (fc), and so on:

a) 2log3 n

b) √n log2 n

c) 2n

d) n! where n! = 1 · 2 · 3 · · · (n – 1) · n so for example 4! = 1 · 2 · 3 · 4 = 24

e) n2

Question 4: (5 points)

Let an denote the n-th number in a sequence defined as follows. Define a1 = 1, a2 = 1, a3 = 1, and an = an– 1 + an–2 + an–3 for n ≥ 4. Prove (by induction on n) that for each n ∈ N with n > 1, an ≤ 2n–2 .

Question 5: (5+3+2=10 points)

Let A[1, 2, ..., n] be an array of n elements.

1. Give an algorithm that finds the index of the first element in the array that equals some previous element in the array. If no such element exists, return an index of 0.

2.  Prove the correctness of your algorithm.

3. Give the run time bounds for your algorithm.