Homework 5

**Abbreviations**

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

- Chapters 3 and 4 of DPV

(16 points) Suppose is a directed acyclic graph represented by a adjacency lists. Divise a linear time algorithm that, given such a , returns the length of the longest path in . Prove your algorithm runs in -time

(16 points) Suppose is a directed graph represented by a adjacency lists. Divise a linear time algorithm that, given such a , returns a list of all the source vertices of . (Note, this list may be empty.) Prove your algorithm runs in -time.

There is a simple solution that does not involve any DFS’s or BFS’s.*Hint:*(16 points) DPV Problem 3.18

(16 points) DPV Problem 3.22

First consider the special case of G being an directed acyclic graph.*Hint:*(16 points) DPV Problem 3.23

(20 points) DPV Problem 4.1