Due Date: November 15th, 2005 at 2:00 PM
See course policy regarding late homework submissions
- Read Chapter 3 of the textbook in detail.
- Problems: You need to turn in a hard copy of your written
solutions to the following exercises
at the beginning of class on the day the homework is due.
Remember to show your work and explain your answers.
Correct answers without complete explanations won't receive full credit.
Incorrect answers with explanations may receive partial credit.
For each of the algorithms that you write as part of your HW solutions,
remember that you are required to:
- show the algorithm's correctness
(i.e., it terminates producing the correct result), and
- analyze its time complexity in detail.
- Chapter 3: exercise 1.
- Chapter 3: exercise 2.
- Chapter 3: exercise 7.
- Chapter 3: exercise 9.
- Give a linear time algorithm (i.e., O(m+n)) that takes as
input a DIRECTED acyclic graph G=(V,E) and two vertices s and t,
and returns the number of paths from s to t in G.
Your algorithm only needs to count the paths, not list them.
For instance, in the graph of Figure 3.8 (page 103) of the textbook,
there are exactly 3 paths from v2 to v5:
v2-v5;
v2-v3-v5;
v2-v3-v4-v5.