Solved-Homework 2 – Solution

Description

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 t on two sides of 1 page).

A Walsh-Hadamard matrix Hn is an 2	n	2		n				+	,
				1		matrix with each entry being 1 or +1 and n 2 Z
such that the (i; j)-th entry of Hn[i; j] =			p				(	1)i j . Assume that the rows and columns of Hn
					2n

are counted from zero, i.e., the left-topmost entry of H_n is H_n[0; 0]. Here i j is the bitwise dot-product 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.																			21	11						13
																					1	1	1	1	1
																			1		1	1	1	1	1	1
H2 =	1			1	1	1	1	3	H3 =							1			61	11	1	1	1	1	1	1	7
				2	1	1	1												6		1	1	1	1	1	1	7
				1															1
				1	1	1	1												61	1	1	1	1	1	1	1	7
	p2		2											p2				3
				6				7											6								7
				61	1	1	1	7											61	1	1	1	1	1	1	1	7
				4				5											6								7
																			61	1	1	1	1	1	1	1	7
																			6								7
																			61	1	1	1	1	1	1	1	7
											1								4								5
Starting from the fact that Hn[i; j] =										p						(			1)i j , show that
											2n
									Hn = p			2				Hn 1				Hn 1
									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 de nition of Euclidean norm.)

Using the above properties, write and prove an induction claim that shows that the columns of H_n form an orthonormal basis, i.e., the dot-product of any two columns of H_n equals to zero, and every column of H_n has Euclidean norm of one. Hint: You will need one of the properties of orthonormal matrices to show this.

Consider a vector v 2 R²ⁿ , i.e., a vector with 2ⁿ entries with real numbers. Design an algorithm to compute H_n v in time O(n log n). Prove the runtime bound for your algorithm.

2. (Divide and Conquer, 2-page limit { your solutions should t 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 log₂(n) + O(1) guesses in the worst case scenario. Recalling how binary search works might be helpful.

2. (Greedy Algorithm, 2-page limit { your solutions should t 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, a_i, to the time they have other engagements, b_i. 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 su ced.)

Your e cient greedy algorithm should take input a list of pairs of times (a_i; b_i) for i = 1 to n

1. 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 nd the smallest set of nurses.

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

3. Prove that your algorithm is correct.

4. State its running time.

4. (Greedy Algorithm, 2-page limit { your solutions should t 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 e cient algorithm that achieves this goal using the minimum number of power plants. Prove using greedy stays ahead strategy.

4. [ ] (Optional, no collaboration, 2-page limit { your solutions should t 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 room-mate accepted your o er, you might want to try binary search as your strategy. However, it would also be annoying to change your mind so many times.

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

4. 2. 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 f_k(n) denote the number of rounds you use, as a function of n. (The answer from part (a) is your f₁(n).) For each k, you should be able to get an asymptotically better solution than for k 1: that is, make sure that f_k(n) = o(f_{k 1}(n)).

4