CS180 Homework 3
All algorithms/proofs should be in bullet form: step by step or psuedo code.
1. Exercise 10 Page 110
2. Exercise 6 on page 108
3. Exercise 12 on page 112
4. Exercise 3 on page 189
5. Exercise 6 on page 191
6. (a) Can you design an algorithm that finds the longest path in a directed
graph (DG)? (you can use an edge at most once)? If yes, describe
the algorithm and analyze its time complexity.
(b) Can you design an algorithm that finds the longest path in a directed
acyclic graph (DAG)? (you can use an edge at most once)? If yes,
describe the algorithm and analyze its time complexity.
1
