Algorithm Design Techniques
Due: Beginning of class, Thurs Oct 4
Late assignments -10% per day, including
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,
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
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
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!