AI summary by TwinMind
Problem Session 8
MIT OpenCourseWare
1h 34m 41s
Course Introduction and Dynamic Programming Overview
- First of two problem sessions covering dynamic programming in algorithms class
- Dynamic programming described as "meta-algorithm" or problem-solving approach rather than specific algorithm
- Follows SRTBOT template: Sub-problems, Relate, Topological order, Base case, Original problem, Time analysis
- Key concept: memoization to avoid redundant recursive computations (Fibonacci example)
- Two implementation approaches: recursive with memoization table vs. iterative bottom-up construction
Problem 1: Tim the Beaver's Weather Decisions
- Tim has n days until final exam, makes daily decisions based on temperature T
- Rules:
- Go outside: happiness increases by T
- Stay inside: happiness stays same (corrected from initial decrease)
- Constraint: cannot go outside more than 2 consecutive days
- Sub-problems: X(i) = maximum happiness from day i to day n
- Recursive cases:
- Case 1: Stay inside → X(i) = X(i+1)
- Case 2A: Go out today, stay in tomorrow → X(i) = T(i) + X(i+2)
- Case 2B: Go out today and tomorrow → X(i) = T(i) + T(i+1) + X(i+3)
- Base case: X(n) = max(0, T(n))
- Original problem: X(1)
- Time complexity: O(n) - n sub-problems, O(1) work each
- Additional consideration: reconstruct actual plan using decision tracking
Problem 2: File Edit Distance (Minix Operating System)
- Files are sequences of strings (lines), length ≤ K each
- Three operations on file A to transform to file B:
- Add line (expensive, cost = 1)
- Remove line (expensive, cost = 1)
- Swap adjacent lines (cheap, cost = 0)
- Goal: minimum number of non-swap operations
- Key insight: can only edit file A (not B)
- Sub-problems: X(i,j) = min work to convert A[i:] into B[j:]
- Recursive cases:
- Case 1: A[i] = B[j] → X(i,j) = X(i+1,j+1)
- Case 2: Delete A[i] → X(i,j) = 1 + X(i+1,j)
- Case 3: Insert line to match B[j] → X(i,j) = 1 + X(i,j+1)
- Case 4: Swap A[i] and A[i+1] if beneficial → X(i,j) = X(i+2,j+2)
- Swap only useful when A[i+1] = B[j] and A[i] = B[j+1]
- Base cases: X(n+1,j) = n+1-j, X(i,n+1) = n+1-i
- Time complexity: O(n²) - (n+1)² sub-problems, O(1) work each
- Runtime includes factor K for string comparisons
Problem 3: Saggy's Block Stacking
- Saggy has n blocks, each with dimensions (w_i, h_i, l_i)
- Has at least 3 of each block type, can rotate blocks freely
- Goal: maximum height tower with strict support condition
- Key observations:
- Always align shorter sides together for optimal support
- Each orientation can appear at most once due to strict support
- Only 3 orientations per block type matter
- Preprocessing:
- Sort block dimensions: w ≤ h ≤ l
- Create 3 orientations per block: (w,h,l), (w,l,h), (h,l,w)
- Sort lexicographically, remove duplicates
- Time: O(n log n)
- Sub-problems: X(i) = max height using block i and possibly blocks 1 to i-1
- Recursive relation: X(i) = v_i + max{X(j) : j < i and block j can support block i}
- Base case: X(1) = v_1
- Original: max over all i of X(i)
- Time complexity: O(n²) - n sub-problems, O(n) work per sub-problem
Problem 4: Princess Plum's Mushroom Collection
- Princess moves on n×n grid from upper-left to lower-right
- Grid squares contain: mushroom, tree (impassable), or empty
- Must take "quick path" = exactly 2n-1 squares (shortest possible)
- Goal: count paths achieving maximum mushroom collection
- Key insight: quick paths can only move down or right
- Two-phase approach:
- Phase 1: Compute K(i,j) = max mushrooms on quick path to position (i,j)
- Phase 2: Compute X(i,j) = number of quick paths to (i,j) with K(i,j) mushrooms
- Phase 1 recursion:
- If tree at (i,j): K(i,j) = -∞
- Else: K(i,j) = indicator(mushroom at i,j) + max(K(i-1,j), K(i,j-1))
- Phase 2 recursion:
- If tree at (i,j): X(i,j) = 0
- Else: X(i,j) = sum of X values from valid predecessor positions
- Valid predecessor: path + current mushroom = target mushroom count
- Base cases: K(1,1) = 0, X(1,1) = 1
- Time complexity: O(n²) for each phase
