What does the greedy choice property state?
Coins {1, 3, 4} are available in unlimited supply. For the amount 6, how many coins does the "largest coin first" greedy algorithm use, and how many does an optimal solution use?
With coins {1, 10, 25}, for which amount does "largest coin first" give a non-optimal answer?
Activities are given as [start, finish): A [1, 3), B [2, 5), C [4, 7), D [1, 8), E [6, 9), F [8, 10), G [9, 12), H [11, 13). An activity may start exactly when the previous one ends. Which set does the "earliest finish time first" greedy algorithm choose?
For the interval scheduling problem (maximise the number of non-overlapping activities), which greedy rule is always optimal?
A fractional knapsack has capacity 10. The items (weight, value) are (5, 30), (4, 28), (6, 24) and (3, 9). What is the maximum total value?
A 0/1 knapsack has capacity 10 and items (weight, value): (6, 30), (5, 20), (5, 20). What does "highest value per weight first" produce, and what is optimal?
A text contains the characters A, B, C, D with frequencies 1, 2, 3 and 4. Huffman coding builds its tree by repeatedly joining the two least frequent trees. How many bits does the encoded text need in total?
Which set of codes is prefix-free (no code is the beginning of another)?
Which two properties together suggest that dynamic programming is a good approach?
What does this program print?
public class FibCalls {
static int calls = 0;
static int fib(int n) {
calls++;
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
int r = fib(5);
System.out.println(r + " " + calls);
}
}
You climb a staircase taking either 1 or 3 steps at a time. With ways(0) = 1, how many different ordered sequences of moves reach step 7?
What does this code print?
int[] coins = {1, 3, 4};
int[] dp = new int[8];
for (int a = 1; a <= 7; a++) {
dp[a] = Integer.MAX_VALUE;
for (int c : coins)
if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
}
for (int v : dp) System.out.print(v + " ");
What does this code print?
int[] coins = {1, 2, 5};
int[] ways = new int[6];
ways[0] = 1;
for (int a = 1; a <= 5; a++)
for (int c : coins)
if (c <= a) ways[a] += ways[a - c];
System.out.println(ways[5]);
A 0/1 knapsack has capacity 7 and items (weight, value): (1, 1), (3, 4), (4, 5), (5, 7). What is the maximum total value?
For the knapsack in the previous question, K[i][c] is the best value using only the first i items with capacity c. What is K[3][5], i.e. items (1, 1), (3, 4), (4, 5) with capacity 5?
Which recurrence is correct for the 0/1 knapsack, when item i (weight wᵢ, value vᵢ) fits in capacity c?
The 0/1 knapsack DP runs in Θ(nW) time. Why is it called pseudo-polynomial rather than polynomial?
What is the length of the longest common subsequence of "PROGRAM" and "GRAMMAR"?
In the LCS table, dp[i][j] is the LCS length of the first i characters of x and the first j characters of y. If x.charAt(i - 1) != y.charAt(j - 1), what is dp[i][j]?
What is the length of the longest strictly increasing subsequence of {3, 10, 2, 1, 20, 4, 6, 7}?
What does this code print?
int[] a = {5, 1, 6, 2, 7, 3, 8};
int[] dp = new int[a.length];
for (int i = 0; i < a.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++)
if (a[j] < a[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
for (int v : dp) System.out.print(v + " ");
Which statement about top-down memoization and bottom-up tabulation is true?
What happens when fib(10) is called?
static Map<Integer, Long> memo = new HashMap<>();
static long fib(int n) {
if (n <= 1) return n;
long cached = memo.get(n);
if (memo.containsKey(n)) return cached;
long r = fib(n - 1) + fib(n - 2);
memo.put(n, r);
return r;
}
You only need the length of the LCS of strings of lengths m and n, not the subsequence itself. How much memory is really needed?
Prove, with an exchange argument, that choosing the activity with the earliest finish time first is safe for interval scheduling (maximising the number of non-overlapping activities).
Using the 0/1 knapsack table in this chapter's review (W = 7, items (1, 1), (3, 4), (4, 5), (5, 7)), explain step by step how to find which items give the value 9, and state the rule you apply at each row.
A robot starts at the top-left cell of an r × c grid of non-negative costs and may move only right or down to reach the bottom-right cell; it pays the cost of every cell it visits. Design a DP for the minimum total cost: define the state, the recurrence, the base cases, the fill order, and the time and space.
Compare top-down memoization and bottom-up tabulation: how each works, their time complexity, and one situation in which you would prefer each.
Write static int lis(int[] a) that returns the length of the longest strictly increasing subsequence of a in O(n²) time (0 for an empty array). For {3, 10, 2, 1, 20, 4, 6, 7} it returns 4.
Given non-negative amounts a[0..n-1] of money in houses along a street, a thief may not rob two adjacent houses. Write static int maxNonAdjacent(int[] a) that returns the largest total that can be robbed, in Θ(n) time and Θ(1) extra space. For {2, 7, 9, 3, 1} it returns 12 (2 + 9 + 1); for {5, 1, 1, 5} it returns 10.