CSE 421 Assignment #10
Autumn 2005

Due: Friday, December 9, 2005, 1:30 pm.

Reading Assignment: Kleinberg and Tardo, Chapter 8 .

Problems: (see Grading Guidelines sheet before answering)

1. Kleinberg and Tardos, Chapter 7, Problem 19, pages 425-426.

2. Kleinberg and Tardos, Chapter 7, Problem 35, pages 436-437.

3. Kleinberg and Tardos, Chapter 7, Problem 39 a and b, pages 440-441.

4. Kleinberg and Tardos, Chapter 7, Problem 45, page 444. (Hint: convert this to a graph problem, without thinking too much about the economics. Set the problem up as a minimum cut problem to find the maximum value free-standing subset. If this is the entire set S, you will need to do something special to determine if it has a proper subset that is free-standing.)

5. Extra credit: Kleinberg and Tardos, Chapter 7, Problem 33, pages 435.