Assignment 3-Longest common subsequence

CS 341: Algorithms 
Assignment 3
For all algorithm design questions, you must give the algorithm, argue the correctness, and analyze time complexity.
1 Longest common subsequence of many strings [10 marks] Recall that a string z = z1 z2···zk is a subsequence of a string x = x1 x2···xn if there are indices 1 ≤ i1 < i2 < ···ik ≤ n for which z1 = xi1, z2 = xi2, ..., zk = xik. The string z is a common subsequence of a set of m strings x(1),x(2),...,x(m) if and only if z is a subsequence of all m of these strings. For example, the string ONI is a common subsequence of the 3 strings
x(1) = POLYNOMIAL x(2) = EXPONENTIAL x(3) = CONSTANTTIME
but the string PAL is not. Design an dynamic programming algorithm that, given as input a set of m strings x(1),x(2),...,x(m) of lengths n1,...,nm, respectively, outputs the length of the longest common subsequence of x(1),x(2),...,x(m).
2 Bookshelf [10 marks]
In the LibraryBookshelf problem, you are given as input a set of n books and the thickness ti 0 of each book i ∈{1,2,...,n}, along with the width W of the bookshelves that will be used to build the library. Design a greedy algorithm that determines the minimum number of bookshelves required to store the books, keeping in mind that since the books have call numbers, you must place them in order in the bookshelves, but that you can choose how many go on a shelf.
1
CS 341: Algorithms (S’18) Assignment 3 E. Blais, N. Harms, E. Zima
3 Hiring [10 marks]
In the Hiring problem, you own two companies that have salary budgets B1 0 and B2 0, respectively. There are n people 1,2,...,n applying to work at one of your companies, where person i requires salary si and would generate revenues r1(i) 0 and r2(i) 0 to companies 1 and 2, respectively. A valid solution to the Hiring problem is the maximum value R for which there exists a pair of disjoint sets S1,S2 ⊆{1,2,...,n} that satisfy (i) Pi∈S1 si ≤ B1, (ii) Pi∈S2 si ≤ B2, and (iii) Pi∈S1 r1(i) +Pi∈S2 r2(i) = R. Design a dynamic programming algorithm to solve the Hiring problem. (Note that to solve the problem, the algorithm needs to find the maximum revenue R as described above, but it does not need to identify the sets S1 and S2.) In your description of the algorithm, make sure you clearly indicate what are the subproblems and the order in which they are solved. Also: your time complexity analysis should be in terms of n, B1, and B2.
4 Scriptio continua [10 marks] Let Σ = {a,b,c,...,z} denote the alphabet, and let S ⊂ Σ∗ be the set of all words in the English language. In the SriptioContinua problem, you are given a string s ∈ Σn (that does not have any spaces or punctuation marks) and you must output True if there exists a sequence of words w1,...,wm ∈ S such that s = w1w2···wm is the concatenation of the words w1,...,wm, and False otherwise. For example, for the input
s = thisstringisasequenceofwordswrittenwithoutanyspaces
the valid solution is True since we can partition s into the sequence of 11 words
s = this |{z} w1
string |{z} w2
is |{z} w3
a |{z} w4
sequence | {z } w5
of |{z} w6
words |{z} w7
written | {z } w8
without | {z } w9
any |{z} w10
spaces |{z} w11
with w1,w2,...,w11 ∈ S. 1. Design a dynamic programming algorithm for solving the SriptioContinua problem. In your solution, you can assume that you have access to an algorithm IsWord that, on any input w ∈ Σ`, outputs True if w ∈ S and False otherwise, and has time complexity Θ(1). You should aim for an algorithm with runtime O(n2).
2. Modify the algorithm in part (a) so that when the answer is True, the algorithm also outputs w1,...,wm ∈ Sm for which s = w1w2···wm.
2
CS 341: Algorithms (S’18) Assignment 3 E. Blais, N. Harms, E. Zima
5 Shipping paper [10 marks]
Note: For this assignment only, you do not need to program your solution to the problem; only the written solution needs to be submitted.
There are two warehouses, V and W, which ship supplies of paper to n factories, denoted F1,...,Fn. The factory Fi requires exactly di units of paper, it costs vi to ship a unit of paper from V to Fi, and it costs wi to ship a unit of paper from W to Fi, for each i ∈{1,2,...,n}. The total amount of paper available at V and W is rV and rW, respectively, where rV +rW = d1 +···+dn. We want to determine how much paper to ship from V and W to each of the factories so that the total shipping cost is minimized. Formally, let xi denote the number of units of paper that are shipped from V to Fi and yi denote the units of paper that are shipped from W to Fi, for 1 ≤ i ≤ n. The following constraints must be satisfied: • x1,...,xn,y1,...,yn are non-negative integers, • x1 +···+ xn = rV , • y1 +···+ yn = rW, and • xi + yi = di for each i ∈{1,2,...,n}. The total shipping cost is
C =
n X i=1
(vixi + wiyi).
An instance of the Shipping problem is specified by the values rV , rW, d1,...,dn, v1,...,vn, and w1,...,wn. A valid solution to such an instance is an n-tuple (x1,...,xn) that satisfies the constraints above and minimizes C. (Since the value of xi determines the value of yi uniquely for each i ∈ {1,2,...,n}, the n-tuple (y1,...,yn) does not need to be provided explicitly in the solution.) Design a greedy algorithm that solves the Shipping problem.
3