CS4040/5040
Homework # 4
(CS4040 50 pts / CS5040 60 pts)
1. (10 pts.) Give the optimal parenthization of the matrices, and the number of multiplications required for the optimal solution of the following chain matrix multiplication
problem. Show all work, including any tables required.
Matrix dimensions are: A[10×2], B[2×8], C[8×12], D[12×100], E[100×4], F[4×44].
2. (10 pts.) What is the solution to the problem (with the same matrices as the previous
question) if instead of trying to minimize the number of multiplications, we instead
want to find the maximum amount of multiplications? Give the optimal parenthization
of the matrices (for this new version of the problem), and the number of multiplications
required for the optimal solution of this chain matrix multiplication problem. Show
all work, including any tables required.
3. (10 pts.) What modification to QuickSort will guarantee that it runs in O(n lg n) time
in the worst case?
4. (10 pts.) Compute the Longest Common Subsequence of the following strings
representing DNA strands. Show all work, including any tables required.
String A = “CGCCGATGTCCGATCC”, B = “GGCCCTTTAAGTCAGCA”
5. (10 pts.) Activity Selection. Give the solution to the following activity selection problem. Show all work.
Activity # si fi
1 2 3
2 1 2.5
3 8 10
4 1 5
5 7 8
6 2 5
7 4 5
8 8 11
9 2 6
10 5 9
11 3 4
6. (10 pts.) CS5040 only Suppose you have a list of n unsorted distinct numbers and
you want to find which ones are closest to the median. In particular, you want to find
the m numbers closest to the median in this list of numbers. Give an algorithm to find
these m numbers that runs in time O(n).
1
