Description
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. [3 points]
(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. [5 points]
(iii) 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.
1
(i) Find a recurrence for this problem. Specify the base cases for your recurrence. [3 points]
(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. [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.
(i) Find a recurrence for this problem. Specify the base cases for your recurrence. [3 points]
(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. [5 points]
(iii) Analyze the time and space complexities of your algorithm. [2 points]
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. [3 points]
(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. [5 points]
(iii) Analyze the time and space complexities of your algorithm. [2 points]
2
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. [3 points]
(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. [3 points]
(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. [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.
(i) Find the sum of the contiguous subarray A[i..j](1 ≤ i ≤ j ≤ n), which has the largest
sum Pj
k=i A[k]. [5 points]
(ii) Find the product of the contiguous subarray A[i..j](1 ≤ i ≤ j ≤ n), which has the largest
product Qj
k=i A[k]. Note: Here “largest” refer to the numbers, not their magnitudes. For
example, 2 is larger than -6. [10 points]
(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. [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 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? [5 points]
(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. [10 points]
3
(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. [10 points]
4
