CIS 675: Algorthms – Spring 2019
Homework 9

Abbreviations

• DPV = Algorithms, by S. Dasgupta, C. Papadimitriou, and U. Vazirani, McGraw-Hill, 2007.
• PG = Problems on Algorithms, 2/e, by Ian Parberry and William Gasarch.

Reading

• Chapters 7 and 8 of DPV

Problems

1. (20 points) DPV, Exercise 7.1. Be sure to draw the diagram.

2. (20 points) DPV, Exercise 7.4. Be sure to draw the diagram.

3. (8 points) DPV, Exercise 7.6.

4. (12 points) DPV, Exercise 7.7.

5. (20 Points) DPV, Exercise 7.17.

6. (20 Points) DPV, Exercise 7.18, parts (a) and (b).