diff --git a/writeup.md b/writeup.md
index 518f933..c2bb708 100644
--- a/writeup.md
+++ b/writeup.md
@@ -1,9 +1,389 @@
-# COMP182 Homework 8
+# COMP182 Homework 8: Recurrences and Dynamic Programming
 
 ## Student Responses
 
-<!-- Write your solutions below. Add sections for each problem as needed. -->
-<!-- Use proper mathematical notation where applicable. -->
+---
 
-[Your solutions here]
+## Problem 1.1: Tiling Recurrences [20 pts]
 
+### Part 1: 1 x n area
+
+Let T(n) denote the number of ways to tile a 1 x n strip using 1x1 and 1x2 tiles.
+
+**Reasoning:** Consider the rightmost cell (position n). There are two cases:
+
+- **Case 1:** Place a 1x1 tile at position n. The remaining area is a 1 x (n-1) strip, which can be tiled in T(n-1) ways.
+- **Case 2:** Place a 1x2 tile covering positions n-1 and n (horizontally). The remaining area is a 1 x (n-2) strip, which can be tiled in T(n-2) ways. This requires n >= 2.
+
+**Recurrence:**
+
+$$T(n) = T(n-1) + T(n-2), \quad n \geq 2$$
+
+**Boundary conditions:**
+
+- T(0) = 1 (the empty strip has exactly one tiling: do nothing)
+- T(1) = 1 (only one 1x1 tile)
+
+This is the Fibonacci recurrence. The first few values are: T(0)=1, T(1)=1, T(2)=2, T(3)=3, T(4)=5, ...
+
+### Part 2: 2 x n area
+
+Let T(n) denote the number of ways to tile a 2 x n grid using 1x1 and 1x2 tiles (which can be rotated to 2x1).
+
+**Reasoning:** We analyze column by column from right to left. Consider what tiles cover the two cells in the rightmost column n.
+
+The key insight is that horizontal 1x2 tiles can span two columns, creating partial states. We define an auxiliary quantity:
+
+- **T(n)** = number of ways to tile a complete 2 x n grid.
+- **U(n)** = number of ways to tile a 2 x n grid with one corner cell removed (say the top-right cell (1,n) is missing, so 2n - 1 cells remain). By vertical symmetry, the count is the same whether the top-right or bottom-right cell is removed.
+
+**Deriving T(n):** Consider what covers the cells in column n of the 2 x n grid:
+
+1. **Two 1x1 tiles** (one in each row): remaining is a complete 2 x (n-1) grid -> T(n-1) ways.
+2. **One vertical 1x2 tile** covering both cells of column n: remaining is a complete 2 x (n-1) grid -> T(n-1) ways.
+3. **Top cell covered by a horizontal 1x2 tile from column n-1, bottom cell is a 1x1 tile:** Cell (1,n-1) is also filled by the horizontal tile. Remaining is a 2 x (n-1) grid with cell (1,n-1) removed -> U(n-1) ways.
+4. **Bottom cell covered by a horizontal 1x2 tile from column n-1, top cell is a 1x1 tile:** By vertical symmetry, this also gives U(n-1) ways.
+5. **Both cells covered by horizontal 1x2 tiles from column n-1:** Both cells (1,n-1) and (2,n-1) are also filled. Remaining is a complete 2 x (n-2) grid -> T(n-2) ways.
+
+Therefore:
+
+$$T(n) = 2T(n-1) + 2U(n-1) + T(n-2)$$
+
+**Deriving U(n):** For a 2 x n grid with the top-right cell removed, only cell (2,n) needs to be covered in column n:
+
+1. **A 1x1 tile at (2,n):** remaining is a complete 2 x (n-1) grid -> T(n-1) ways.
+2. **A horizontal 1x2 tile from (2,n-1) to (2,n):** cell (2,n-1) is also filled. Remaining is a 2 x (n-1) grid with bottom-right removed. By vertical symmetry, this equals U(n-1) ways.
+
+Therefore:
+
+$$U(n) = T(n-1) + U(n-1)$$
+
+**Boundary conditions:**
+
+- T(0) = 1 (empty grid, one tiling)
+- T(1) = 2 (two 1x1 tiles, or one vertical 1x2 tile)
+- U(1) = 1 (one cell remains, covered by one 1x1 tile)
+
+**Verification:**
+
+- U(2) = T(1) + U(1) = 2 + 1 = 3
+- T(2) = 2T(1) + 2U(1) + T(0) = 4 + 2 + 1 = 7
+
+We can verify T(2) = 7 by enumeration on a 2x2 grid:
+- All four 1x1 tiles: 1 way
+- One 1x2 tile + two 1x1 tiles: the 1x2 can be vertical in column 1, vertical in column 2, horizontal in row 1, or horizontal in row 2 -> 4 ways
+- Two 1x2 tiles: both vertical or both horizontal -> 2 ways
+- Total: 1 + 4 + 2 = 7. Confirmed.
+
+**Collapsed single recurrence:** By eliminating U, we can show:
+
+$$T(n) = 3T(n-1) + T(n-2) - T(n-3), \quad n \geq 3$$
+
+with T(0) = 1, T(1) = 2, T(2) = 7.
+
+*Derivation:* From U(n) = T(n-1) + U(n-1), we get U(n-1) - U(n-2) = T(n-2). Subtracting the recurrence for T(n-1) from T(n):
+
+T(n) - T(n-1) = 2(T(n-1) - T(n-2)) + 2(U(n-1) - U(n-2)) + (T(n-2) - T(n-3))
+= 2(T(n-1) - T(n-2)) + 2T(n-2) + T(n-2) - T(n-3)
+= 2T(n-1) + T(n-2) - T(n-3)
+
+So T(n) = 3T(n-1) + T(n-2) - T(n-3).
+
+The first few values: T(0)=1, T(1)=2, T(2)=7, T(3)=22, T(4)=71, ...
+
+---
+
+## Problem 1.2: Paths in a Graph [10 pts]
+
+**Graph:** G = (V, E) where V = {1,2,3,4,5} and E = {{1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {3,4}, {4,5}, {5,2}}.
+
+**Adjacency list:**
+- Node 1: neighbors {2, 3, 4, 5} (degree 4)
+- Node 2: neighbors {1, 3, 5} (degree 3)
+- Node 3: neighbors {1, 2, 4} (degree 3)
+- Node 4: neighbors {1, 3, 5} (degree 3)
+- Node 5: neighbors {1, 2, 4} (degree 3)
+
+We count walks of length n starting at node 1 (a walk of length n traverses n edges, visiting n+1 nodes with possible repeats).
+
+Let P(n) = total number of walks of length n starting at node 1.
+
+**Exploiting symmetry:** Observe that nodes 2 and 4 have identical neighborhoods ({1, 3, 5}), and nodes 3 and 5 have identical neighborhoods ({1, 2, 4}). Define:
+
+- a(n) = number of walks of length n from node 1 to node 1
+- b(n) = number of walks of length n from node 1 to node 2 (= same as to node 4, by symmetry)
+- c(n) = number of walks of length n from node 1 to node 3 (= same as to node 5, by symmetry)
+
+Then P(n) = a(n) + 2b(n) + 2c(n).
+
+**System of recurrences** (from the adjacency structure):
+
+- a(n) = 2b(n-1) + 2c(n-1)    [node 1's neighbors are 2, 3, 4, 5]
+- b(n) = a(n-1) + 2c(n-1)      [node 2's neighbors are 1, 3, 5; using c for nodes 3 and 5]
+- c(n) = a(n-1) + 2b(n-1)      [node 3's neighbors are 1, 2, 4; using b for nodes 2 and 4]
+
+**Boundary conditions:** a(0) = 1, b(0) = 0, c(0) = 0 (a walk of length 0 from node 1 stays at node 1).
+
+**Simplification:** Since b(0) = c(0) and b(n) - c(n) = 2c(n-1) - 2b(n-1) = -2(b(n-1) - c(n-1)), we get b(n) - c(n) = (-2)^n(b(0) - c(0)) = 0. Therefore **b(n) = c(n) for all n >= 0**.
+
+With b(n) = c(n), the system simplifies to:
+
+- a(n) = 4b(n-1)
+- b(n) = a(n-1) + 2b(n-1) = 4b(n-2) + 2b(n-1)
+
+So b satisfies: **b(n) = 2b(n-1) + 4b(n-2)**, with b(0) = 0, b(1) = 1.
+
+And **P(n) = a(n) + 4b(n) = 4b(n-1) + 4b(n) = 4(b(n) + b(n-1))**.
+
+**Single recurrence for P(n):** Since b(n) satisfies b(n) = 2b(n-1) + 4b(n-2), and P(n) is a linear combination of terms involving b, P satisfies the same characteristic equation:
+
+$$P(n) = 2P(n-1) + 4P(n-2), \quad n \geq 2$$
+
+**Boundary conditions:** P(0) = 1, P(1) = 4.
+
+**Verification:**
+
+- P(0) = 1 (the trivial walk staying at node 1). Correct.
+- P(1) = 4 (from node 1, we can walk to 2, 3, 4, or 5). Correct.
+- P(2) = 2(4) + 4(1) = 12. Check: from node 1, go to any of 4 neighbors; from each neighbor, 3 edges lead out. Total = 4 x 3 = 12. Correct.
+- P(3) = 2(12) + 4(4) = 40.
+
+---
+
+## Problem 1.3: Constrained Functions [20 pts]
+
+**Definition:** F = {f : {1,...,n} -> {0,1,2} : for all 1 <= i <= n-1, f(i) + f(i+1) != 4}.
+
+The only pair (a,b) in {0,1,2}^2 with a + b = 4 is (2,2). So the constraint is: **no two consecutive positions can both have value 2.**
+
+### Part (a): Recurrence for |F|
+
+Let T(n) = |F|.
+
+**Conditioning on the last value:** Partition F based on f(n):
+
+- **f(n) in {0, 1}:** The constraint f(n-1) + f(n) != 4 is automatically satisfied (since max is 2 + 1 = 3 < 4). So f restricted to {1,...,n-1} can be any function in F_{n-1}. There are 2 choices for f(n), giving 2 * T(n-1) functions.
+
+- **f(n) = 2:** The constraint requires f(n-1) != 2 (otherwise f(n-1) + f(n) = 4). The number of valid functions on {1,...,n-1} with f(n-1) in {0,1} equals the number of valid functions on {1,...,n-1} with f(n-1) != 2. Call this p(n-1). Since p(n-1) counts functions where the last value is 0 or 1, and by the same argument as above, p(n) = 2 * T(n-1). So p(n-1) = 2 * T(n-2).
+
+This gives:
+
+$$T(n) = 2T(n-1) + 2T(n-2), \quad n \geq 2$$
+
+**Boundary conditions:**
+
+- T(0) = 1 (the empty function vacuously satisfies the constraint)
+- T(1) = 3 (f(1) can be 0, 1, or 2)
+
+**Verification:**
+
+- T(2) = 2(3) + 2(1) = 8. Check: total functions = 3^2 = 9; the only forbidden one is f(1)=2, f(2)=2. So |F| = 9 - 1 = 8. Correct.
+- T(3) = 2(8) + 2(3) = 22. Check: total = 27; bad functions (those containing "2,2" consecutively): {f(1)=f(2)=2} gives 3 functions, {f(2)=f(3)=2} gives 3 functions, minus {f(1)=f(2)=f(3)=2} gives 1 function. Bad = 3 + 3 - 1 = 5. So |F| = 27 - 5 = 22. Correct.
+
+### Part (b): Explicit Formula
+
+The recurrence is T(n) = 2T(n-1) + 2T(n-2).
+
+**Characteristic equation:** x^2 - 2x - 2 = 0
+
+$$x = \frac{2 \pm \sqrt{4 + 8}}{2} = \frac{2 \pm 2\sqrt{3}}{2} = 1 \pm \sqrt{3}$$
+
+**General solution:** T(n) = A(1 + sqrt(3))^n + B(1 - sqrt(3))^n.
+
+**Applying boundary conditions:**
+
+From T(0) = 1:
+A + B = 1   ... (i)
+
+From T(1) = 3:
+A(1 + sqrt(3)) + B(1 - sqrt(3)) = 3
+A + A*sqrt(3) + B - B*sqrt(3) = 3
+(A + B) + sqrt(3)(A - B) = 3
+1 + sqrt(3)(A - B) = 3
+A - B = 2/sqrt(3) = 2*sqrt(3)/3   ... (ii)
+
+From (i) and (ii):
+A = (1 + 2*sqrt(3)/3) / 2 = (3 + 2*sqrt(3)) / 6
+B = (1 - 2*sqrt(3)/3) / 2 = (3 - 2*sqrt(3)) / 6
+
+**Explicit formula:**
+
+$$|F_n| = \frac{3 + 2\sqrt{3}}{6} \cdot (1 + \sqrt{3})^n + \frac{3 - 2\sqrt{3}}{6} \cdot (1 - \sqrt{3})^n$$
+
+**Verification:**
+
+- n = 0: (3 + 2*sqrt(3) + 3 - 2*sqrt(3)) / 6 = 6/6 = 1. Correct.
+- n = 1: [(3 + 2*sqrt(3))(1 + sqrt(3)) + (3 - 2*sqrt(3))(1 - sqrt(3))] / 6
+  = [(3 + 3*sqrt(3) + 2*sqrt(3) + 6) + (3 - 3*sqrt(3) - 2*sqrt(3) + 6)] / 6
+  = [(9 + 5*sqrt(3)) + (9 - 5*sqrt(3))] / 6
+  = 18/6 = 3. Correct.
+- n = 2: The formula gives T(2) = 2(3) + 2(1) = 8. Correct.
+
+---
+
+## Problem 2.1: Seam Carving [25 pts]
+
+### Part (a): Exponential number of seams
+
+A seam is a sequence of pixels s = ((1, j_1), (2, j_2), ..., (m, j_m)) where |j_{i+1} - j_i| <= 1 for all i, i.e., consecutive pixels in the seam are in the same or adjacent columns.
+
+**Claim:** The number of seams is at least 2^m, which is exponential in m.
+
+**Proof:** Since n > 1, both columns 1 and 2 exist. Consider only seams restricted to columns {1, 2}. At each row, the seam pixel is in column 1 or column 2. The adjacency condition |j_{i+1} - j_i| <= 1 is always satisfied when j_i, j_{i+1} in {1, 2}, since |1-1| = 0, |2-2| = 0, |1-2| = 1, |2-1| = 1 are all <= 1.
+
+Therefore, at each of the m rows, we independently choose column 1 or column 2, giving exactly **2^m** valid seams using only columns 1 and 2.
+
+Since the total number of seams includes all seams (not just those restricted to {1,2}), we have:
+
+Number of seams >= 2^m
+
+This is exponential in m, as required. QED.
+
+### Part (b): DP algorithm for minimum-disruption seam
+
+**Subproblem:** Let D[i, j] = minimum total disruption of a seam from row 1 to row i, with the pixel in row i being in column j.
+
+**Recurrence:** For 2 <= i <= m:
+
+$$D[i, j] = d[i, j] + \min(D[i-1, j-1], \; D[i-1, j], \; D[i-1, j+1])$$
+
+where D[i-1, j-1] is treated as +infinity if j-1 < 1, and D[i-1, j+1] is treated as +infinity if j+1 > n.
+
+**Boundary condition:** For the first row:
+
+$$D[1, j] = d[1, j], \quad 1 \leq j \leq n$$
+
+**Optimal value:** The minimum disruption seam has cost:
+
+$$\text{OPT} = \min_{1 \leq j \leq n} D[m, j]$$
+
+**Reconstruction:** To recover the actual seam, maintain a predecessor array P[i, j] that stores which column in row i-1 achieved the minimum for D[i, j]:
+
+$$P[i, j] = \arg\min_{k \in \{j-1, j, j+1\} \cap \{1,...,n\}} D[i-1, k]$$
+
+After finding j* = argmin_j D[m, j], trace back: j_m = j*, j_{m-1} = P[m, j*], j_{m-2} = P[m-1, j_{m-1}], etc.
+
+**Algorithm:**
+
+```
+FIND-MIN-SEAM(d, m, n):
+  // Base case
+  for j = 1 to n:
+    D[1, j] = d[1, j]
+
+  // Fill table row by row
+  for i = 2 to m:
+    for j = 1 to n:
+      best = D[i-1, j]
+      P[i, j] = j
+      if j > 1 and D[i-1, j-1] < best:
+        best = D[i-1, j-1]
+        P[i, j] = j-1
+      if j < n and D[i-1, j+1] < best:
+        best = D[i-1, j+1]
+        P[i, j] = j+1
+      D[i, j] = d[i, j] + best
+
+  // Find optimal endpoint
+  j* = argmin_{j=1..n} D[m, j]
+  OPT = D[m, j*]
+
+  // Trace back the seam
+  seam[m] = j*
+  for i = m downto 2:
+    seam[i-1] = P[i, seam[i]]
+
+  return OPT, seam
+```
+
+**Time complexity:** O(mn) — we fill an m x n table, and each entry takes O(1) time (looking at at most 3 neighbors).
+
+**Space complexity:** O(mn) for the D and P tables. (Can be reduced to O(n) for the value alone by keeping only two rows, but O(mn) is needed to reconstruct the seam.)
+
+---
+
+## Problem 2.2: Optimal String Breaking [25 pts]
+
+**Setup:** We have a string S of n characters and m break points L[1], ..., L[m] (in sorted order). Breaking a string of length l costs l time units. We want to find the order of breaks that minimizes total cost.
+
+**Key insight:** After sorting the break points, introduce sentinel values. Let b_0 = 0 and b_{m+1} = n, and let b_1 < b_2 < ... < b_m be the sorted break points. These m+2 boundary points define m+1 final pieces.
+
+**Subproblem definition:** Let C[i, j] = minimum cost to make all required breaks in the substring spanning from position b_i to position b_j (i.e., the substring of length b_j - b_i), for 0 <= i < j <= m+1.
+
+The breaks that must be made within this substring are at positions b_{i+1}, b_{i+2}, ..., b_{j-1} (the break points strictly between the boundaries b_i and b_j).
+
+**Recurrence:** For j - i >= 2 (at least one break point exists between b_i and b_j):
+
+$$C[i, j] = (b_j - b_i) + \min_{i < k < j} \big(C[i, k] + C[k, j]\big)$$
+
+The first term (b_j - b_i) is the cost of the first break in this substring (it costs the length of the current piece to break it). We choose to break at some b_k, splitting the substring [b_i, b_j] into [b_i, b_k] and [b_k, b_j], and then recursively make all remaining breaks in each piece.
+
+**Boundary conditions:** For j = i + 1 (no break points between b_i and b_j):
+
+$$C[i, i+1] = 0, \quad 0 \leq i \leq m$$
+
+**Optimal value:** The answer is C[0, m+1].
+
+**Reconstruction:** Maintain a table R[i, j] that stores the optimal first break point:
+
+$$R[i, j] = \arg\min_{i < k < j} \big(C[i, k] + C[k, j]\big)$$
+
+After computing C[0, m+1], reconstruct the sequence of breaks recursively: break first at b_{R[0,m+1]}, then recursively reconstruct the left and right subproblems.
+
+**Algorithm:**
+
+```
+OPTIMAL-BREAKS(n, L[1..m]):
+  Sort L in ascending order
+  Set b[0] = 0, b[1..m] = L[1..m], b[m+1] = n
+
+  // Base cases
+  for i = 0 to m:
+    C[i, i+1] = 0
+
+  // Fill table by increasing gap size
+  for gap = 2 to m+1:
+    for i = 0 to m+1-gap:
+      j = i + gap
+      C[i, j] = infinity
+      for k = i+1 to j-1:
+        cost = C[i, k] + C[k, j]
+        if cost < C[i, j]:
+          C[i, j] = cost
+          R[i, j] = k
+      C[i, j] = C[i, j] + (b[j] - b[i])
+
+  return C[0, m+1]
+
+PRINT-BREAKS(R, b, i, j):
+  if j - i <= 1: return
+  k = R[i, j]
+  print "Break at position b[k]"
+  PRINT-BREAKS(R, b, i, k)
+  PRINT-BREAKS(R, b, k, j)
+```
+
+**Verification with the example:** n = 20, breaks at positions 2, 8, 10. So b = [0, 2, 8, 10, 20].
+
+Base cases: C[0,1] = C[1,2] = C[2,3] = C[3,4] = 0.
+
+Gap = 2:
+- C[0,2] = (b_2 - b_0) + C[0,1] + C[1,2] = 8 + 0 + 0 = 8 (break at b_1=2)
+- C[1,3] = (b_3 - b_1) + C[1,2] + C[2,3] = 8 + 0 + 0 = 8 (break at b_2=8)
+- C[2,4] = (b_4 - b_2) + C[2,3] + C[3,4] = 12 + 0 + 0 = 12 (break at b_3=10)
+
+Gap = 3:
+- C[0,3] = (b_3 - b_0) + min(C[0,1]+C[1,3], C[0,2]+C[2,3]) = 10 + min(0+8, 8+0) = 10 + 8 = 18
+- C[1,4] = (b_4 - b_1) + min(C[1,2]+C[2,4], C[1,3]+C[3,4]) = 18 + min(0+12, 8+0) = 18 + 8 = 26
+
+Gap = 4:
+- C[0,4] = (b_4 - b_0) + min(C[0,1]+C[1,4], C[0,2]+C[2,4], C[0,3]+C[3,4])
+  = 20 + min(0+26, 8+12, 18+0) = 20 + min(26, 20, 18) = 20 + 18 = **38**
+
+The optimal cost is 38, achieved by first breaking at position 10 (k=3 gives C[0,3]+C[3,4] = 18+0), then breaking [0,10] at position 8 or 2 (both achieve cost 18). This matches the right-to-left order from the problem: break at 10 (cost 20), break at 8 (cost 10), break at 2 (cost 8), total = 38.
+
+**Time complexity:** O(m^3) — there are O(m^2) subproblems (pairs (i,j) with 0 <= i < j <= m+1), and each requires O(m) time to try all possible first break points k.
+
+**Space complexity:** O(m^2) for the C and R tables.
+
+This is polynomial in m (the number of break points), and since m <= n-1, it is also polynomial in n.