CSE 521 Assignment #1
Winter 2010

Due: Thursday, January 21, 2010 in class.

Reminder: If you haven't done so already, subscribe to class email group ASAP by following the link from the course webpage

Reading Assignment: Kleinberg and Tardos Chapters 4 and 5.

Instructions: You are allowed to collaborate with fellow students taking the class in solving problem sets. However, you must write up your problem sets individually. If you do collaborate in any way, you must acknowledge for each problem the people you worked with on that problem.

The problems have been chosen for their pedagogical value and hence might be similar or identical to those given out in past offerings of this course at UW, or similar courses at other schools. Using any pre-existing solutions from these sources, from the Web or other algorithms textbooks constitues a violation of the academic integrity expected of you and is strictly prohibited.

Most of the problems require only one or two key ideas for their solution. In writing up your solutions make sure that you clearly write out the main ideas of your solution first so that if you make a mistake in the details you can still get good partial credit for the problem. After you sketch out your solution try to clean up your presentation to make sure that you are only making necessary correct claims since additional incorrect claims will hurt your score.

Please typeset solutions for legibility and hand in hard copies. (The goal for this is not to be time-consuming so don't waste time using drawing programs; hand-drawn diagrams are OK.)

Whether or not the problem asks for it explicitly, you are required to prove that your algorithms do what you claim.

A final piece of advice: Begin work on the problem set early and don't wait till the deadline is only a few days away.

Problems:

1. Kleinberg and Tardos, Chapter 1, Problem 4, pages 23-24.

2. Kleinberg and Tardos, Chapter 1, Problem 6, pages 25-26.

3. Kleinberg and Tardos, Chapter 2, Problem 8, pages 69-70. For part (a) write precisely what the best possible solution is for k=2 and n=25. Write the complexity of your solution to part (b) as a function of both k and n. Try to find the best possible solution and argue that for each k your solution is asymptotically best possible as a function of n.

4. Consider the problem of making change for n cents using the least number of coins.

   1. Describe a greedy algorithm to make change consisting of quarters, dimes, nickels, and pennies. Prove that your algorithm yields an optimal solution.

   2. Suppose that the available coins are in the denominations 1,b¹, b²,...,b^k for some integers b > 1 and k≥1. Show that the greedy algorithm always yields an optimal solution.

   3. Give a set of coin denominations for which the greedy algorithm does not yield an optimal solution.

   4. Extra credit: Give a condition that generalizes those in parts (a) and (b) under which the greedy algorithm will yield an optimal solution.

5. Kleinberg and Tardos, Chapter 4, Problem 17, page 197.

6. Kleinberg and Tardos, Chapter 4, Problem 24, pages 200-201. Note that unlike the example, the optimal solution may not put all intermediate nodes at the same level. In that example if the v"-c edge originally had length 1 then the cheapest solution would increase the length of the v-v" edge to 3.