CPSC 629: Analysis of Algorithms
Homework Assignment #1

Due: Thursday January 28, 1999 at the beginning of class

General Guidelines for Homework

• Be careful of the distinction between exercises and problems in [CLR]. Each section ends with a set of exercises, each chapter ends with a set of problems.
• Be clear and precise. Write neatly and legibly (you will lose points for sloppy and illegible handwriting). Justify all answers, even if not specified in the question. Use good judgement concerning how detailed to make your answer.
• If the question is not fully specified, you may need to make some assumptions. In this case, you must state any assumptions you make, and justify why they are reasonable.
• Everyone must turn in their own copy of the assignment. You may consult outside material or work with others (this is encouraged), but you must reference your sources (people, texts, solutions, etc.); in particular, list all collaborators on the first page of your assignment.

Do the following problems.

1. Find an optimal order for multiplying a sequence of matrices that are given by the dimension sequence <10, 3, 12, 1, 50, 2> (i.e., matrix A1 is of dimension 10 x 3 , matrix A2 is of dimension 3 x 12, etc). Use algorithm Matrix-Chain-Order on p. 306 and show your work.

2. Describe a dynamic programming algorithm for determining the maximum number of multiplications that could be performed when multiplying a sequence of matrices (that are given by a dimension sequence). Your algorithm should run in O(n³) time, and use O(n²) space. Analyze the running time and space requirements of your algorithm. Also, prove that your algorithm correctly determines the maximal number of multiplications.

3. Show how your algorithm from #2 above works on the sequence of matrices given by the dimension sequence in #1.