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

TwinMind

Get summaries like this for your own meetings

TwinMind takes notes in the background during meetings, lectures, and calls, then writes the summary for you.

Free plan to get started

No bot joins your calls

Phone, desktop & Chrome apps

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome