Algorithm Design Techniques
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
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, a, ..., a[n], if 1<=
i1 < i2 < ... < ik <=
The subsequence is increasing if a[i1] <= a[i2]
<= ... <= a[ik] and decreasing if
a[i1] >= a[i2] >= ... >=
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