Practice Exam

Forward Edges (remaining capacity):

sa	sb	ab	ac	bc	bd	cd	ct	dt
5	5	4	2	3	5	2	4	5

Reverse Edges (current flow that can be pushed back):

saR	sbR	abR	acR	bcR	bdR	cdR	ctR	dtR
5	3	0	5	3	0	2	6	2

Explanation:

• Forward edge weight = capacity - current_flow
• Example: sa has flow 5/10, so forward edge = 10 - 5 = 5
• Reverse edge weight = current_flow
• Example: sa has flow 5, so reverse edge sa_R = 5
• Edges with 0 current flow (ab, bd) have 0 reverse capacity

ANSWER: s → a → c → t

Explanation:

• Edmonds-Karp uses BFS, which finds the shortest path (fewest edges) first
• This path has length 3 (3 edges)
• All edges have available capacity in the residual graph:
• s → a: capacity 5 available
• a → c: capacity 2 available
• c → t: capacity 4 available
• Bottleneck = min(5, 2, 4) = 2
• Any other path of length 3 would also be acceptable for EK

ANSWER: s → b → c → d → t

Explanation:

• Ford-Fulkerson can find any valid augmenting path, not just shortest
• This path has length 4 (4 edges)
• Edmonds-Karp would NOT find this because it's longer than the shortest path (length 3)
• All edges have available capacity:
• s → b: capacity 5 available
• b → c: capacity 3 available
• c → d: capacity 2 available
• d → t: capacity 5 available
• Bottleneck = min(5, 3, 2, 5) = 2
• Other acceptable answers: s → a → b → c → t (length 4), s → a → b → c → d → t (length 5)

ANSWER: Maximum flow = 13

Augmenting paths used:

1. s → a → c → t with bottleneck = 2
2. s → b → c → d → t with bottleneck = 3
3. s → a → b → d → t with bottleneck = 4
4. s → b → d → t with bottleneck = 1
5. s → a → c → d → t with bottleneck = 2
6. s → b → c → t with bottleneck = 1

Verification:

• Flow out of s = 5 (to a) + 8 (to b) = 13
• Flow into t = 10 (from c) + 3 (from d) = 13
• Minimum cut = {sa, sb} with capacity 10 + 8 = 18, or {ct, dt} with capacity 10 + 7 = 17
• Actual minimum cut = 13 (verified by max-flow min-cut theorem)

ANSWER: Problem X can be solved in polynomial time.

Alternative acceptable answers:

• "X can be solved by a deterministic Turing machine in polynomial time"
• "There exists an algorithm that solves X in O(n^k) time for some constant k"
• "X is efficiently solvable"

ANSWER: Problem X can be verified in polynomial time.

Alternative acceptable answers:

• "X can be solved by a non-deterministic Turing machine in polynomial time"
• "A solution to X can be checked in polynomial time"
• "X can be solved in polynomial time via non-determinism"

Note: NP stands for "Nondeterministic Polynomial time," NOT "Non-Polynomial"

ANSWER: If a problem can be solved in polynomial time, it can also be verified in polynomial time.

Alternative acceptable answers:

• "Any deterministic polynomial algorithm can also verify in polynomial time"
• "Solving is at least as hard as verifying"
• "If you can solve it fast, you can check it fast"

Detailed explanation: If we have an algorithm that solves problem X in polynomial time, we can use that same algorithm to verify a proposed solution (just solve the problem ourselves and compare the result). Since solving takes polynomial time, verification also takes polynomial time, so X ∈ NP.

ANSWER: NP-complete problems are the hardest problems to solve, but easy to check if someone gives you an answer.

Alternative acceptable answers:

• "Problems that are extremely difficult to solve but solutions can be verified quickly"
• "The hardest problems where checking an answer is fast but finding it is slow"
• "Problems with no known fast solution, but you can verify a solution quickly"

Real-world analogy: Like a jigsaw puzzle - very hard to solve, but easy to check if it's completed correctly by just looking at it.

ANSWER: (1) Show the problem is in NP (verifiable in polynomial time), AND (2) Reduce a known NP-complete problem to it in polynomial time.

Breakdown of the two steps:

1. Show X is in NP: Demonstrate that given a candidate solution, you can verify it's correct in polynomial time
2. Show X is NP-hard: Take a known NP-complete problem Y and show how to transform any instance of Y into an instance of X in polynomial time (reduction Y ≤_p X)

Common mistakes to avoid:

• ❌ Reducing X to a known NP-complete problem (direction is backwards)
• ❌ Only showing X is in NP (missing the NP-hard part)
• ❌ Using exponential-time reduction (must be polynomial)

ANSWER: d) Polynomial time

Explanation: For a reduction to be useful in complexity analysis, the reduction itself must take polynomial time (or faster). This is critical because:

• If we reduce problem A to problem B in polynomial time, and B is solvable in polynomial time, then A is also solvable in polynomial time
• The reduction should not be the bottleneck - it should be faster than or comparable to solving the target problem
• For NP-completeness proofs, we specifically use polynomial-time reductions

Why other answers are wrong:

• a, b, c: Too restrictive - polynomial time is sufficient
• e, f: If reduction is exponential, it defeats the purpose of using it to analyze complexity

