## 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[i_{1}], a[i_{2}], ..., a[i_{k}]
is a subsequence of a sequence of a[1], a[2], ..., a[n], if 1<=
i_{1} < i_{2} < ... < i_{k} <=
n.

The subsequence is increasing if a[i_{1}] <= a[i_{2}]
<= ... <= a[i_{k}] and decreasing if

a[i_{1}] >= a[i_{2}] >= ... >=
a[i_{k}].

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 k^{2} ^{}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