CS180 Homework 6
All algorithms/proofs should be in bullet form: step by step or psuedo code.
1. Exercise 19 on page 329
2. Exercise 22 on page 330
3. Exercise 24 on page 331
4. Exercise 7 on page 417
5. Exercise 9 on page 419
6. Given a sequence of numbers find a sub-sequence of alternating order,
where the sub-sequence is as long as possible. (that is, find a longest
sub-sequence with alternate low and high elements). As always, prove the
correctness of your algorithm and analyze its time complexity.
Example Input: 8, 9, 6, 4, 5, 7, 3, 2, 4
Output: 8, 9, 6, 7, 3, 4 (of length 6) because- 8 < 9 6 < 7 3 < 4
1
