diff --git a/writeup.md b/writeup.md
index 518f933..d361d64 100644
--- a/writeup.md
+++ b/writeup.md
@@ -1,9 +1,336 @@
-# COMP182 Homework 8
+# COMP182 Homework 8 Solutions
 
-## Student Responses
+## Problem 1.1: Tiling Problems
 
-<!-- Write your solutions below. Add sections for each problem as needed. -->
-<!-- Use proper mathematical notation where applicable. -->
+### Part 1.1a: Tiling a 1 × n Area
 
-[Your solutions here]
+For a 1×n rectangular strip with 1×1 tiles and 1×2 tiles (which can be rotated):
+- In a 1×n strip, a 1×2 tile must be placed horizontally (2 wide, 1 tall) to fit
+- The available tiles are: 1×1 and 2×1 (rotated 1×2)
 
+**Recurrence:**
+Let f(n) = number of ways to cover a 1×n strip.
+
+We can fill the rightmost end of the strip in two ways:
+1. Place a 1×1 tile at position n, leaving a 1×(n-1) strip: f(n-1) ways
+2. Place a 2×1 tile at positions (n-1, n), leaving a 1×(n-2) strip: f(n-2) ways
+
+**Recurrence Relation:**
+```
+f(n) = f(n-1) + f(n-2)    for n ≥ 2
+```
+
+**Boundary Conditions:**
+```
+f(0) = 1  (one way to tile empty strip: use no tiles)
+f(1) = 1  (one way to tile 1×1 strip: use one 1×1 tile)
+```
+
+This is the Fibonacci recurrence.
+
+---
+
+### Part 1.1b: Tiling a 2 × n Area
+
+For a 2×n rectangular grid with 1×1, 1×2 (1 wide, 2 tall), and 2×1 (2 wide, 1 tall) tiles:
+
+To derive the recurrence, I'll track states at the boundary between filled and unfilled columns.
+
+Let:
+- f(n, 0) = ways to tile n columns such that no tiles extend beyond column n
+- f(n, 1) = ways to tile n columns with top row extending beyond (bottom complete)
+- f(n, 2) = ways to tile n columns with bottom row extending beyond (top complete)
+- f(n, 3) = ways to tile n columns with both rows extending beyond
+
+Transitions from a fully complete boundary (state 0):
+- Place two 1×1 tiles in column n+1: stays in state 0
+- Place one 1×2 tile in column n+1: stays in state 0
+- Place 2×1 tile in top row extending to n+1: goes to state 1
+- Place 2×1 tile in bottom row extending to n+1: goes to state 2
+- Place 2×1 in both rows: goes to state 3
+
+From states 1, 2, 3: must complete the remaining cells with 1×1 tiles, returning to state 0.
+
+This gives:
+- g(n) = f(n, 0) satisfies: g(n) = 2·g(n-1) + 3·g(n-2)
+
+**Recurrence Relation:**
+```
+g(n) = 2·g(n-1) + 3·g(n-2)    for n ≥ 2
+```
+
+**Boundary Conditions:**
+```
+g(0) = 1  (one way to tile empty grid)
+g(1) = 2  (two 1×1 tiles stacked OR one 1×2 tile)
+```
+
+Verification:
+- g(2) = 2·2 + 3·1 = 7 ✓ (matches enumeration of 7 distinct tilings of 2×2)
+
+---
+
+## Problem 1.2: Paths in a Graph
+
+Given: G = (V, E) with V = {1,2,3,4,5} and E = {{1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {3,4}, {4,5}, {5,2}}
+
+Assuming undirected edges (standard notation {u,v}), the adjacency is:
+- Node 1: neighbors {2, 3, 4, 5}
+- Node 2: neighbors {1, 3, 5}
+- Node 3: neighbors {1, 2, 4}
+- Node 4: neighbors {1, 3, 5}
+- Node 5: neighbors {1, 2, 4}
+
+**Recurrence Relations:**
+Let p_i(n) = number of paths of length n starting at node 1 and ending at node i.
+
+For n ≥ 1:
+```
+p_1(n) = p_2(n-1) + p_3(n-1) + p_4(n-1) + p_5(n-1)
+p_2(n) = p_1(n-1) + p_3(n-1) + p_5(n-1)
+p_3(n) = p_1(n-1) + p_2(n-1) + p_4(n-1)
+p_4(n) = p_1(n-1) + p_3(n-1) + p_5(n-1)
+p_5(n) = p_1(n-1) + p_2(n-1) + p_4(n-1)
+```
+
+**Boundary Conditions:**
+```
+p_1(0) = 1  (path of length 0 is the starting node 1)
+p_i(0) = 0  for i ∈ {2, 3, 4, 5}
+```
+
+The total number of paths of length n starting at node 1 is: p(n) = Σ p_i(n) for i ∈ {1,2,3,4,5}
+
+---
+
+## Problem 1.3: Functions with Constraints
+
+Given: F = {f : {1,...,n} → {0,1,2} : for all 1 ≤ i ≤ n-1, f(i) + f(i+1) ≠ 4}
+
+### Part (a): Recurrence and Boundary Conditions
+
+The constraint f(i) + f(i+1) ≠ 4 rules out only the case where both consecutive values are 2.
+
+Define:
+- a(n) = |F| (number of valid functions on {1,...,n})
+- c(n) = number of valid functions on {1,...,n} with f(n) = 2
+
+**Deriving the recurrence:**
+
+For f ∈ F defined on {1,...,n}:
+- If f(n) = 0 or 1: f(n-1) can be any value in {0,1,2}. These contribute a(n-1) functions each.
+- If f(n) = 2: then f(n-1) + f(n) ≠ 4 requires f(n-1) ≠ 2. These contribute a(n-1) - c(n-1) functions.
+
+Thus:
+```
+a(n) = a(n-1) + a(n-1) + (a(n-1) - c(n-1)) = 3·a(n-1) - c(n-1)
+```
+
+And:
+```
+c(n) = a(n-1) - c(n-1)  (functions ending in 2 must have f(n-1) ≠ 2)
+```
+
+From these relations:
+- a(n) - c(n) = 2·a(n-1)
+- a(n) = 2·a(n-1) + c(n)
+- c(n) = 2·a(n-2) (can be derived by substitution)
+
+Therefore:
+```
+a(n) = 2·a(n-1) + 2·a(n-2)   for n ≥ 2
+```
+
+**Boundary Conditions:**
+```
+a(0) = 1  (one way to assign values on empty domain: the empty function)
+a(1) = 3  (three functions: f(1)∈{0,1,2}, no constraint)
+```
+
+Verification:
+- a(2) = 2·3 + 2·1 = 8 ✓
+- a(3) = 2·8 + 2·3 = 22 ✓
+
+---
+
+### Part (b): Explicit Formula
+
+The recurrence a(n) = 2·a(n-1) + 2·a(n-2) has characteristic equation:
+```
+x² - 2x - 2 = 0
+```
+
+Using the quadratic formula:
+```
+x = (2 ± √(4 + 8))/2 = (2 ± 2√3)/2 = 1 ± √3
+```
+
+The roots are: r₁ = 1 + √3 and r₂ = 1 - √3
+
+The general solution is:
+```
+a(n) = A·(1 + √3)ⁿ + B·(1 - √3)ⁿ
+```
+
+Using boundary conditions a(0) = 1 and a(1) = 3:
+- a(0) = A + B = 1
+- a(1) = A(1 + √3) + B(1 - √3) = 3
+
+Solving:
+- From the first: B = 1 - A
+- Substituting: A(1 + √3) + (1-A)(1 - √3) = 3
+- A(2√3) + (1 - √3) = 3
+- A = (2 + √3)/(2√3) = (2√3 + 3)/6
+
+And B = (3 - 2√3)/6
+
+**Explicit Formula:**
+```
+a(n) = [(2√3 + 3)/6]·(1 + √3)ⁿ + [(3 - 2√3)/6]·(1 - √3)ⁿ
+```
+
+Or equivalently:
+```
+a(n) = (1/6)·[(2√3 + 3)·(1 + √3)ⁿ + (3 - 2√3)·(1 - √3)ⁿ]
+```
+
+---
+
+## Problem 2.1: Seam Removal for Image Compression
+
+### Part (a): Exponential Growth of Seams
+
+A seam is a sequence of pixels (one per row) from top to bottom where consecutive pixels are vertically or diagonally adjacent (in the same or adjacent columns).
+
+**Number of possible seams:**
+
+For an m×n grid with m rows and n columns:
+- Row 1: pixel can be in any of n columns
+- Row 2: pixel can be in one of 3 columns (same column or ±1 columns from previous)
+- Rows 3 to m: each can be in one of 3 columns (relative to previous row)
+
+In the worst case (avoiding boundary effects by assuming n is large):
+- Number of seams ≥ n · 3^(m-1)
+
+Since 3^(m-1) grows exponentially in m and n > 1, the number of seams grows **at least exponentially in m**.
+
+For large m, the growth is approximately O(3^m), which is exponential.
+
+---
+
+### Part (b): Dynamic Programming Algorithm for Minimum-Disruption Seam
+
+**Problem:** Find a seam with minimum total disruption cost.
+
+**Recurrence:**
+
+Let DP[i][j] = minimum disruption cost of a seam from row 1 to row i, ending at column j.
+
+```
+DP[1][j] = d[1][j]   for all j ∈ {1,...,n}
+```
+
+For i > 1:
+```
+DP[i][j] = d[i][j] + min(DP[i-1][j-1], DP[i-1][j], DP[i-1][j+1])
+```
+(where boundary conditions apply: DP[i-1][j-1] = ∞ if j-1 < 1, etc.)
+
+**Boundary Conditions:**
+```
+DP[1][j] = d[1][j]  for j ∈ {1,...,n}
+```
+
+**Algorithm:**
+
+```
+1. Initialize: DP[1][j] = d[1][j] for all j
+2. For i = 2 to m:
+     For j = 1 to n:
+       DP[i][j] = d[i][j] + min of (DP[i-1][j-1], DP[i-1][j], DP[i-1][j+1])
+           (handling boundaries appropriately)
+3. Answer = min(DP[m][j]) for all j ∈ {1,...,n}
+4. Backtrack to reconstruct the seam
+```
+
+**Efficiency:**
+
+- Time complexity: **O(m·n)** — iterate through m rows and n columns, each cell examined once
+- Space complexity: **O(m·n)** for the DP table, or **O(n)** if using rolling arrays since only previous row is needed
+- Overall: **Polynomial time** (linear in input size)
+
+This is a classic dynamic programming problem similar to the matrix chain multiplication or longest common subsequence problems.
+
+---
+
+## Problem 2.2: Optimal String Breaking Sequence
+
+### Problem Setup
+
+Given a string of n characters and an array L[1..m] of m break points (positions after which breaks occur).
+
+Objective: Find the sequence of breaks that minimizes total cost, where breaking a string of length ℓ costs ℓ time units.
+
+### Recurrence and Algorithm
+
+**Insight:** The problem is a partition optimization problem. After breaks are made, we have m+1 substrings. The order of breaks affects which substring gets broken when.
+
+Let the positions be extended as p₀ = 0 and p_{m+1} = n (full string), with L[1..m] = p₁, p₂, ..., p_m in sorted order.
+
+**Define:** DP[i][j] = minimum cost to completely partition substring from position p_i to p_j (which has length p_j - p_i).
+
+This represents the cost of performing all internal breaks to further split the substring into parts matching the required break points within [p_i, p_j].
+
+**Recurrence:**
+
+If no further breaks are needed within (p_i, p_j):
+```
+DP[i][i+1] = 0  (substring with no internal breaks requires no breaks)
+```
+
+For segments requiring internal breaks:
+```
+DP[i][j] = (p_j - p_i) + min{ DP[i][k] + DP[k][j] : i < k < j }
+```
+
+The cost (p_j - p_i) is incurred by the first break that splits the segment into two parts at some internal position k.
+
+**Boundary Conditions:**
+```
+DP[i][i+1] = 0  for all i (no breaks needed for adjacent boundaries)
+```
+
+**Base Case for Computation:**
+
+Compute DP values in increasing order of segment length (j - i):
+
+1. Length 1: DP[i][i+1] = 0 for all i
+2. Length 2: DP[i][i+2] = (p_{i+2} - p_i) + 0 = p_{i+2} - p_i (one break needed)
+3. Length k: DP[i][i+k] = (p_{i+k} - p_i) + min{ DP[i][i+t] + DP[i+t][i+k] : 1 ≤ t < k }
+
+**Algorithm:**
+
+```
+1. Sort break points: L[1..m]
+2. Extend: p[0]=0, p[1..m]=L[1..m], p[m+1]=n
+3. Initialize DP[i][i+1] = 0 for all i
+4. For len = 2 to m+1:
+     For i = 0 to m+1-len:
+       j = i + len
+       DP[i][j] = ∞
+       cost_of_break = p[j] - p[i]
+       For k = i+1 to j-1:
+         DP[i][j] = min(DP[i][j], cost_of_break + DP[i][k] + DP[k][j])
+5. Answer = DP[0][m+1]
+6. Reconstruct by tracking which k achieved the minimum at each step
+```
+
+**Reconstruction:** To output the sequence of breaks, maintain parent pointers tracking which k value was chosen at each DP[i][j], then recursively reconstruct the left and right subproblems.
+
+### Efficiency
+
+- **Time complexity:** O(m³) — three nested loops over break positions
+- **Space complexity:** O(m²) — DP table of size (m+2)×(m+2)
+- **Overall:** **Polynomial time**
+
+This is a classic interval DP problem, related to matrix chain multiplication and optimal binary search trees.