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