## Description

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

4