Week 6 Assignment 6 (25,26 March)


1. Use graph A) and calculate the graphs that can be reached with exactly 2 and exactly 3 "hops" using matrix multiplication of adjacency matrices. Calculate the transitive closure of the graph.

2. Implement the Warshall algorithm and create the transitive closure graph of A). Verify the correctness of the algorithm, and justify it.

3. Use graph B). Simulate the Dijkstra's algorithm for all shortest paths (from leftmost node). First, assume all weights are positive (i.e. use absolute value of weights). Then use also negative values - what changes?

4. On graph B) - calculate all shortest paths by repeatedly "Relax"-ing the weight estimates. Now change the weight -2 into -4. Try the same. Can you propose a strategy to detect negative-weight cycles?

5. In the DAG - show how to calculate the single-source shortest paths when there can be negative weights (Always possible. Why?).

6. Bonus (3P) - make a simple program that takes in a list of words, uses words as nodes, calculates the weighted arcs between nodes so that if the suffix of a word A (e.g. taldrik) is also a prefix of another word (e.g. rikkur), then the larger the overlap can be (in this case: taldrikkur), the better the score is. Using this graph and single-source shortest path finding, try to find long 'chainable' novel and stupid words. Don't start programming unless you have a good idea, what exactly it should do - design without implementation will give you 1P. (Example wordlist: http://www.eki.ee/tarkvara/wordlist/ )