Homework 2 – Divide and Conquer

How to submit your solutions Each problem must be typed up separately (in at least an 11-point
font) and submitted in the appropriate assignment box on the Canvas website as a PDF file.
This means that you will submit 5
separate files on Canvas, one for each
problem!
You are strongly encouraged, but not required, to format your problem solutions in LATEX. Template HW files and other LATEXresources are posted on the course webpage. LATEXis a free, open-source
scientific document preparation system. Most technical publications in CS are prepared using this tool.
You might want to acquire a LATEX manual or find a good online source for LATEX documentation.

Solution guidelines For problems that require you to provide an algorithm, you must give the
following:
1. a precise description of the algorithm in English and, if helpful, pseudocode,
2. a proof of correctness,
3. an analysis of running time and space.
You may use algorithms from class as subroutines. You may also use any facts that we proved in class.
You should be as clear and concise as possible in your write-up of solutions. Understandability of
your answer is as desirable as correctness, because communication of technical material is an important
skill. A simple, direct analysis is worth more points than a convoluted one, both because it is simpler
and less prone to error and because it is easier to read and understand. Points might be subtracted
for illegible handwriting and for solutions that are too long. Incorrect solutions will get from 0 to 30%
of the grade, depending on how far they are from a working solution. Correct solutions with possibly
minor flaws will get 70 to 100%, depending on the flaws and clarity of the write up.
Assigned Problems
Exercises (Do not hand in) Chapter 4: 3,4 and 6, Chapter 5:1-3.
Following are the problems to be handed in, 25 points each. Maximum score for this
homework is 100 points. We will take your best four attempted problems.
1. (Divide and Conquer, 2-page limit – your solutions should fit on two sides of 1 page).
A Walsh-Hadamard matrix Hn is an 2n ×2
n matrix with each entry being −1 or +1 and n ∈ Z
+,
such that the (i, j)-th entry of Hn[i, j] = √
1
2n
(−1)i◦j
. Assume that the rows and columns of Hn
are counted from zero, i.e., the left-topmost entry of Hn is Hn[0, 0]. Here i ◦ j is the bitwise dotproduct of the binary representation of i and j represented with n bits. For example, if i = 7 and
j = 5, then i ◦ j = (1, 1, 1) · (1, 0, 1) = 2. Following are couple of examples of Walsh-Hadamard
matrices H2 and H3.
H2 =
1
√
2
2




1 1 1 1
1 −1 1 −1
1 1 −1 −1
1 −1 −1 1




H3 =
1
√
2
3












1 1 1 1 1 1 1 1
1 −1 1 −1 1 −1 1 −1
1 1 −1 −1 1 1 −1 −1
1 −1 −1 1 1 −1 −1 1
1 1 1 1 −1 −1 −1 −1
1 −1 1 −1 −1 1 −1 1
1 1 −1 −1 −1 −1 1 1
1 −1 −1 1 −1 1 1 −1












