CS 330

Summer 2007

Assignment #4

Date Due: Tuesday, June 19

Reading: Chapter 26, pages 643-669.

Problems:

1. In class we have seen a few algorithms which deal with considering all subsets of a given set.

Write an algorithm which takes a set of n elements, say S ={1, 2, 3, ... n} and which outputs the list of all 2ⁿ subsets of S. (Don't forget the empty set and the set S itself. )

2. Use the chain matrix multiplication algorithm to find the best order of multiplying 5 matrices whose dimensions are 5 x 10, 10 x 3, 3 x 12, 12 x 6 and 6x4.

3. Page 384, problem 16.2-5.

4. Page 402. problems a, and b.

5. Page 402. problem c.

6. a. Go back to problem 16-1, part d. on page 402.

Assume there 3 types of coins which are worth 1, 5, and 9 cents each. Answer problem 16-1, part d. by developing a complete dynamic programming solution to do problem.

Your answer should include a description (pseudocode) of the iterative algorithm , the specific table you need to fill in and which square in the table the answer appears in, the complexity of the algorithm, and a method of actually finding which coins are given as change when you run the algorithm.

b. Show how your algorithm works to find change for 11 cents.