50.004-Problem Set 2 Solved

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.

(i)        Find a recurrence for this problem. Specify the base cases for your recurrence.

(ii)      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.                

(iii)    Analyze the time and space complexities of your algorithm.         

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.

 

(i)             Find a recurrence for this problem. Specify the base cases for your recurrence.

(ii)           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.

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.

(i)        Find a recurrence for this problem. Specify the base cases for your recurrence.

(ii)      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 [u1,...,uk], representing a longest path hu1,...,uki from u1 = s to uk = t.             

(iii)    Analyze the time and space complexities of your algorithm.         

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

You have the following three operations permitted on a string:

Insert a character.

Delete a character.

Replace a character.

Example:

 

Input: s1 = “intention”, s2 = “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’)

 

(i)      Find a recurrence for this problem. Specify the base cases for your recurrence.

(ii)    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 s1 and s2, and return as its output an integer representing the minimum number of operations required.     

(iii)  Analyze the time and space complexities of your algorithm.           

 

 Question 5. (i) Suppose that in the rod-cutting problem, we also had a limit li 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.           

(ii)      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.

(iii)    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. 

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.

(i)        Find the sum of the contiguous subarray A[i..j](1 ≤ i ≤ j ≤ n), which has the largest sum  ].         

(ii)      Find the product of the contiguous subarray A[i..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.           

(iii)    A subarray A[i..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.

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 si ≥ 0 and value vi ≥ 0. Your goal is to select items of total size at most m, such that the total value is maximized.

(i)        Assume that each item could be selected at most once. During Week 10’s 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 s1 = 1,s2 = 1,s3 = 2,s4 = 4,s5 = 12, and the values are v1 = 1,v2 = 2,v3 = 2,v4 = 10,v5 = 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?                                                                                                                

(ii)      Suppose that item i could be selected up to ti(ti 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.

(iii)    Suppose that each item could be selected at most once, and suppose further that at most n0 items can be selected, where 0 < n0 ≤ 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.