[Solved] 50.004 Problem set2

Note: This problem set is on dynamic programming. For algorithm design questions that specifically ask for algorithms using dynamic programming, no credit will be given if you do not use dynamic programming.

Following the notation used in the textbook, we write A[1..n] to mean an array A indexed from 1 to n. This means the first entry of A is A[1].

Question 1. You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint stopping you from robbing all of them is that every pair adjacent houses has a connected combined security system that will automatically contact the police if both houses were broken into on the same night.

Given an array of non-negative integers A[1..n], representing the amount of money in dollars that each house has, determine the maximum amount of money in dollars you can rob tonight without alerting the police.

• Find a recurrence for this problem. Specify the base cases for your recurrence. [3 points]
• Design an algorithm to solve the problem with dynamic programming. Please give your algorithm in pseudocode. Your algorithm should take as its input an array A[1..n] of nonnegative integers, and return as its output the integer representing the maximum amount of money that can be robbed. [5 points]
• Analyze the time and space complexities of your algorithm. [2 points]

Question 2. Suppose there are n items arranged in a straight row, where two players alternately take turns to select. The rule is that each player can only choose either the first item or the last item, in the current row. Selected items are removed from the row. Player 1 picks one of the items (from either end of the row), followed by Player 2, followed by Player 1, and so on. This process continues until all items have been selected.

Let A[1..n] be an array of non-negative integers representing the scores of the respective n items that a player gets for selecting them. After all items have been selected, the player with the maximum score wins. Design an algorithm with dynamic programming to predict whether Player 1 is the winner. You can assume each player plays to maximize his/her score. If the scores of both players are equal, then Player 1 is the winner by default.

Example:

Input: [1,5,233,7]

Output: TRUE

Explanation: Player 1 first chooses the item with score 1. Then Player 2 has to choose between two items with scores 5 and 7 respectively. No matter which item Player 2 chooses, Player 1 would be able to choose the item with score 233. Finally, player 1 has a higher score (234) than player 2 (12), so the output of the algorithm given this input [1,5,233,7] must be TRUE, representing that Player1 wins.

• Find a recurrence for this problem. Specify the base cases for your recurrence. [3 points]
• Design an algorithm to solve the problem with dynamic programming. Please give your algorithm in pseudocode. Your algorithm should take as its input an array A[1..n] of non-negative integers, and return as its output either TRUE or FALSE. [5 points] (iii) Analyze the time and space complexities of your algorithm. [2 points]

Question 3. Let G = (V,E) be an unweighted directed acyclic graph with n vertices. Let s and t denote two vertices of G, such that the in-degree of s is 0 and the out-degree of t is 0. Suppose there exists a path from s to t. Your goal is to compute a longest path in G from s to t. By longest, we mean this path has the maximum number of edges among all possible paths from s to t. You may assume that the input graph G has the attribute G.V representing the list of vertices of G, and the attribute G.Adj representing the adjacency list for G. For any vertex u of G, you may also assume that G.Adj[u] represents a linked list of the vertices adjacent to u, with u as the tail.

• Find a recurrence for this problem. Specify the base cases for your recurrence. [3 points]
• Design an algorithm to solve the problem with dynamic programming. Please give your algorithm in pseudocode. Your algorithm should take as its input a graph G, and return as its output an array of vertices [u₁,,u_k], representing a longest path hu₁,,u_ki from u₁ = s to u_k = t. [5 points]
• Analyze the time and space complexities of your algorithm. [2 points]

Question 4. Given two strings s₁ and s₂, which consist of lowercase English letters, find the minimum number of operations required to convert s₁ to s₂.

You have the following three operations permitted on a string:

Insert a character.

Delete a character.

Replace a character.

Example:

Input: s₁ = intention, s₂ = execution

Output: 5

Explanation:

1: inention intention (remove t)

2: enention inention (replace i with e)

3: exention enention (replace n with x)

4: exection exention (replace n with c)

5: execution exection (insert u)

• Find a recurrence for this problem. Specify the base cases for your recurrence. [3 points]
• Design an algorithm to solve the problem with dynamic programming. Please give your algorithm in pseudocode. Your algorithm should take as its input two character strings s₁ and s₂, and return as its output an integer representing the minimum number of operations required. [5 points]
• Analyze the time and space complexities of your algorithm. [2 points] Question 5. (i) Suppose that in the rod-cutting problem, we also had a limit l_i on the number of pieces of length i that we are allowed to produce, for i = 1,2,n. Show that the optimal-substructure property (as described in Lecture L10.02, slide 16) no longer holds. [3 points]
• In Lecture L10.02, on slide 10, we gave an algorithm (using tabulation) to compute and print the first n = 100 Fibonacci numbers. What is the space complexity of this algorithm, in terms of n? Justify your answer with details. [3 points]
• In Lecture L11.02, on slide 19, we gave an algorithm (using bottom-up dynamic programming) to solve the LCS problem. What is the space complexity of this algorithm? Justify your answer with details. [4 points]

Question 6. Let A[1..n] be an integer array. Solve the following problems using dynamic programming. Please give your algorithm in pseudocode. What are your sub-problems? What is your recurrence that relates the sub-problems? Also, what are the base cases of your recurrence? Analyze the time and space complexities of your algorithm.

• Find the sum of the contiguous subarray A[.j](1 i j n), which has the largest sum ]. [5 points]
• Find the product of the contiguous subarray A[.j](1 i j n), which has the largest product]. Note: Here largest refer to the numbers, not their magnitudes. For example, 2 is larger than -6. [10 points]
• A subarray A[.j] (for 1 i j n) is said to be a roller-coaster if and only if: For i k < j, we have A[k] > A[k + 1] when k is odd, and A[k] < A[k + 1] when k is even; OR, for i k < j, we have A[k] > A[k + 1] when k is even, and A[k] < A[k + 1] when k is odd. In other words, a subarray A[i..j] is a roller-coaster if the comparison symbols flip between < and > for every two consecutive pairs of elements in this subarray. Find the maximum length of a roller-coaster in A. [10 points]

Example:

Input: [6,3,2,8,7,9,9,4,5]

Output: 5

Explanation: A[2] > A[3] < A[4] > A[5] < A[6]

Question 7. Knapsack Problem: Given a knapsack of maximum capacity m, we want to pack inside it items selected from a set of n items. Item i (for 1 i n) has size s_i 0 and value v_i 0. Your goal is to select items of total size at most m, such that the total value is maximized.

• Assume that each item could be selected at most once. During Week 10s cohort class, we discussed the bottom-up dynamic programming approach for solving the knapsack problem. Suppose that m = 15 and n = 5, where the sizes are s₁ = 1,s₂ = 1,s₃ = 2,s₄ = 4,s₅ = 12, and the values are v₁ = 1,v₂ = 2,v₃ = 2,v₄ = 10,v₅ = 4. Please give the corresponding 2-dimensional table of recorded values after this knapsack problem has been solved using bottom-up dynamic programming. What does each entry represent?

What is the indexing for your table? [5 points]

• Suppose that item i could be selected up to t_i(t_i > 0) times. Design an algorithm to solve this modified knapsack problem with dynamic programming. Find a recurrence for this problem. Specify the base cases for your recurrence. Please give your algorithm in pseudocode. Also, analyze the time and space complexities of your algorithm. [10 points]
• Suppose that each item could be selected at most once, and suppose further that at most n₀ items can be selected, where 0 < n₀ n. Design an algorithm to solve this new modified knapsack problem with dynamic programming. Find a recurrence for this problem. Specify the base cases for your recurrence. Please give your algorithm in pseudocode. Also, analyze the time and space complexities of your algorithm. [10 points]