CS 5114 Homework 2 (Spring 2009)

Describe your algorithms as clearly as possible. The style used in the book is fine, as long as your description is not ambiguous. Do not make any assumptions not stated in the problem. If you do make any assumptions, state them clearly, and explain why the assumption does not decrease the generality of your solution. Do not describe your algorithms only for a specific example you may have worked out. You must also provide a clear proof that your solution is correct (or a counter-example, where applicable). Analyse your algorithm and state the running time. You will only get partial credit if your analysis is not tight, i.e., if the bound you prove for your algorithm is not the best upper bound possible.

1. (20 points) Solve exercise 2 in Chapter 4 (page 189) of your textbook.
2. (35 points) Solve exercise 5 in Chapter 4 (pages 190-191) of your textbook. Just in case the problem statement is not completely clear, you can assume that the road is the x-axis, that each house lies directly on the road, and that the position of each house can be specified by its x-coordinate.
3. (45 points) Solve exercise 13 in Chapter 4 (pages 194-195) of your textbook. (Hint: Try to use one of the techniques we have seen for proving the correctness of greedy algorithms. Working "backwards" from what you need to prove might help you to discover the algorithm.)