All algorithms/proofs should be in bullet form: step by step or psuedo code.
1. Consider the divide and conquer algorithm for nding the closest pair of points. Analyze the time complexity of the algorithm . Include and discuss a detailed discussion of how to manage points in the x-dimension and how to manage (and search) points in the y-dimension. (You should do this without consulting the book or your notes)
2. Exercise 3 on page 314
3. Exercise 5 on page 316
4. Exercise 10 on Page 321
5. Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces. For example, if length of the rod is 8 and the values of di erent pieces are given as follows, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6)
length
j 1
2
3
4
5
6 7
8
price
j 1
5
8
9
10
17
17 20
6. Consider a row of n coins of values v1:::vn, where n is even. We play a game against an opponent by alternating turns (you can both see all coins at all times). In each turn, a player selects either the rst or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can win if we move rst.
Example 1: [5; 3; 7; 10] : The user collects maximum value of 15 (10 + 5)
- Sometimes the greedy strategy works.
Example 2: [8; 15; 3; 7] : The user collects maximum value of 22 (7 + 15)
{ In general the greedy strategy does not work.
1
