"Algorithm Design: Greedy, Divide & Conquer, Dynamic Programming" — Practice

Question 1

Which technique is appropriate when subproblems overlap and the problem has optimal substructure?

Accepted Answer

C

Question 2

For which problem does a greedy value-to-weight ratio strategy give the optimal answer?

Accepted Answer

B

Question 3

What is the time complexity of the standard dynamic program for the longest common subsequence of strings of lengths m and n?

Accepted Answer

B

Question 4

Give a coin system and an amount for which the greedy algorithm does not produce the minimum number of coins, and explain the failure.

Accepted Answer

Take denominations 1, 3 and 4, and an amount of 6.

Greedy takes the largest coin not exceeding the remainder at each step. It takes 4, leaving 2. It then takes 1, leaving 1, and takes 1 again.

The greedy answer is three coins: 4, 1, 1.

The optimal answer is two coins: 3 and 3.

The failure is structural. Taking the 4 consumed value in a way that left a remainder of 2, which the available denominations cannot cover in fewer than two coins. Choosing the smaller coin 3 first leaves a remainder of 3, which one further coin covers exactly.

This is the same shape as the 0/1 knapsack failure: a locally attractive choice consumes a resource in a way that forecloses a better global arrangement.

The correct algorithm is a dynamic program over amounts, computing the minimum coins for every value from 0 up to the target, at cost O(nA) for n denominations and amount A.

Why greedy works for real currency is that denominations such as 1, 2, 5, 10, 20, 50 are deliberately designed to be canonical, meaning greedy is provably optimal for them. That is a property of the specific system, not of the algorithm.

Question 5

Solve the 0/1 knapsack instance with capacity 8 and items of (weight, value) (3, 30), (4, 50), (5, 60).

Accepted Answer

Build the table V[i][w] over items considered and capacity, with V[0][w] = 0 for all w.

Item 1, weight 3, value 30. For w at least 3 the value is 30, otherwise 0.
Row 1: w = 0 to 2 gives 0; w = 3 to 8 gives 30.

Item 2, weight 4, value 50. At w = 4, skip gives 30 and take gives 50 plus V[1][0] = 50, so 50. At w = 5 and 6, take gives 50 plus V[1][1 or 2] = 50, so 50. At w = 7, skip gives 30 and take gives 50 plus V[1][3] = 80, so 80. At w = 8, take gives 50 plus V[1][4] = 80, so 80.
Row 2: 0, 0, 0, 30, 50, 50, 50, 80, 80.

Item 3, weight 5, value 60. At w = 5, skip gives 50 and take gives 60 plus V[2][0] = 60, so 60. At w = 6, take gives 60 plus V[2][1] = 60, so 60. At w = 7, skip gives 80 and take gives 60 plus V[2][2] = 60, so 80. At w = 8, skip gives 80 and take gives 60 plus V[2][3] = 90, so 90.
Row 3: 0, 0, 0, 30, 50, 60, 60, 80, 90.

The maximum value is 90, achieved by taking items 1 and 3 with total weight 8.

Note what greedy by ratio would have done. The ratios are 10, 12.5 and 12, so it takes item 2 first at weight 4, then item 1 at weight 3 for a total weight of 7 and value 80, and item 3 no longer fits. Greedy gives 80 against the optimal 90, which is exactly the failure this instance was built to show.

Question 6

Naive matrix multiplication uses 8 recursive multiplications of half-sized matrices; Strassen uses 7. Derive both exponents and state where the saving comes from.

Accepted Answer

Both algorithms split each n by n matrix into four blocks of size n over 2, so each recursive call operates on a problem of half the dimension.

The naive recurrence is T(n) = 8 T(n/2) plus O(n squared), since combining the block products requires a constant number of matrix additions, each costing n squared.

Apply the master theorem. Here a = 8 and b = 2, so the critical exponent is log base 2 of 8 = 3, and the critical function is n cubed. The additive term n squared is polynomially smaller, so case 1 applies and T(n) = Theta(n cubed).

Strassen's recurrence is T(n) = 7 T(n/2) plus O(n squared). The critical exponent becomes log base 2 of 7, which is approximately 2.807, and the additive n squared is again polynomially smaller, so case 1 gives T(n) = Theta(n to the 2.807).

The saving comes entirely from reducing the branching factor from 8 to 7. Strassen achieves this by computing seven cleverly chosen products of sums of blocks, then recombining them with additions and subtractions to recover the four output blocks.

