1. In your pre-lecture Exercise for Lecture 3, you saw two different proofs that the solution to the recurrence relation T(n) = 2 T(n/2) + n with T(1) = 1, was exactly T(n) = n(1 + log(n)), when n was a power of two.
   • What is the exact solution to T(n) = 2 T(n/2) + n with T(1) = 2, when n is a power of 2?
   • What is the exact solution to T(n) = 2 T(n/2) + 2n with T(1) = 1, when n is a power of 2?

[We are expecting: Your answer, with a convincing argument (it does not need to be a formal proof). Notice that we want the exact answer, so dont give a O() statement. ]

2. Consider the recurrence relation T(n) = T(n 1) + n with T(1) = 1. Your friend claims that T(n) = O(n), and offers the following justification:

Lets use the Master Theorem with, and d = 1. This applies since

Then we have a < b^d, so the Master Theorem says that T(n) = O(n^d) = O(n).

Whats wrong with your friends argument, and what is the correct answer?

[HINT: It is totally fine to apply the Master Theorem when b is a fraction; thats not the problem.]

[We are expecting: A clear identification of the faulty logic above; your solution to this recurrence (you may use asymptotic notation^[1]) and a short but convincing justification.]

3. (3 pt.) Use any of the methods weve seen in class so far to solve the following recurrence relations.^[2]
   • T(n) = T(n/3) + n², for n > 3, and T(n) = 1 for n 3.
   • T(n) = 2T(n/2) + 10 n + 4, for n > 2, and T(n) = 1 for n 2.
   • T(n) = T(n/2) + T(n/4) + n for n > 4, and T(n) = 1 for n 4.

[We are expecting: The answer (you may use asymptotic notation) and a justification. You do not need to give a formal proof, but your justification should be convincing to the grader.]

Problems

You may talk with your fellow CS161-ers about the problems. However:

• Try the problems on your own before
• Write up your answers yourself, in your own words. You should never share your typed-up solutions with your collaborators.
• If you collaborated, list the names of the students you collaborated with at the beginning of each problem.

1. Consider the function T(n) defined recursively by

Fill in the blank: T(n) = ( ). [HINT: It may be helpful that

[We are expecting: Your answer and a convincing justification. You do not need to write a formal proof; and you may assume that n is a power of 2 if it helps.]

2. Consider the function T(n) defined by

Using an argument by induction (not using the Master Method), prove that T(n) = (nlog(n)).

[We are expecting: A formal proof by induction. Make sure you explicitly state your inductive hypothesis, base case, inductive step, and conclusion. ]

3. (8 pt.) Plucky the Pedantic Penguin sometimes does consulting work on the side.^[3] There are n companies who are interested in Pluckys work. Plucky can work for at most one company during a given day. Each company has a range of times when they are interested in Pluckys work, and an amount they are willing to pay: between a_i and b_i (including a_i and not including b_i), Company i is willing to pay Plucky f_i Here, a_i,b_i,f_i are all positive integers and a_i b_i. Each day, Plucky chooses to work for the highest bidder. If there is no company interested in Pluckys work on a day, Plucky gets zero fish that day.

Plucky gets the bids (a_i,b_i,f_i) as inputs, and wants to make a plot of how many fish he will receive each day. To understand the format he wants the output in, see the example below.

In this problem youll design an algorithm for Plucky. Your algorithm should take as input a list of n bids (a_i,b_i,f_i), one for each company i {0,,n 1}, and return a list fishPlot of (t_i,f_i) pairs as described in the example above.

• Describe a simple O(n²)-time algorithm for Plucky.

[We are expecting: Pseudocode, and a short English description explaining the main idea of the algorithm. No justification of the correctness or running time is required.]

• Design a divide-and-conquer algorithm that takes time O(nlog(n)).

[We are expecting: Pseudocode, and a short English description explaining the main idea of the algorithm. We are also expecting an informal justification of correctness and of the running time.]

[1] Unless specified otherwise, in every problem set, when we ask for an answer in asymptotic notation, we are asking either for a () result, or else the tightest O() result you can come up with.

[2] You may either treat fractions like n/2 as bn/2c, dn/2e, or just as real numbers (not integers), whichever you prefer.

[3] He points out indexing errors for bay area start-ups.