CS 6363.004: Algorithms
Spring 2019
Assignment 4
Wed, Mar 27, 2019

Due: 11:59 PM, Sun, Apr 14 (on elearning).

1. Write a DFS algorithm that prints out every edge of a given directed graph,
   together with its type (tree, back, forward, cross).

2. Consider a DAG G=(V,E) and a special node s in V.  Let N(u) be the number of
   distinct paths from s to u.  Note that the paths need to be distinct and not disjoint.
   Write a recurrence for N(u).  Write a dynamic program based on this recurrence,
   using a topological order of the nodes as the induction order.
   (This is Ex. 22.4-2 (p. 614) [Count number of paths in a DAG]).

3. Problem 22-2, parts d,f (p. 621-622) [Articulation points, bridges].

Optional problems:

4. Ex. 16.1-4 (p. 422) [Interval-graph coloring].

5. Ex. 16.2-1 (p. 427) [Fractional knapsack].