CIS 675: Algorthms – Spring 2019
Homework 6

Version 1 (22 February 2019)

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 4 and 5 of DPV

Problems

(16 points) DPV Problem 4.2.
(16 points) PG Problem 434.
(16 points) DPV Problem 4.13.
Hints for part (b): (i) $|E|$ is $O(|V|^2)$ . (ii) Binary Search may be useful.
(16 points) DPV Problem 4.21.
(16 points) DPV Problem 5.2(a).
(20 points) DPV Problem 5.9(a,b,c,d).
Hint: The counterexamples can be build using four vertices.