Algorithm Design Techniques

COMP-360B Assignment 1 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 selection .
( 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).