Algorithm Design Techniques
Due: Feb 2, 2004 5pm
Revision 2004.1.27: Condition P3' is stronger
than in the original statement of the assigment.
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. (Greedy) Read the course notes on
( http://www.cs.mcgill.ca/~avis/courses/360/notes/selection.ps )
Consider the following property:
P3' : For every subset U of the base set S, every
maximal admissible subset of U has the same cardinality.
(a) For each of Examples (1) to (6) in the notes decide wheter P3' holds.
If it does, give a proof,
if it does not, give a counterexample.
(b) Prove that if a selection problem satisfies P1, P2 and P3, then it
also satisfies P3'.
Prove that if a selection problem satisfies P1,
P2 and P3', then it also satisfies P3.
2. (Matrix Chain Multiplication).
Read Cormen et al. Section 15.2.
(a) Use the algorithm Matrix-Chain-Order on P. 336 of the text to
find the optimal way of multiplying matrices with dimension sequence
(10,2,9,4,6). Model your answer on Figure 15.3.
(b) Show how to modify the algorithm to find the worst way of multiplying
matrices (ie. most multiplications). Illustrate your algorithm on the same
dimension sequence as part (a).