CS 6515 — Exam 1 Practice

Dynamic Programming & Divide and Conquer | 180 min | No notes, no calculator

00:00:00

Part A: Multiple Choice / Short Answer (20 points)

Select the best answer. Some questions may have multiple correct answers.

Question 1 (2 pts)

What is the runtime of the Chain Matrix Multiplication DP algorithm for multiplying a chain of n matrices?

O(n²)
O(n² log n)
O(n³)
O(2ⁿ)

Question 2 (2 pts)

In the Knapsack without repetition problem, which of the following correctly describes the subproblem?

K(w) = max value achievable with capacity w using any items
K(i, w) = max value achievable using items 1..i with capacity w
K(i) = max value achievable using exactly i items
K(i, w) = max value achievable using items i..n with capacity w

Question 3 (2 pts)

The Karatsuba algorithm for multiplying two n-bit integers makes how many recursive calls on inputs of size n/2?

Question 4 (2 pts)

Which of the following recurrences does the Median of Medians (FastSelect) algorithm satisfy?

T(n) = 2T(n/2) + O(n)
T(n) = T(n/5) + T(7n/10) + O(n)
T(n) = T(n/3) + T(2n/3) + O(n)
T(n) = T(n/2) + O(1)

Question 5 (2 pts)

Using the Master Theorem on T(n) = 4T(n/2) + O(n), what is the runtime?

O(n log n)
O(n²)
O(n² log n)
O(n³)

Question 6 (2 pts)

Why does the Median of Medians algorithm use groups of 5 instead of groups of 3?

Groups of 3 give O(n log n) because the recursive fractions sum to exactly 1
Groups of 3 give O(n²) because the pivot is not guaranteed to be good
Groups of 5 use less memory than groups of 3
Groups of 3 require sorting which adds O(n log n) overhead

Question 7 (2 pts)

In the Chain Matrix Multiplication problem, what do the subproblems represent?

Prefixes: optimal cost to multiply matrices A₁ through Aᵢ
Substrings: optimal cost to multiply matrices Aᵢ through Aⱼ
Suffixes: optimal cost to multiply matrices Aᵢ through Aₙ
Individual pairs: cost to multiply Aᵢ × Aⱼ

Question 8 (2 pts)

What is the runtime of the naive divide-and-conquer algorithm for integer multiplication (before the Karatsuba improvement)?

O(n log n)
O(n^1.585)
O(n²)
O(n³)

Question 9 (2 pts)

For the LCS (Longest Common Subsequence) problem on strings of length m and n, what is the size of the DP table?

O(m + n)
O(m × n)
O(max(m, n))
O(m × n × (m+n))

Question 10 (2 pts)

Which of the following is TRUE about D&C solutions in this course? (Select all that apply)

You may use pseudocode to describe your algorithm
Your solution must beat the brute force runtime
You may use Binary Search, Merge Sort, FastSelect, or FastMultiply as black boxes
If you modify a black-box algorithm, you must describe the modification and account for its runtime impact
The Master Theorem will be provided on the exam

Part B: Dynamic Programming (10 points)

Define subproblem, recurrence, base case, runtime, and how to extract the answer.

Problem B1 (10 pts)

You are given a sequence of n words with lengths ℓ₁, ℓ₂, ..., ℓₙ. You want to arrange them into lines, where each line can hold at most L characters (including exactly one space between adjacent words on the same line). The penalty for a line is (L − total characters used on that line)³ — i.e., the cube of the leftover space. The last line has zero penalty regardless of leftover space.

Design a DP algorithm to partition the words into lines minimizing the total penalty.

Required parts: (1) Define table entries in words. (2) Recurrence with base case. (3a) Number of subproblems. (3b) Runtime to fill table. (3c) How return is extracted. (3d) Runtime of extraction.

Part C: Divide and Conquer (20 points)

Describe your algorithm in plain English (no pseudocode). Justify correctness. Analyze runtime.

Problem C1 (20 pts)

You are given a sorted array A of n distinct integers. An element A[i] is called a fixed point if A[i] = i (using 1-based indexing). Design an O(log n) algorithm to find a fixed point if one exists, or report that none exists.

Faster (and correct) solutions are worth more credit.

⚠️ Remember: Describe in plain English. No pseudocode. Must include: (a) Algorithm, (b) Justification of Correctness, (c) Runtime Analysis.

Problem C2 (20 pts — BONUS PRACTICE)

You are given an unsorted array A of n distinct integers and a value T. Design a divide-and-conquer algorithm that determines whether there exist two elements in A that sum to T. Your algorithm must run in O(n log n) time.

Faster (and correct) solutions are worth more credit.

⚠️ Remember: Describe in plain English. No pseudocode. Must include: (a) Algorithm, (b) Justification of Correctness, (c) Runtime Analysis.