The cost is more additions: naive uses 4 and Strassen uses 18. Additions are Theta(n squared), which sits below the critical function, so they inflate the constant without touching the exponent. That asymmetry between a and f is precisely why the trade is worthwhile asymptotically, and why Strassen nonetheless loses to the naive method for small matrices where the constant dominates.

Question 7

Prove that selecting activities by earliest finishing time is optimal, and show why earliest start time fails.

Accepted Answer

Let the activities be sorted by finishing time and let a1 be the one finishing earliest. Let S be any optimal solution, containing k activities.

If S already contains a1, nothing needs proving for the first step.

Otherwise let b be the activity in S that finishes earliest. Since a1 finishes no later than b, replacing b with a1 in S cannot create a conflict: every other activity in S starts after b finishes, and therefore after a1 finishes as well.

The modified set is still feasible and still has k activities, so it is also optimal. This shows that some optimal solution contains a1, which is exactly the greedy choice property.

After selecting a1, the remaining problem is to select the maximum number of activities starting after a1 finishes, which is a smaller instance of the same problem. That is optimal substructure, and induction completes the proof.

For earliest start time, a counterexample suffices. Take activities (0, 10), (1, 2), (3, 4) and (5, 6).

Sorting by start time selects (0, 10) first, which overlaps all three others, so the answer is one activity.

Sorting by finishing time selects (1, 2), then (3, 4), then (5, 6), giving three.

The failure is that an early start says nothing about how long the activity occupies the resource, so a long activity can block many short ones. Earliest finish is the right rule precisely because finishing early is what leaves room for others, and that is the quantity the exchange argument turns on.

Shortest duration also fails: with activities (0, 5), (4, 6) and (5, 10), the shortest is (4, 6), which blocks both others and gives one instead of two.

Question 8

Explain why the O(nW) knapsack algorithm does not prove that knapsack is in P, and give a concrete instance where it is intractable.

Accepted Answer

A polynomial-time algorithm must run in time polynomial in the length of the input, measured in bits, since that is how input size is defined in complexity theory.

The input to knapsack consists of n items and a capacity W. Listing n items takes space proportional to n, so a factor of n in the running time is genuinely polynomial in the input length.

But W is a single number written in binary, occupying only log base 2 of W bits. A capacity of one billion fits in 30 bits.

So the running time O(nW) is O(n times 2 to the power log W), which is exponential in the number of bits used to encode W. Adding one bit to W doubles the running time, and doubling the bits squares it.

A concrete intractable instance: take n = 50 items and W = 2 to the 40, which is about one trillion. The input is 50 item descriptions plus a 40-bit number, easily under a kilobyte. The table has 50 times 2 to the 40 entries, which is roughly 5 times 10 to the 13 cells — beyond any feasible memory or time budget.

The term pseudo-polynomial names exactly this situation: polynomial in the numeric value of an input, exponential in its encoded length.

The consequence for complexity theory is that knapsack remains NP-complete, and the existence of this algorithm does not contradict that. What it does show is that knapsack is not strongly NP-complete: instances with small numeric values are tractable, which distinguishes it from problems that remain hard even when all numbers are small.

Question 9

For the longest increasing subsequence problem, describe the O(n squared) dynamic program and the O(n log n) improvement, and explain what the faster version gives up.

Accepted Answer

The quadratic dynamic program defines L[i] as the length of the longest increasing subsequence ending exactly at position i.

The recurrence takes the best over all earlier positions with a smaller value: L[i] = 1 plus the maximum of L[j] over all j less than i with a[j] less than a[i], or 1 if no such j exists.

There are n states and each scans up to n predecessors, giving O(n squared). The answer is the maximum over all L[i], and the subsequence itself is recovered by storing a predecessor pointer with each entry.

The faster version abandons that state definition entirely. It maintains an array in which position k holds the smallest possible tail value of any increasing subsequence of length k plus one.

For each element, binary search finds the first tail value that is at least the element, and overwrites it. If the element exceeds every tail, it extends the array by one.

The array is always sorted, which is what makes the binary search valid, and its final length is the answer. Each of n elements costs a binary search over at most n positions, giving O(n log n).

What the faster version gives up is the subsequence itself, at least directly. The tails array does not hold an actual subsequence — its entries can come from non-contiguous and even incompatible positions, so reading it off as an answer is wrong. Recovering the actual subsequence requires additionally storing, for each element, the index it was placed at and a pointer to the element that preceded it, which restores the reconstruction at the cost of O(n) extra space.

The quadratic version reconstructs naturally because its state is genuinely about subsequences ending at a position, and that is the trade.

Practice — "Algorithm Design: Greedy, Divide & Conquer, Dynamic Programming"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities