CSCI 570 – Fall 2020 – HW7
Due October 21st 11:59pm 2020
1 Graded Problems
1. Let us think of character strings as sequences of characters. Given two se- quences X = and Z = , we say that Z is a sub- sequence of X if there is a strictly increasing sequence of k indices (i1,i2,…,ik) (1 ≤ i1 < i2 < ... < ik ≤ n) such that Z = xi1,xi2,...,xik. For example, let X = ABRACADABRA and let Z = AADAA, then Z is a subsequence of X. Given two strings X and Y , the longest common subsequence of X and Y is a longest sequence Z that is a subsequence of both X and Y . For example, let X = ABRACADABRA and let Y = Y ABBADABBADOO. Then the longest common subsequence is Z = ABADABA.
Given two sequences X = (x1,...,xm) and Y = (y1,...,yn) come up with an efficient algorithm using dynamic programming that determines the length of their longest common subsequence, and more generally the sequence itself. Note that the subsequence is not necessarily unique.
2. This problem involves the question of determining the optimal sequence for performing a series of operations. This general class of problem is important in compiler design for code optimization and in databases for query optimization.
Some background on matrix multiplication:
let A be a p×q matrix and B be a q×r matrix: We know that for matrix multiplication, the number of columns of A must equal the number of rows of B. In particular for 1 ≤ i ≤ p and 1 ≤ j ≤ r, for C = AB we have:
q
C[i, j] = A[i, k]B[k, j] k=1
This corresponds to the (hopefully familiar) rule that the [i, j] entry of C is the dot product of the ith (horizontal) row of A and the jth (vertical) column
1
of B. Observe that there are pr total entries in C and each takes O(q) time to compute, thus the total time to multiply these two matrices is proportional to the product of the dimensions, pqr.
We also know that matrix multiplication is associative, meaning:
(AB)C = A(BC)
Notice the difference between the order of operations. On the right side we have to compute AB first and then multiply it by C while on the left side BC is computed first and then it is multiplied by A.
Suppose that we wish to multiply a series of matrices C = A1A2...An
Devise a dynamic programming algorithm that determines the best order to perform the multiplications. Note that this algorithm does not perform the multiplications, it just determines the best order in which to perform the multiplications and the total number of operations.
3. Alice is the owner of a honey fried chicken restaurant. One day she receives a request for preparing and delivering meals for a CS conference at USC. The coordinator of the conference has collected orders for all conference participants. Unfortunately, Kara’s restaurant is too small to support all of the orders made. She has to decide to forfeit some orders, but she wants to earn as much as she can. Here is the information she has:
• There are N orders from the conference. For the i − th order, Kara knows it will take ti minutes to prepare and will need ki pounds of chicken.
• The coordinator will pay ci dollars if Kara can deliver the i − th order. If Kara cannot deliver that order, she could cancel it without paying any penalty.
• Alice has only T minutes and K pounds of chicken to prepare a meal.
• T,K, N and ci,ti,ki for all i are positive integers for simplicity.
Help Alice to respond to the coordinator with the list of orders she could deliver
by designing a dynamic programming algorithm.
• (a) What is the subproblem?
• (b) What is the recurrence relation for the subproblems. Also describle your algorithm?
• (c) What is runtime for your algorithm? 2
2 Practice Problems
4. Reading assignment: Kleinberg and Tardos, Chapter 6.
3