Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
CS547 Homework 3 - due Friday September 22, 2006 ----------------------------------------------------- For each of the following problems (except for the extra credit), you must solve it by either modifying an existing algorithm, or just showing how an existing algorithm can be applied directly to the given problem. The way you must modify an existing algorithm is to copy the algorithm directly from the book and add some new data structure or functionality to the algorithm. You must highlight the part that you have modified. 1. Chapter 3, problem 2 (Modify DFS, page 93) 2. Chapter 3, problem 3. Note: Don't just add a check for a cycle on the beginning of the topological sort algorithm. Instead, make the cycle check part of the algorithm. (Modify TopSort, page 102, it's ok that it is THETA(V^2) since the same modification could be done to the more efficient version) 3. Chapter 3, problem 4 4. Chapter 3, problem 10 (Modify BFS, page 90) 5 (Extra Credit). In a directed garph, a sink is defined to be a node v such that all other nodes have an edge into v, but there are no edges out of v. Write your own algorithm to determine if a directed graph has a sink. Your algorithm must run in THETA(V) time. Use the adjacency matrix represetnation for the graph. Hint: One way to do it is to keep a set of nodes that may possibly be a sink, and a set of nodes that cannot possibly be a sink.