CIS 675: Algorthms – Spring 2019
Homework 5

Version 0 (16 February 2019)

Abbreviations

DPV = Algorithms, by S. Dasgupta, C. Papadimitriou, and U. Vazirani, McGraw-Hill, 2007.

(16 points) Suppose $G=(V,E)$ is a directed acyclic graph represented by a adjacency lists. Divise a linear time algorithm that, given such a $G$ , returns the length of the longest path in $G$ . Prove your algorithm runs in $O(|V|+|E|)$ -time
(16 points) Suppose $G=(V,E)$ is a directed graph represented by a adjacency lists. Divise a linear time algorithm that, given such a $G$ , returns a list of all the source vertices of $G$ . (Note, this list may be empty.) Prove your algorithm runs in $O(|V|+|E|)$ -time.
Hint: There is a simple solution that does not involve any DFS’s or BFS’s.
(16 points) DPV Problem 3.18
(16 points) DPV Problem 3.22
Hint: First consider the special case of G being an directed acyclic graph.
(16 points) DPV Problem 3.23
(20 points) DPV Problem 4.1