CS 4349.003. Advanced Algorithm Design and Analysis Spring 2017 Assignment 6 Wed, Apr 12 You can write or type your answers. Submit in class or upload on elearning. Due: 1:00 PM, Tue, April 25 1. Run Bellman-Ford algorithm on the graph in Fig. 24.4 (p. 652), using z as source. Show your output in the form of a table, like we did in class. 2. Write an efficient algorithm to count the number of paths from a source s to each node of a DAG G=(V,E). Note that the paths need not be edge-disjoint. So, s->a->c and s->a->b->c are counted as two different paths from s to c. Hint: Write a recurrence for N(u) = number of paths in G from s to u. ind an efficient way to computer N(u) for all u in V. 3. Given a directed graph G=(V,E), with positive integer weights w:E-->Z+, and a source vertex s in V, write an efficient algorithm that computes for each vertex u in V, RT(u) = delta(u,s) + delta(s,u), and stores it in u.rt. RT(u) is the round-trip distance between u and s. 4. Extend Floyd-Warshall algorithm to compute the predecessor matrix Pi, where Pi[u,v] is the predecessor of v on the shortest path from u to v computed by the algorithm, whose length is D[u,v]. Optional problems (for extra credit): A. Problem 24-3 (p. 679). Arbitrage B. Find shortest paths from z in the graph in Fig. 24.6 (p. 659), using Dijkstra's algorithm. C. Run Floyd-Warshall algorithm on the graph in Fig. 25.2 (p. 691). Show the matrix after each iteration of k.