CIS 675: Algorthms – Spring 2019
Homework 4

Version 4 (8 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.

(30 points) ♦ Be sure to read the paragraph before problem 341. ♦
1. (15 points) PG Problem 341.
2. (15 points) PG Problem 343.
  This is also Problem 343 is also DPV Problem 2.17 and is related to the Bisection method.
(20 points)
1. (10 points) DPV Problem 2.19(a).
2. (10 points) DPV Problem 2.19(b), i.e., find an $O(n\cdot k \cdot \log k)$ -time divide-and-conquer algorithm for this problem. You do not have to do a run-time analysis for this part.
(24 points)
1. (8 points) DPV Problem 3.1.
2. (8 points) DPV Problem 3.2(a).
3. (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.