20CS472001  Design and Analysis of Algorithms II  Winter 2011 


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.
Consider multiplying more than two matrices such as:
A^{10x4}*B^{4x8}*C^{8x2}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?