Algorithm Design Techniques

COMP-360B              Assignment 2             Due: Feb 16, 2004 5pm

Assignments are to be left in the box in McConnell 1st floor, near elevators.
Late assignments  -10% per day, including weekends.
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. a[i1], a[i2], ...,  a[ik] is a subsequence of a  sequence of  a[1], a[2], ..., a[n], if 1<=  i1 < i2 < ... <  ik <= n.
The subsequence is increasing if a[i1] <=  a[i2] <=  ... <=   a[ik] and decreasing if
a[i1] >=  a[i2] >=  ... >=   a[ik].
Write a dynamic programming algorithm that finds a longest increasing subsequence and a longest decreasing subsequence of a sequence of numbers, thus finding the longest monotone subsequence.

Bonus: Show that every sequence of k2 integers has a monotone subsequence of at least k integers.
2.  Let G  be a weighted directed network, with source s. Prove that if a sequence of relax operations(text p. 586) results in  pi[s] getting set to a non null value, then G contains a negative weight cycle.

3. Run the Bellman-Ford algorithm on the digraph shown in figure 25.1, P. 626, showing the result after each iteration.  Process the edges in increasing lexicographic order: 12, 13, 15, 24, 25, 32, 41, 43, 54.
3.  Text , Exercise 25.3.6