20-CS-472-001 Design and Analysis of Algorithms II Winter 2011

Dynamic Programming

Due: January 21, 2011

  1. Write a Dynamic Program for the vertex cover problem. Is it fast or slow in the worst case?

    Given a graph G=(V,E), a vertex cover for G is a subset V'of vertices V such that every edge in E is incident to at least one vertex in V'. The Vertex Cover Problem is the problem of finding a minimum size vertex cover for a given graph.

  2. Denote a matrix A of a rows and b columns by Aaxb. Recall the operation of multiplying matrices: The product Aaxb*Bbxc is a matrix of a rows and c columns such that the element of the ith row and jth column is the sum of the products of elements of the ith row of Aaxb and the jth column of Bbxc. Thus the number of scalar (plain old) multiplications typically used to build the matrix product above is a*b*c.

    Consider multiplying more than two matrices such as:

    One can multiply B and C first then multiply that result by A, or multiply A and B first then multiply the result by C. Either way, the outcome is the same. However, it is usually the case that one choice of multiplication order may produce a result using fewer scalar multiplications than the other order. In the above example multiplying A and B first uses 10*4*8=320 scalar multiplies to get a 10x8 matrix which multiplies with C using 10*8*2=160 scalar multiplications for a total of 320+160=480. However, multiplying B and C first uses 4*8*2=64 plus 10*4*2=80 scalar multiplications for a total of 144 to get the same result. Clearly, it is better to mutliply B and C first to save time.

    Now, suppose you are given a list of n matrices to be multiplied. Write a divide and conquer algorithm which determines the best order in which to multiply the matrices (with respect to minimizing the total number of scalar multiplications). Assume the maximum row dimension and the maximum column dimension is m. What is the complexity of your algorithm? How many different ways are there to multiply a list of n matrices? Based on this number, do you think your algorithm is fairly efficient?