Introduction to Algorithms: 6.006Massachusetts Institute of Technology November 16th, 2010Professors Konstantinos Daskalakis and Patrick Jaillet Handout 6Problem Set 6This problem set is divided into two parts: Part A problems are theory questions, and Part Bproblems are programming tasks.Part A questions are due Tuesday, November 30th at 11:59PM.Part B questions are due Thursday, December 2nd at 11:59PM.Solutions should be turned in through the course website. Your solution to Part A should be inPDF form using LATEX or scanned handwritten solutions. Your solution to Part B should be a validPython file, together with one PDF file containing your solutions to the two theoretical questionsin Part B.Templates for writing up solutions in LATEX are available on the course website.Remember, your goal is to communicate. Full credit will be given only to the correct solutionwhich is described clearly. Convoluted and obtuse descriptions might receive low marks, evenwhen they are correct. Also, aim for concise solutions, as it will save you time spent on write-ups,and also help you conceptualize the key idea of the problem.Part A: Due Tuesday, November 30th1. (25 points) Placing ParenthesesYou are given an arithmetic expression containing n real numbers and n − 1 operators, eacheither + or ×. Your goal is to perform the operations in an order that maximizes the value ofthe expression. That is, insert n − 1 pairs of parentheses into the expression so that its valueis maximized.For example:• For the expression 6 × 3 + 2 × 5, the optimal ordering is to add the middle numbersfirst, then perform the multiplications: ((6 × (3 + 2)) × 5) = 150.• For the expression 0.1 × 0.1+0.1, the optimal ordering is to perform the multiplicationfirst, then the addition: ((0.1 × 0.1) + 0.1) = 0.11.• For the expression (−3) × 3 + 3, the optimal ordering is ((−3) × 3) + 3) = −6.(a) (10 points) Clearly state the set of subproblems that you will use to solve this problem.(b) (10 points) Write a recurrence relating the solution of a general subproblem to solutionsof smaller subproblems.(c) (5 points) Analyze the running time of your algorithm, including the number of sub-problems and the time spent per subproblem.2 Handout 6: Problem Set 62. (25 points) Pots of GoldThere are N pots of gold arranged linearly. Alice and Bob are playing the following game.They take alternate turns, and in each turn they remove (and win) either of the two pots atthe two ends of the line. Alice plays first. Given the amount of gold in each pot, design analgorithm to find the maximum amount of gold that Alice can assure herself of winning.(a) (10 points) Clearly state the set of subproblems that you will use to solve this problem.(b) (10 points) Write a recurrence relating the solution of a general subproblem to solutionsof smaller subproblems.(c) (5 points) Analyze the running time of your algorithm, including the number of sub-problems and the time spent per subproblem. Hint: your overall algorithm should beO(N2).Part B: Due Thursday, December 2nd1. (50 points) Website RankingsIn class, you saw that the length of the longest common subsequence can be computed inO(n2) time for two strings x and y of length n, using dynamic programming. For general xand y, it is not known if this value can be computed in O(n1.999) time. In this problem, youwill learn how to compute it in O(n log n) time for non-repetitive strings.Theory part (do not submit a solution to it). Definitions:• Let z = (z1, . . . , zn) be a sequence of integers. We say that t = (t1, . . . , tk) is asubsequence of z if there is a sequence (i1, . . . , ik) of k indices such that i1< i2<. . . < ik, and for all j, tj= zij.• Let z = (z1, . . . , zn) be a sequence of integers. We write LIS(z) to denote the lengthof the longest increasing subsequence of z.Example: LIS( (6, 2, 7, 5, 3, 4) ) = 3, and this corresponds to the subsequence (2, 3, 4).• Let x = (x1, . . . , xn) and y = (y1, . . . , ym) be sequences of integers. We writeLCS(x, y) to denote the length of the longest common subsequence of x and y.Example: LCS( (6, 2, 7, 5, 3, 4), (5, 6, 1, 7, 3, 4) ) = 4, and this corresponds to the sub-sequence (6, 7, 3, 4).• Let z = (z1, . . . , zn) be a sequence of integers. We say that z is non-repetitive if nointeger appears twice in it.Example: (5, 6, 1, 7, 3, 4) is non-repetitive, and (4, 6, 1, 7, 1, 3) is not.Design algorithms for the following two problems:Handout 6: Problem Set 6 3(a) Show how to compute LIS(z) for a sequence z of n integers in O(n log n) time.Hint 1: Use the following sequence of arrays Ai. Let Ai[j], where i, j ∈ {1, 2, . . . , n},be the lowest integer that ends an increasing length-j subsequence of (z1, . . . , zi). If(z1, . . . , zi) has no increasing subsequence of length j, then Ai[j] = ∞.Hint 2: How can Aibe turned into Ai+1in O(log n) time? How can LIS(z) be extractedfrom An?(b) Show how to compute LCS(x, y) for two non-repetitive integer sequences x and y oflength n in O(n log n) time.Hint 1: Reduce to the previous problem.Hint 2: Create a sequence z from y in the following way. Remove all integers that donot appear in x, and replace the other ones by their index in x. How is LIS(z) relatedto LCS(x, y)?Coding part (50 points). Consider two web search engines A and B. We send the samequery, say “6.006”, to both search engines, and in reply we get a ranking of the first kpages according to each of them. How can we measure the similarity of these two rankings?Various methods for this have been designed, but here, we’ll use the simplest of them: LCS,the length of the longest common subsequence of the rankings.Your task is to write a program that uses the above O(n log n) algorithm to compute LCSfor two rankings. The program has to read the rankings from the standard input, and writetheir LCS to the standard output. We assume that pages are identical only if their URLs areidentical. No URL appears twice in a ranking. You can use the Python dictionary to convertthe input into an instance of the LIS problem.Input FormatLine 1: The number k of URLs we receive from each of the search engines.Lines 2 . . . k + 1: The list of k URLs received from A.Lines k + 2 . . . 2k + 3: The list of k URLs received from B.Sample
View Full Document
Unlocking...