Chapter 9 Directed graphs & Partial Orders276
(c)Explain the connection between increasing and decreasing subsequences ofS,
and chains and anti-chains under .
(d)Prove that every sequence,S, of lengthnhas an increasing subsequence of
length greater than
p
nor a decreasing subsequence of length at leastp
n.(e)(Optional, tricky) Devise an efficient procedure for finding the longest in-
creasing and the longest decreasing subsequence in any given sequence of integers.
(There is a nice one.)
Problem 9.33.
We want to schedulenpartially ordered tasks.
(a)Explain why any schedule that requires onlypprocessors must take time at
leastdn=pe.
(b)LetDn;tbe the strict partial order withnelements that consists of a chain of
t 1 elements, with the bottom element in the chain being a prerequisite of all the
remaining elements as in the following figure:
...
...
t - 1^n - (t - 1)What is the minimum time schedule forDn;t? Explain why it is unique. How many
processors does it require?
(c)Write a simple formula,M.n;t;p/, for the minimum time of ap-processor
schedule to completeDn;t.