CS161-Homework 2 Solved

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.

(a)    What is the exact solution to T(n) = 2 · T(n/2) + n with T(1) = 2, when n is a power of 2?

(b)   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 don’t 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:

Let’s use the Master Theorem with , and d = 1. This applies since

 .

Then we have a < bd, so the Master Theorem says that T(n) = O(nd) = O(n).

What’s wrong with your friend’s argument, and what is the correct answer?

[HINT: It is totally fine to apply the Master Theorem when b is a fraction; that’s 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 we’ve seen in class so far to solve the following recurrence relations.[2]

(a)    T(n) = T(n/3) + n2, for n 3, and T(n) = 1 for n ≤ 3.

(b)   T(n) = 2T(n/2) + 10 · n + 4, for n 2, and T(n) = 1 for n ≤ 2.

(c)    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.]

 

 

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.   Plucky the Pedantic Penguin sometimes does consulting work on the side.[3] There are n companies who are interested in Plucky’s 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 Plucky’s work, and an amount they are willing to pay: between ai and bi (including ai and not including bi), Company i is willing to pay Plucky fi fish. Here, ai,bi,fi are all positive integers and ai ≤ bi. Each day, Plucky chooses to work for the highest bidder. If there is no company interested in Plucky’s work on a day, Plucky gets zero fish that day.

Plucky gets the bids (ai,bi,fi) 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 you’ll design an algorithm for Plucky. Your algorithm should take as input a list of n bids (ai,bi,fi), one for each company i ∈ {0,...,n − 1}, and return a list fishPlot of (ti,fi) pairs as described in the example above.

(a)    Describe a simple O(n2)-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.]

(b)   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.