Homework 4

**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.

- Chapters 3 and 4 of DPV

- (30 points) ♦
*Be sure to read the paragraph before problem 341.*♦- (15 points) PG Problem 341.

- (15 points) PG Problem 343.

*This is also Problem 343 is also DPV Problem 2.17 and is related to the Bisection method.*

- (15 points) PG Problem 341.
- (20 points)
- (10 points) DPV Problem 2.19(a).
- (10 points) DPV Problem 2.19(b), i.e., find an -time divide-and-conquer algorithm for this problem. You
**do not**have to do a run-time analysis for this part.

- (24 points)
- (8 points) DPV Problem 3.1.
- (8 points) DPV Problem 3.2(a).
- (8 points) DPV Problem 3.2(b).

(12 points) DPV Problem 3.3.

(14 points) DPV Problem 3.11

**Painfully obvious hint:**There is a DFS involved.