• Starting from the fact that Hn[i, j] = √
1
2n
(−1)i◦j
, show that
Hn =
1
√
2
?
Hn−1 Hn−1
Hn−1 −Hn−1
?
• Show that the Euclidean norm of every column and every row is 1. (You are allowed to
search Wikipedia for the definition of Euclidean norm.)
2
• Using the above properties, write and prove an induction claim that shows that the columns
of Hn form an orthonormal basis, i.e., the dot-product of any two columns of Hn equals to
zero, and every column of Hn has Euclidean norm of one. Hint: You will need one of the
properties of orthonormal matrices to show this.
• Consider a vector v ∈ R
2
n
, i.e., a vector with 2n
entries with real numbers. Design an
algorithm to compute Hn·v in time O(n log n). Prove the runtime bound for your algorithm.
2. (Divide and Conquer, 2-page limit – your solutions should fit on two sides of 1 page).
You and your sister are travelling on a bus when you recall the ”Hot and cold” game you used
to play as kids. To kill time, you decide to play a version of it with numbers. One of you
thinks of a number between 1 and n, and the other tries to guess the number. If you are the
one guessing, every time you make a guess your sister tells you if you are ”warmer”, which is
closer to the number in her head, or ”colder”, which is further away from the number in her
head. Using this information you have to come up with an algorithm which helps you guess the
number quickly. You can use a command called Guess(x), where x is your guess, which returns
”warmer”, ”colder” or ”you guessed it!”. You are required to give an English explanation for
your algorithm. Also, prove the correctness of your algorithm and give an analysis of the space
and time complexity. An ideal solution will propose an algorithm that takes log2
(n) + O(1)
guesses in the worst case scenario. Recalling how binary search works might be helpful.
3. (Greedy Algorithm, 2-page limit – your solutions should fit on two sides of 1 page). The Menlo
Park Surgical Hospital admitted a patient, Mr. Banks, last night who was in a car accident and
is still in critical condition and needs monitoring at all time. At any given time only one nurse
needs to be on call for the patient though. For this we have availability slots of all the nurses,
which is a time from which they are available, ai
, to the time they have other engagements, bi
.
You need to devise an algorithm that makes sure you can cover Mr. Banks’ entire stay while
having minimum number of nurses be on call for him. A nurse leaving at the same time as
another arrives is acceptable. Following is an example of how the availability slots for the nurses
will look like. The darker bars correspond to a set of 5 nurses who can cover the entire duration.
(Notice, though, that 4 nurses would have sufficed.)
Your efficient greedy algorithm should take input a list of pairs of times (ai
, bi) for i = 1 to n
(a) Consider the greedy algorithm that selects nurses by repeatedly choosing the nurse who
will be there for the longest time among the periods not covered by previously selected
nurses. Give an example showing that this algorithm does not always find the smallest set
of nurses.
(b) Present an algorithms that outputs a smallest subset of nurses that can cover the entire
duration of Mr. Banks’ stay at the hospital or say that no such subset exists.
(c) Prove that your algorithm is correct.
(d) State its running time.
3
4. (Greedy Algorithm, 2-page limit – your solutions should fit on two sides of 1 page). Picture, if
you will, a long river with some towns scattered sparely along it. You are in charge of building a
series of small hydro-electric power plants for these towns to give them some renewable electricity;
however, the power plants can’t power a town further than 20 miles away, due to their particular
design - they can, however, give power to as many towns as they can reach. You want to build
them along the river such that every town is within 20 miles of at least one of the plants.
Give an efficient algorithm that achieves this goal using the minimum number of power plants.
Prove using greedy stays ahead strategy.
5. [
∗
] (Optional, no collaboration, 2-page limit – your solutions should fit on two sides of 1 page).
You and your roommate are in a war over the thermostat - they like it cold, and you like it
warmer. The temperatures range from 1 to n degrees. Your roommate is willing to leave the
thermostat at some (unknown to you) temperature t or any lower temperature. You sit down
with your roommate and agree to negotiate in the following way: In each round, you can name
any temperture s between 1 and n. If s t, they will say ”too warm”. Otherwise, they’ll agree
to s. Your goal is to ensure that the apartment is at the maximum acceptable temperture t.
One way to ensure that you will have the temperture at s is to name all integers, starting from
n and going down by 1 in each round, until they agree to the temperture t. But, if you follow
this strategy, you might have to go through n rounds (irratating everyone involved).
If you are allowed to change your mind (that is, ask for a higher temperature) after your roommate accepted your offer, you might want to try binary search as your strategy. However, it
would also be annoying to change your mind so many times.
(a) Suppose you are allowed to change your mind exactly once. Describe a strategy for ensuring
a fair temperture, t, that uses o(n) rounds of negotiation (as few as you can).
(b) Now suppose you are allowed to change your mind k times, where k 1. Describe a strategy
for ensuring a fair temperture, s, with as few negations as you can. Let fk(n) denote the
number of rounds you use, as a function of n. (The answer from part (a) is your f1(n).)
For each k, you should be able to get an asymptotically better solution than for k −1: that
is, make sure that fk(n) = o(fk−1(n)).