a) Base case [6 points]:

ANSWER: If the array has 1 or 2 elements, check directly. A single character is a palindrome of length 1. Two characters are a palindrome if they match, otherwise the longest palindrome is length 1.

b) Divide step [6 points]:

ANSWER: Divide the array A[1...n] into two halves: left = A[1...n/2] and right = A[n/2+1...n]

c) Conquer step [6 points]:

ANSWER: Recursively find the longest palindrome in the left half and in the right half. Let these be L_left and L_right.

d) Combine step [6 points]:

ANSWER: Find the longest palindrome that crosses the midpoint by expanding from the center outward (similar to merge in mergesort). Compare L_left, L_right, and L_cross, and return the longest one. The crossing palindrome check takes O(n) time.

e) Recurrence relation [6 points]:

ANSWER: T(n) = 2T(n/2) + O(n)

This solves to Θ(n log n) by Master Theorem Case 2 (a=2, b=2, log_ba = 1, f(n) = n = n¹)

ANSWER:

Arrange 9 elements into 3 groups of 3:

Group 1: [a, b, c]  → median = b
Group 2: [d, e, f]  → median = e
Group 3: [g, h, i]  → median = h

Medians: [b, e, h] → median-of-medians = e
                    

After sorting each group:

a ≤ b ≤ c
d ≤ e ≤ f
g ≤ h ≤ i
                    

And sorting the medians: b ≤ e ≤ h

Elements definitely ≤ e: {a, b, d, e} = 4 elements

• From Group 1: a, b (both ≤ b ≤ e)
• From Group 2: d, e (both ≤ e)

Elements definitely ≥ e: {e, f, h, i} = 4 elements

• From Group 2: e, f (both ≥ e)
• From Group 3: h, i (both ≥ h ≥ e)

Conclusion: e is greater than or equal to at least 4 out of 9 elements = 44.4% > 33% ✓

Note: We're unsure about c and g, but we don't need them to prove the 33% guarantee.

Recurrence: T(n) = 4T(n/2) + n²

Identify parameters:

• a = 4 (number of recursive calls)
• b = 2 (division factor)
• f(n) = n² (work outside recursion)
• log_ba = log₂4 = 2
• So n^log_ba = n²

Compare f(n) with n^log_ba:

• f(n) = n²
• n^log_ba = n²
• They are equal: f(n) = Θ(n²)

Which case applies: Case 2

Since f(n) = Θ(n^log_ba log^k n) where k = 0

Solution: T(n) = Θ(n² log n)

Intuition: The work at each level is n², and there are log n levels, so total work is n² × log n.

a) Base case(s) [8 points]:

ANSWER: Base case: n = 1

• For an array of size 1, binary search makes 1 comparison and terminates
• We claim T(1) ≤ c·1 for some constant c
• Choose c = 1, then T(1) = 1 ≤ 1·1 = 1 ✓

Alternative base case: n = 0

• Empty array requires 0 operations
• T(0) = 0 ≤ c·0 for any c ✓

b) Inductive hypothesis [6 points]:

ANSWER: Assume that for all k < n, T(k) ≤ c·k for some constant c ≥ 1

c) Inductive step [11 points]:

ANSWER: Need to prove: T(n) ≤ c·n

Binary search recurrence: T(n) = T(n/2) + O(1)

Let d be the constant for the O(1) work, so T(n) = T(n/2) + d

By inductive hypothesis: T(n/2) ≤ c·(n/2)

Therefore:

T(n) = T(n/2) + d
     ≤ c·(n/2) + d         (by inductive hypothesis)
     = cn/2 + d
     ≤ cn                  (if we choose c ≥ 2d)
                    

Conclusion: By choosing c ≥ max(1, 2d), we have T(n) ≤ cn for all n ≥ 0, proving binary search is O(n) ✓

Note: This is a weak bound - binary search is actually O(log n), but O(n) is technically correct since O(log n) ⊆ O(n).

a) T(n) = 2T(n/2) + n log n [5 points]

• a = 2, b = 2, f(n) = n log n
• log_ba = log₂2 = 1, so n^log_ba = n
• Compare f(n) = n log n with n¹ = n
• f(n) = n log n = Θ(n¹ log¹ n)
• Case 2 applies (with k=1)
• Answer: T(n) = Θ(n log² n)

b) T(n) = 3T(n/3) + n² [5 points]

• a = 3, b = 3, f(n) = n²
• log_ba = log₃3 = 1, so n^log_ba = n
• Compare f(n) = n² with n¹ = n
• f(n) = n² = Ω(n^1+ε) where ε = 1
• Check regularity: 3·f(n/3) = 3·(n/3)² = n²/3 ≤ (1/3)·n² for large n ✓
• Case 3 applies
• Answer: T(n) = Θ(n²)

c) T(n) = 8T(n/2) + n² [5 points]

• a = 8, b = 2, f(n) = n²
• log_ba = log₂8 = 3, so n^log_ba = n³
• Compare f(n) = n² with n³
• f(n) = n² = O(n^3-ε) where ε = 1
• Case 1 applies
• Answer: T(n) = Θ(n³)