CS180 Homework 5
All algorithms/proofs should be in bullet form: step by step or psuedo code.
1. Consider the divide and conquer algorithm for finding 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 different pieces are given as follows, then the
maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and
6)
length | 1 2 3 4 5 6 7 8
− − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − −
price | 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 first 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 first.
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
