Algorithm Design Techniques

COMP-360 Assignment 2 Due: Beginning of class, Thurs Oct 4

Late assignments -10% per day, including weekends.
Please give late assignments to Perouz (T.A) in McConnell 232
If you work closely with someone else, indicate the person's name(s) on your homework.
The final write-up of each assignment must, however, be your own work.

1. Text, P. 313, problem 2.

2. Text, P. 330, problem 22.

3. Consider the Bellman-Ford algorithm Push-Based-Shortest-Path on pages 298-9, modified so that the outer loop is also executed for i=n.

     Claim: G has a negative cyle if and only if there is some change in the array M on the n-th iteration.
     For each case below, either prove the claim or give a counterexample using a graph of the given type.

     (a) In G there is a vertex v such that v is connected to every other vertex by a directed path.
     (b) In G there is a vertex v such that for each other vertex w there is a directed path from v to w and from w to v.

If you find a counterexample, give the array M after each iteration and state the order in which you consider vertices.
______________________________________________________________________________________________________________________________

4. Write a one page (at most 400 words) critical review of the economist articles on algorithms (here and here).
Are there are inaccuracies in the article? Do you find it convincing? Anything else you think should have been included? etc.

Note: You must prove the correctness of your algorithms, and analyze their running times.
Carefully review the proofs of similar results in the text first!