diff --git a/writeup.md b/writeup.md
index 5119c04..1545869 100644
--- a/writeup.md
+++ b/writeup.md
@@ -2,8 +2,347 @@
 
 ## Student Responses
 
-<!-- Write your solutions below. Add sections for each problem as needed. -->
-<!-- Use proper mathematical notation where applicable. -->
+---
 
-[Your solutions here]
+## Problem 1: String Merging
 
+### Part 1 [5 points]
+
+**Algorithm:**
+
+Define `dp[i][j]` = `true` if `Z[1..i+j]` can be formed by interleaving `X[1..i]` and `Y[1..j]`.
+
+**Base case:** `dp[0][0] = true`
+
+**Recurrence:**
+```
+dp[i][j] = (i > 0 AND dp[i-1][j] AND Z[i+j] == X[i])
+         OR (j > 0 AND dp[i][j-1] AND Z[i+j] == Y[j])
+```
+
+**Return:** `dp[m][n]`
+
+**Pseudocode:**
+```
+MERGE_CHECK(X, Y, Z):
+  m = |X|, n = |Y|
+  dp[0][0] = true
+  dp[i][j] = false for all other (i, j)
+  for i = 0 to m:
+    for j = 0 to n:
+      if (i, j) == (0, 0): continue
+      if i > 0 and dp[i-1][j] and Z[i+j] == X[i]:
+        dp[i][j] = true
+      if j > 0 and dp[i][j-1] and Z[i+j] == Y[j]:
+        dp[i][j] = true
+  return dp[m][n]
+```
+
+**Correctness:** `dp[i][j]` is `true` iff there is a way to interleave `X[1..i]` and `Y[1..j]` to form `Z[1..i+j]`. At each cell, we consider whether the last character came from `X` (moving from `dp[i-1][j]`) or from `Y` (moving from `dp[i][j-1]`).
+
+**Time complexity:** O(mn), since we fill an (m+1) × (n+1) table with O(1) work per cell.
+
+---
+
+### Part 2 [10 points]
+
+**Algorithm:**
+
+Define `dp[i][j]` = minimum Hamming distance between `Z[1..i+j]` and any string `Z'[1..i+j]` that is a valid interleaving of `X[1..i]` and `Y[1..j]`.
+
+**Base case:** `dp[0][0] = 0`
+
+**Recurrence:** When building Z' at position i+j, the character comes from either X[i] (moving from dp[i-1][j]) or Y[j] (moving from dp[i][j-1]):
+```
+dp[i][j] = min(
+  dp[i-1][j] + (X[i] != Z[i+j] ? 1 : 0),   // take X[i] as next char
+  dp[i][j-1] + (Y[j] != Z[i+j] ? 1 : 0)    // take Y[j] as next char
+)
+```
+with the convention that `dp[i][j] = ∞` if neither predecessor is valid (i.e., when i = j = 0 and both terms don't apply).
+
+**Pseudocode:**
+```
+MERGE_WITH_ERRORS(X, Y, Z, K):
+  m = |X|, n = |Y|
+  Initialize dp[i][j] = ∞ for all i, j
+  dp[0][0] = 0
+  for i = 0 to m:
+    for j = 0 to n:
+      if i == 0 and j == 0: continue
+      cost_x = ∞ if i == 0 else dp[i-1][j] + (X[i] != Z[i+j] ? 1 : 0)
+      cost_y = ∞ if j == 0 else dp[i][j-1] + (Y[j] != Z[i+j] ? 1 : 0)
+      dp[i][j] = min(cost_x, cost_y)
+  return dp[m][n] <= K
+```
+
+**Correctness:** `dp[i][j]` gives the minimum number of positions where Z' must differ from Z to produce Z[1..i+j] as an interleaving of X[1..i] and Y[1..j]. At each position i+j of Z', we choose the character from either X[i] or Y[j], incurring a cost of 1 if that character differs from Z[i+j]. We return `true` iff this minimum cost is ≤ K.
+
+**Time complexity:** O(mn), using the same (m+1) × (n+1) table with O(1) work per cell.
+
+---
+
+## Problem 2: Inventory Planning [20 Points]
+
+**DP Formulation:**
+
+Let `dp[i][j]` = minimum total cost for months 1 through i, with j machines left in inventory at the end of month i.
+
+**State space:** i ∈ {0, ..., n}, j ∈ {0, ..., D} where D = Σ dᵢ is total demand.
+
+**Base case:** `dp[0][0] = 0`, `dp[0][j] = ∞` for j > 0 (start with no inventory).
+
+**Transition:** For each month i with demand dᵢ and ending inventory j, the starting inventory was prev_j (end of month i−1), so production is:
+```
+p_i = j - prev_j + d_i
+```
+This requires p_i ≥ 0, i.e., prev_j ≤ j + dᵢ.
+
+The holding cost is h(j) for j ≥ 1, and 0 for j = 0. Define h(0) = 0.
+
+```
+dp[i][j] = min over 0 ≤ prev_j ≤ min(D, j + d_i):
+              dp[i-1][prev_j] + c · max(0, (j - prev_j + d_i) - m) + h(j)
+```
+
+**Algorithm:**
+```
+INVENTORY_PLAN(d[1..n], m, c, h[1..D]):
+  D = sum of d[i]
+  Initialize dp[0][0] = 0, dp[0][j] = ∞ for j > 0
+  for i = 1 to n:
+    for j = 0 to D:
+      dp[i][j] = ∞
+      for prev_j = 0 to min(D, j + d[i]):
+        p_i = j - prev_j + d[i]       // production this month
+        overtime = c * max(0, p_i - m) // overtime labor cost
+        holding = h(j)                 // holding cost (h(0) = 0)
+        dp[i][j] = min(dp[i][j], dp[i-1][prev_j] + overtime + holding)
+  return min over j of dp[n][j]
+```
+
+**Correctness:** The DP correctly accounts for all costs. In each month i, given prev_j units of inventory carried over, producing p_i = j - prev_j + dᵢ ≥ 0 machines fulfills demand dᵢ and leaves j units in inventory. Overtime cost applies when p_i > m. The DP considers all reachable states and takes the minimum cost.
+
+**Time complexity:** O(n · D²), since for each of the n months we iterate over O(D) values of j and O(D) values of prev_j.
+
+**Space complexity:** O(D) using a rolling array (only need previous row).
+
+Since n and D are the problem parameters and this running time is polynomial in both, the algorithm satisfies the requirement.
+
+---
+
+## Problem 3: Optimal Matching of Sequences [30 Points]
+
+### Part 1 [3 points]
+
+**Claim:** Every matching M for (X, Y) contains the pairs (1, 1) and (m, n).
+
+**Proof that (1, 1) ∈ M:**
+
+By left-coverage, ∃j ≥ 1 such that (1, j) ∈ M.
+By right-coverage, ∃i ≥ 1 such that (i, 1) ∈ M.
+
+If i = 1, then (1, 1) ∈ M and we are done.
+
+Suppose i > 1 (so i' := i > 1). We have (1, j) ∈ M and (i', 1) ∈ M. If j > 1, then taking i = 1 < i' and j_small = 1 < j_large = j, we have (1, j_large) = (1, j) ∈ M and (i', j_small) = (i', 1) ∈ M, which violates the no-crossing condition. Therefore j = 1, giving (1, 1) ∈ M. ∎
+
+**Proof that (m, n) ∈ M:**
+
+By left-coverage, ∃j ≤ n such that (m, j) ∈ M.
+By right-coverage, ∃i ≤ m such that (i, n) ∈ M.
+
+If j = n, then (m, n) ∈ M and we are done.
+
+Suppose j < n. If i = m, then (m, n) ∈ M and we are done. Suppose i < m. Then we have (i, n) ∈ M and (m, j) ∈ M with i < m and j < n. Taking i_small = i < i_large = m and j_small = j < j_large = n, we have (i_small, j_large) = (i, n) ∈ M and (i_large, j_small) = (m, j) ∈ M, which violates no-crossing. Therefore i = m and (m, n) ∈ M. ∎
+
+---
+
+### Part 2 [7 points]
+
+**Recursive definition:**
+
+```
+f(1, n) = 1   for all n ≥ 1
+f(m, 1) = 1   for all m ≥ 1
+f(m, n) = f(m-1, n) + f(m, n-1) + f(m-1, n-1)   for m, n ≥ 2
+```
+
+**Explanation:**
+
+First, we observe the no-crossing condition implies that the pairs of any matching, sorted by first index, must have non-decreasing second indices. (If (i₁, j₁) and (i₂, j₂) are in M with i₁ < i₂ but j₁ > j₂, this is precisely a crossing.) Therefore every matching M corresponds to a **monotone path** of cells from (1,1) to (m,n) in the grid [m] × [n], where consecutive cells in the path differ by (+1,0), (0,+1), or (+1,+1). The pairs in M are exactly the cells visited by the path.
+
+The left-coverage, right-coverage, and no-crossing properties are equivalent to this path visiting every row 1…m (path starts at row 1 and ends at row m, visiting each row at least once) and every column 1…n (similarly).
+
+**Base cases:** For m = 1 (only one row), the path must visit all n columns, so it moves right at each step: the unique path is (1,1), (1,2), ..., (1,n), giving f(1,n) = 1. Symmetrically, f(m,1) = 1.
+
+**Recursive case:** Consider a matching M for [m] × [n]. By Part 1, (m,n) ∈ M. We show: it is impossible to have both (m, j) ∈ M with j < n and (i, n) ∈ M with i < m simultaneously, because that would give a crossing (with i_small = i, i_large = m, j_small = j, j_large = n). Therefore exactly one of three cases holds:
+
+- **Case A** — No extra pairs in row m or column n: removing (m,n) yields a valid matching for [m−1] × [n−1].
+  - Left-coverage: row m is covered by (m,n) in the original; rows 1..m−1 had no pairs in column n (by case assumption), so all their pairs remain and they are still covered.
+  - Right-coverage: column n is covered by (m,n); columns 1..n−1 had no pairs in row m (by case assumption), so they remain covered.
+  - These matchings are in bijection with matchings for [m−1] × [n−1]: count = f(m−1, n−1).
+
+- **Case B** — Extra pairs in row m (some (m, j) ∈ M with j < n), but no extra pairs in column n: removing (m,n) gives a valid matching for [m] × [n−1].
+  - Right-coverage for [n−1]: each column j < n must be covered; column n has no pairs other than (m,n) (case assumption), so column n−1 must be covered in M by some i < m, which remains. ✓
+  - Left-coverage for row m: (m, j) ∈ M for some j < n, so row m is still covered after removing (m,n). ✓
+  - These matchings are in bijection with matchings for [m] × [n−1]: count = f(m, n−1).
+
+- **Case C** — Extra pairs in column n (some (i, n) ∈ M with i < m), but no extra pairs in row m: by symmetry, removing (m,n) gives a valid matching for [m−1] × [n]: count = f(m−1, n).
+
+Since the three cases are mutually exclusive and exhaustive:
+$$f(m,n) = f(m-1,n-1) + f(m,n-1) + f(m-1,n)$$
+
+(These are the **Delannoy numbers**, counting monotone paths with steps right, down, or diagonal.)
+
+---
+
+### Part 3 [20 points]
+
+**DP Algorithm:**
+
+Let `OPT[i][j]` = minimum cost of a matching for (X[1..i], Y[1..j]).
+
+**Base cases:**
+```
+OPT[1][1] = (x₁ - y₁)²
+OPT[1][j] = OPT[1][j-1] + (x₁ - yⱼ)²   for j ≥ 2
+OPT[i][1] = OPT[i-1][1] + (xᵢ - y₁)²   for i ≥ 2
+```
+
+**Recurrence:**
+```
+OPT[i][j] = (xᵢ - yⱼ)² + min(OPT[i-1][j], OPT[i][j-1], OPT[i-1][j-1])
+```
+
+**Answer:** OPT[m][n]. To recover the actual matching, backtrack through the table.
+
+**Pseudocode:**
+```
+OPTIMAL_MATCH(X[1..m], Y[1..n]):
+  OPT[1][1] = (x₁ - y₁)²
+  for j = 2 to n: OPT[1][j] = OPT[1][j-1] + (x₁ - yⱼ)²
+  for i = 2 to m: OPT[i][1] = OPT[i-1][1] + (xᵢ - y₁)²
+  for i = 2 to m:
+    for j = 2 to n:
+      OPT[i][j] = (xᵢ - yⱼ)² + min(OPT[i-1][j], OPT[i-1][j-1], OPT[i][j-1])
+  return OPT[m][n]
+```
+
+**Correctness:**
+
+By Part 1 (generalized to any sub-rectangle), every matching for (X[1..i], Y[1..j]) must contain the pair (i, j). Combined with the structure from Part 2, any matching for [i] × [j] is a monotone path ending at (i,j), whose second-to-last step was one of (i−1,j), (i,j−1), or (i−1,j−1).
+
+We prove correctness by induction on i+j:
+
+*Base case:* OPT[1][1] = (x₁−y₁)² is correct: the only valid matching for [1]×[1] is {(1,1)}.
+
+*Inductive step:* Assume OPT[i'][j'] is correct for all i'+j' < i+j. Any matching M for [i]×[j] contains (i,j) and falls into one of three cases from Part 2:
+- Restriction to [i−1]×[j] is a valid matching with cost OPT[i−1][j] (by IH)
+- Restriction to [i]×[j−1] is a valid matching with cost OPT[i][j−1] (by IH)
+- Restriction to [i−1]×[j−1] is a valid matching with cost OPT[i−1][j−1] (by IH)
+
+The cost of M equals (xᵢ−yⱼ)² plus the cost of the restriction. Therefore:
+$$\text{OPT}[i][j] = (x_i - y_j)^2 + \min(\text{OPT}[i-1][j],\ \text{OPT}[i][j-1],\ \text{OPT}[i-1][j-1])$$
+
+is correct by optimal substructure. ✓
+
+**Time complexity:** O(mn) — filling an m×n table with O(1) work per cell.
+
+**Space complexity:** O(mn) to store the table (reducible to O(min(m,n)) using two rows if we only need the cost, not the full matching).
+
+---
+
+## Problem 4: Edit Distance & LCS [35 Points]
+
+### Part 1 [3 points]
+
+```
+EDITDISTANCE(X, Y, cᵢ, c_d, c_s):
+  m = |X|, n = |Y|
+  Create table D[0..m][0..n]
+  D[0][0] = 0
+  for i = 1 to m:
+    D[i][0] = i * c_d          // delete X[1..i] entirely
+  for j = 1 to n:
+    D[0][j] = j * cᵢ           // insert Y[1..j] from empty string
+  for i = 1 to m:
+    for j = 1 to n:
+      sub_cost = 0 if X[i] == Y[j] else c_s
+      D[i][j] = min(
+        D[i-1][j] + c_d,       // delete X[i]
+        D[i][j-1] + cᵢ,        // insert Y[j]
+        D[i-1][j-1] + sub_cost // match or substitute
+      )
+  return D[m][n]
+```
+
+---
+
+### Part 2 [12 points]
+
+**Claim:** D(xa, ya) = D(x, y) for all strings x, y and every letter a.
+
+**Proof:**
+
+We use the edit distance recurrence, which follows directly from the definition D(X,Y) = min{cost(W) | edit sequence W for (X,Y)}: for any strings X[1..m] and Y[1..n], an optimal edit sequence for transforming X to Y must either delete X[m], insert Y[n], or match/substitute X[m] with Y[n] as its last operation, giving:
+$$D(X[1..m], Y[1..n]) = \min\bigl(D(X[1..m{-}1], Y[1..n]) + c_d,\ D(X[1..m], Y[1..n{-}1]) + c_i,\ D(X[1..m{-}1], Y[1..n{-}1]) + \text{cost}(X[m], Y[n])\bigr)$$
+
+Applying this to (xa, ya) where both strings end in the same letter a (so the substitution cost is 0):
+$$D(xa, ya) = \min\bigl(D(x, ya) + c_d,\ D(xa, y) + c_i,\ D(x, y) + 0\bigr) \tag{*}$$
+
+We now establish two bounds.
+
+**Step 1:** D(xa, ya) ≤ D(x, y).
+
+This follows immediately from (*): D(xa, ya) = min{..., D(x,y),...} ≤ D(x, y).
+
+Alternatively: take any optimal edit sequence W for (x, y). Appending the operation "match a with a" (cost 0) to W yields a valid edit sequence for (xa, ya) of cost D(x, y). Hence D(xa, ya) ≤ D(x, y).
+
+**Step 2:** D(xa, ya) ≥ D(x, y), i.e., the minimum in (*) equals D(x, y).
+
+We show each of the first two terms in (*) is ≥ D(x, y):
+
+- **D(x, ya) + c_d ≥ D(x, y):** By the triangle inequality for edit distance, D(x, y) ≤ D(x, ya) + D(ya, y). Since D(ya, y) ≤ c_d (delete the last character a from ya), we get D(x, y) ≤ D(x, ya) + c_d, i.e., D(x, ya) + c_d ≥ D(x, y). ✓
+
+- **D(xa, y) + cᵢ ≥ D(x, y):** By the triangle inequality, D(x, y) ≤ D(x, xa) + D(xa, y). Since D(x, xa) ≤ cᵢ (insert a at the end of x), we get D(x, y) ≤ cᵢ + D(xa, y), i.e., D(xa, y) + cᵢ ≥ D(x, y). ✓
+
+Since both D(x, ya) + c_d ≥ D(x, y) and D(xa, y) + cᵢ ≥ D(x, y), and the third term equals D(x, y), the minimum in (*) is exactly D(x, y).
+
+**Conclusion:** Combining Steps 1 and 2:
+$$D(xa, ya) = D(x, y) \qquad \square$$
+
+---
+
+### Part 3 [20 points]
+
+**One-line computation:**
+```
+L(X, Y) = (|X| + |Y| - EDITDISTANCE(X, Y, 1, 1, ∞)) / 2
+```
+
+**Explanation:** We call `EDITDISTANCE(X, Y, 1, 1, ∞)` with insertion cost cᵢ = 1, deletion cost c_d = 1, and substitution cost c_s = ∞.
+
+**Proof of correctness:**
+
+We prove that D(X, Y, 1, 1, ∞) = |X| + |Y| − 2·L(X, Y), which immediately gives the formula.
+
+Let m = |X|, n = |Y|, L = L(X, Y).
+
+**Setting c_s = ∞ means substitutions are never used.** Any edit sequence that uses a substitution has infinite cost, so no optimal sequence uses substitutions (since there always exists a finite-cost sequence using only insertions and deletions).
+
+**Upper bound:** D(X, Y, 1, 1, ∞) ≤ m + n − 2L.
+
+Let (i₁, j₁), ..., (i_L, j_L) be the index pairs of a longest common subsequence (so X[i_k] = Y[j_k] for each k). Construct an edit sequence:
+- Delete the m − L characters of X not in the LCS (cost m − L).
+- Insert the n − L characters of Y not in the LCS in the correct positions (cost n − L).
+The result is Y, with total cost (m − L) + (n − L) = m + n − 2L.
+
+**Lower bound:** D(X, Y, 1, 1, ∞) ≥ m + n − 2L.
+
+Consider any edit sequence W for (X, Y) using only insertions and deletions. We can analyze W as follows: some characters of X are deleted (say m − k are deleted) and some characters of Y are inserted (say n − k are inserted). The remaining k characters of X are "kept": they must appear in Y without insertion, in the same relative order. Since these kept characters must match characters of Y exactly (substitutions are forbidden), they form a **common subsequence** of X and Y of length k. By definition of L(X, Y), we have k ≤ L(X, Y). Therefore:
+$$\text{cost}(W) = (m - k) \cdot 1 + (n - k) \cdot 1 = m + n - 2k \geq m + n - 2L$$
+
+**Combining:** D(X, Y, 1, 1, ∞) = m + n − 2L(X, Y), so:
+$$L(X, Y) = \frac{|X| + |Y| - D(X, Y, 1, 1, \infty)}{2} = \frac{|X| + |Y| - \texttt{EDITDISTANCE}(X, Y, 1, 1, \infty)}{2}$$
+
+Note that the result is always a non-negative integer since D(X,Y,1,1,∞) and |X|+|Y| have the same parity (both differ from 2L by equal amounts). ∎