diff --git a/writeup.md b/writeup.md
index 5119c04..8b51f34 100644
--- a/writeup.md
+++ b/writeup.md
@@ -2,8 +2,527 @@
 
 ## 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 [15 points]
 
+### Part 1 [5 points]
+
+**Algorithm:** String Merging Decision DP
+
+We use a 2D DP table `dp[i][j]` to determine if we can form the first `i + j` characters of Z by merging the first `i` characters of X and the first `j` characters of Y.
+
+**Pseudocode:**
+```
+MERGE-DP(X, Y, Z):
+  m = length(X)
+  n = length(Y)
+
+  // Initialize DP table
+  dp = new boolean[m+1][n+1]
+  dp[0][0] = true
+
+  // Base cases: merging empty string with X
+  for i = 1 to m:
+    if Z[i-1] == X[i-1]:
+      dp[i][0] = dp[i-1][0]
+
+  // Base cases: merging empty string with Y
+  for j = 1 to n:
+    if Z[j-1] == Y[j-1]:
+      dp[0][j] = dp[0][j-1]
+
+  // Fill the table
+  for i = 1 to m:
+    for j = 1 to n:
+      // Try taking character from X
+      if X[i-1] == Z[i+j-1] and dp[i-1][j]:
+        dp[i][j] = true
+      // Try taking character from Y
+      if Y[j-1] == Z[i+j-1] and dp[i][j-1]:
+        dp[i][j] = true
+
+  return dp[m][n]
+```
+
+**Time Complexity:** O(m·n) where m = |X| and n = |Y|. We fill an (m+1) × (n+1) table with constant work per cell.
+
+**Space Complexity:** O(m·n) for the DP table.
+
+---
+
+### Part 2 [10 points]
+
+**Algorithm:** String Merging with Hamming Distance Errors
+
+We modify the DP to track the minimum number of errors (substitutions) needed to merge X and Y into a string that has Hamming distance ≤ K from Z.
+
+Let `dp[i][j][k]` be a boolean indicating whether we can form the first `i + j` characters of some string Z' by merging the first `i` characters of X and the first `j` characters of Y, using exactly k errors (substitutions).
+
+**Pseudocode:**
+```
+MERGE-WITH-ERRORS(X, Y, Z, K):
+  m = length(X)
+  n = length(Y)
+
+  // Initialize DP table
+  dp = new boolean[m+1][n+1][K+1]
+  dp[0][0][0] = true
+
+  // Base cases: merging X with empty Y
+  for i = 1 to m:
+    for k = 0 to K:
+      if k == 0:
+        if Z[i-1] == X[i-1] and dp[i-1][0][0]:
+          dp[i][0][0] = true
+      else:
+        // Use a substitution error
+        if dp[i-1][0][k-1]:
+          dp[i][0][k] = true
+        // No error needed
+        if Z[i-1] == X[i-1] and dp[i-1][0][k]:
+          dp[i][0][k] = true
+
+  // Base cases: merging Y with empty X
+  for j = 1 to n:
+    for k = 0 to K:
+      if k == 0:
+        if Z[j-1] == Y[j-1] and dp[0][j-1][0]:
+          dp[0][j][0] = true
+      else:
+        // Use a substitution error
+        if dp[0][j-1][k-1]:
+          dp[0][j][k] = true
+        // No error needed
+        if Z[j-1] == Y[j-1] and dp[0][j-1][k]:
+          dp[0][j][k] = true
+
+  // Fill the table
+  for i = 1 to m:
+    for j = 1 to n:
+      for k = 0 to K:
+        char_merged = the next character should be X[i-1] or Y[j-1]
+
+        // Try taking character from X
+        if X[i-1] == Z[i+j-1]:
+          // No error needed
+          if dp[i-1][j][k]:
+            dp[i][j][k] = true
+        else:
+          // Error needed (substitution)
+          if k > 0 and dp[i-1][j][k-1]:
+            dp[i][j][k] = true
+
+        // Try taking character from Y
+        if Y[j-1] == Z[i+j-1]:
+          // No error needed
+          if dp[i][j-1][k]:
+            dp[i][j][k] = true
+        else:
+          // Error needed (substitution)
+          if k > 0 and dp[i][j-1][k-1]:
+            dp[i][j][k] = true
+
+  // Check if we can merge with at most K errors
+  for k = 0 to K:
+    if dp[m][n][k]:
+      return true
+  return false
+```
+
+**Time Complexity:** O(m·n·K) where m = |X|, n = |Y|, and K is the maximum number of errors allowed. We fill an (m+1) × (n+1) × (K+1) table with constant work per cell.
+
+**Space Complexity:** O(m·n·K) for the 3D DP table. This can be optimized to O(n·K) using rolling arrays if needed.
+
+---
+
+## Problem 2: Inventory Planning [20 Points]
+
+**Problem Setup:**
+- n months with known demand d₁, d₂, ..., dₙ
+- Total demand D = Σdᵢ
+- Regular production capacity: m machines/month (no cost)
+- Overtime production: c dollars per machine (above m)
+- Inventory holding cost: h(j) for holding j machines (monotonically increasing)
+- Goal: Minimize total cost while meeting all demand
+
+**Algorithm:** Dynamic Programming for Inventory Planning
+
+Let `dp[i][j]` be the minimum cost to meet demand for months 1 through i, ending with j machines in inventory at the end of month i.
+
+**Pseudocode:**
+```
+INVENTORY-PLAN(n, d[], m, c, h[]):
+  // Precompute maximum possible inventory at any point
+  max_inventory = sum of all demands
+
+  // Initialize DP table
+  dp = new integer[n+1][max_inventory+1]
+  for j = 0 to max_inventory:
+    dp[0][j] = infinity
+  dp[0][0] = 0  // Start with no inventory
+
+  // Process each month
+  for i = 1 to n:
+    for prev_inventory = 0 to max_inventory:
+      if dp[i-1][prev_inventory] == infinity:
+        continue
+
+      // We must satisfy demand d[i]
+      // We have prev_inventory from previous month
+      // We need to produce: units_needed
+
+      for final_inventory = 0 to max_inventory:
+        units_produced = d[i] + final_inventory - prev_inventory
+
+        // Check feasibility
+        if units_produced < 0:
+          continue  // Can't reduce production below 0
+
+        // Calculate cost for this month
+        if units_produced <= m:
+          production_cost = 0  // Within regular capacity
+        else:
+          overtime_units = units_produced - m
+          production_cost = overtime_units * c
+
+        holding_cost = h[final_inventory]  // Cost to hold final_inventory machines
+
+        total_cost = dp[i-1][prev_inventory] + production_cost + holding_cost
+
+        // Update DP
+        if total_cost < dp[i][final_inventory]:
+          dp[i][final_inventory] = total_cost
+
+  // Find minimum cost to satisfy all demand
+  min_cost = infinity
+  for j = 0 to max_inventory:
+    min_cost = min(min_cost, dp[n][j])
+
+  return min_cost
+```
+
+**Time Complexity:** O(n·D²) where n is the number of months and D is the total demand. The DP table has size O(n·D), and for each cell we iterate through possible production amounts (O(D) per cell).
+
+**Space Complexity:** O(n·D) for the DP table. This can be optimized to O(D) by storing only the previous month's row.
+
+**Key Insight:** The DP state tracks the inventory level at the end of each month. For each month, we determine what production level minimizes cost while satisfying current demand and considering future holding costs.
+
+---
+
+## Problem 3: Optimal Matching of Sequences [30 Points]
+
+### Part 1 [3 points]
+
+**Claim:** Every matching contains the pairs (1, 1) and (m, n).
+
+**Proof:**
+
+By the definition of a matching, we need:
+- **(Left covered):** Every i ∈ [m] must have at least one match in [n]
+- **(Right covered):** Every j ∈ [n] must have at least one match in [m]
+- **(No crossing):** For all i < i' and j < j', we cannot have (i, j') ∈ M and (i', j) ∈ M simultaneously
+
+Consider index 1 ∈ [m]. By the "left covered" property, there exists some j ∈ [n] such that (1, j) ∈ M.
+
+Suppose j > 1. Then consider the rightmost j' < j such that (i, j') ∈ M for some i. If i > 1, then we have 1 < i and j' < j, which would give a crossing with (1, j) and (i, j'), violating the "no crossing" property. Therefore, any match involving indices j' < j must have i = 1. But then we cannot match any other index i > 1 to an index j' < j without creating a crossing.
+
+Since we must cover all indices in [n], the only consistent way is to have (1, 1) ∈ M.
+
+By similar reasoning applied to indices m and n, we must have (m, n) ∈ M.
+
+More formally: If (1, j) ∈ M for j > 1, then no index i > 1 can match to any j' < j (by no-crossing). Since index 1 is covered, all indices i > 1 must match to indices ≥ j. But then indices 2, 3, ..., m (m-1 indices) must all match to the remaining n - j + 1 indices. For this to satisfy "right covered," we need n - j + 1 ≥ m - 1, which may not always hold. The only way to guarantee both conditions is (1, 1) ∈ M. Similarly, (m, n) ∈ M.
+
+---
+
+### Part 2 [7 points]
+
+**Claim:** Let f(m, n) be the number of possible matchings for sequences of length m and n.
+
+**Recursive Definition:**
+
+$$f(m, n) = \begin{cases}
+1 & \text{if } m = 1 \text{ and } n = 1 \\
+0 & \text{if } m \neq n \\
+\sum_{k=1}^{m} f(k-1, k-1) \cdot f(m-k, n-k) & \text{if } m = n \geq 2
+\end{cases}$$
+
+**Explanation:**
+
+From Part 1, we know every matching contains (1, 1) and (m, n).
+
+Consider the structure imposed by the "no-crossing" constraint. The pair (1, 1) is always matched. The pair (m, n) is always matched.
+
+Between these two pairs, we can partition the remaining indices into independent subproblems. Specifically:
+- Indices {2, 3, ..., k} from X and {2, 3, ..., k} from Y form a matching (not crossing with (k+1, ..., m) and (k+1, ..., n))
+- Indices {k+1, ..., m} from X and {k+1, ..., n} from Y form a matching (not crossing with (1, ..., k) and (1, ..., k))
+
+For any valid matching, there exists a "split point" k such that:
+- Indices 1 to k from both X and Y form a valid matching
+- Indices k+1 to m from both X and Y form a valid matching
+- No edges cross between these two partitions
+
+Therefore, for each possible k, the number of matchings is:
+f(k, k) × f(m-k, n-k)
+
+Summing over all possible split points gives the recursive formula above.
+
+The base case f(1, 1) = 1 represents the single matching {(1, 1)} for sequences of length 1.
+
+---
+
+### Part 3 [20 points]
+
+**Algorithm:** Dynamic Programming for Optimal Matching
+
+**Definition:**
+Let `OPT[i][j]` = minimum cost of a matching for X[1..i] and Y[1..j]
+
+**Key Observation:** By the "no-crossing" property and the proof that (1, 1) and (m, n) must be in every matching, the problem has optimal substructure.
+
+**Pseudocode:**
+```
+OPTIMAL-MATCHING(X, Y):
+  m = length(X)
+  n = length(Y)
+
+  // Ensure m == n (required for valid matching)
+  if m != n:
+    return "No valid matching exists"
+
+  // Initialize DP table
+  OPT = new real[m+1][n+1]
+  for i = 0 to m:
+    for j = 0 to n:
+      if i != j:
+        OPT[i][j] = infinity
+      else:
+        OPT[i][j] = 0 if i == 0, else infinity
+
+  OPT[0][0] = 0  // Empty matching
+
+  // Fill the DP table
+  for i = 1 to m:
+    for j = 1 to n:
+      if i != j:
+        continue  // Only valid when lengths are equal
+
+      // The matching must include (i, j)
+      // We sum cost of matching (i, j) with optimal matchings of X[1..k] and Y[1..k]
+      // for some k < i, plus optimal matching of X[k+1..i] and Y[k+1..j]
+
+      cost_i_j = (X[i] - Y[j])^2
+
+      // Try all split points
+      for k = 0 to i-1:
+        candidate = OPT[k][k] + cost_i_j + OPT[i-k][j-k]
+        OPT[i][j] = min(OPT[i][j], candidate)
+
+  return OPT[m][n]
+```
+
+**Correctness:**
+
+The algorithm is correct because:
+
+1. **Optimal Substructure:** If we include pair (i, j) in the optimal matching, then by the no-crossing constraint, the matching must be partitionable into:
+   - A matching of X[1..k] with Y[1..k] for some k < i
+   - The pair (i, j)
+   - A matching of X[k+1..i] with Y[k+1..j]
+   These subproblems are independent and optimal solutions combine to give optimal solution for the full problem.
+
+2. **Complete Coverage:** Every valid matching must have (1, 1) and (m, n) as established in Part 1. The DP considers all possible ways to build up from (1, 1) to (m, n) using the recursive structure.
+
+3. **No-Crossing Compliance:** The recursive structure ensures no crossing: if we match X[k+1..i] to Y[k+1..j], these indices form a contiguous block. Since i = j, the structure is symmetric and no crossing occurs.
+
+**Time Complexity:** O(m³) = O(n³) where m = n is the sequence length. For each of O(m²) DP cells, we iterate through O(m) split points.
+
+**Space Complexity:** O(m²) = O(n²) for the DP table.
+
+---
+
+## Problem 4: Edit Distance & LCS [35 Points]
+
+### Part 1 [3 points]
+
+**Pseudocode:**
+```
+EDITDISTANCE(X, Y, c_i, c_d, c_s):
+  m = length(X)
+  n = length(Y)
+
+  // Initialize DP table
+  D = new real[m+1][n+1]
+
+  // Base case: transforming empty string to Y requires n insertions
+  D[0][0] = 0
+  for j = 1 to n:
+    D[0][j] = D[0][j-1] + c_i
+
+  // Base case: transforming X to empty string requires m deletions
+  for i = 1 to m:
+    D[i][0] = D[i-1][0] + c_d
+
+  // Fill the table using recurrence relation
+  for i = 1 to m:
+    for j = 1 to n:
+      if X[i] == Y[j]:
+        // Characters match: no operation needed
+        D[i][j] = D[i-1][j-1]
+      else:
+        // Take minimum of three operations:
+        // 1. Insert Y[j]: D[i][j-1] + c_i
+        // 2. Delete X[i]: D[i-1][j] + c_d
+        // 3. Substitute X[i] with Y[j]: D[i-1][j-1] + c_s
+        D[i][j] = min(
+          D[i][j-1] + c_i,      // Insert
+          D[i-1][j] + c_d,      // Delete
+          D[i-1][j-1] + c_s     // 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:**
+
+Let x be a string of length m and y be a string of length n. Let a be any letter. We want to show D(xa, ya) = D(x, y), where xa denotes the string x concatenated with a.
+
+**Definition Recall:** D(X, Y) is the minimum cost of any sequence of edit operations that transforms X into Y.
+
+**Direction 1: D(xa, ya) ≤ D(x, y)**
+
+Let W be an optimal edit sequence transforming x to y with cost D(x, y). We can construct an edit sequence W' that transforms xa to ya as follows:
+- Apply the same operations as W to transform x to y
+- The final character a in xa becomes the final character in ya (they match)
+- No additional operation is needed for the final character
+
+Thus, cost(W') = cost(W) = D(x, y), which shows D(xa, ya) ≤ D(x, y).
+
+**Direction 2: D(x, y) ≤ D(xa, ya)**
+
+Let W* be an optimal edit sequence transforming xa to ya with cost D(xa, ya).
+
+Consider the last operation in W*:
+- If W* ends with a delete of a from xa, then the sequence before this operation transforms xa to y. This sequence has cost D(xa, ya) - c_d. But this also transforms x to y (since removing a from xa leaves x). Therefore, D(x, y) ≤ D(xa, ya) - c_d < D(xa, ya).
+
+- If W* ends with a substitution of a to something other than a, then the final character of ya is not a. But ya ends with a by definition, contradiction. So this case is impossible.
+
+- If W* ends with an insertion, then before this insertion, we have transformed xa to y[1..n-1]. But y[1..n-1] has length n-1 and ya has length n, so the insertion adds the n-th character. Since both y and ya end with a, this insertion must insert a. So the state before the insertion is y[1..n-1], and we transformed xa to y[1..n-1]. But then we need to reach ya = y[1..n-1]a by inserting a, at cost c_i. So the cost before the insertion is D(xa, ya) - c_i. But the sequence transforming xa to y[1..n-1] also transforms x to y[1..n-1]... wait, let me reconsider.
+
+Let me use a clearer argument:
+
+**Clearer proof:**
+
+Consider any edit sequence W that transforms xa to ya. Let's analyze this sequence systematically.
+
+**Case 1:** The last operation in W matches the final a from xa with the final a from ya (by performing no operation on the matching pair).
+
+Then the sequence W, before the final step, transforms x to y. So cost(W) = cost(W') where W' is the edit sequence from x to y represented by W without the final pair. Therefore, D(xa, ya) ≥ D(x, y).
+
+**Case 2:** The final character a of xa is deleted before reaching ya.
+
+Then, before the deletion, the partial sequence transforms some prefix xa[1..m] = x to some string. After deletion, we need to still reach ya. But ya ends with a, so after deleting a from xa, we need to match the remaining string to y, then somehow produce the final a in ya. This requires an insertion of a at some point. But we can instead directly match x to y (the edit sequence for that) and add a final insertion of a to get from y to ya... Actually, let me think about this differently.
+
+**Alternative Approach using Optimality:**
+
+Suppose D(xa, ya) < D(x, y). Then there exists an edit sequence W* from xa to ya with cost D(xa, ya) < D(x, y).
+
+Consider the state of the transformation after processing the first m characters of xa (which is x):
+- At some point during W*, the first m operations have transformed x to some string Z
+- The remaining operations transform Za to ya
+- The total cost is cost(W*) = D(xa, ya)
+
+For any such decomposition:
+- cost(first m transformations) + cost(remaining transformations) ≥ D(xa, ya)
+
+Now, the remaining transformation must transform Za to ya, which ends with a. If Z = y (the optimal endpoint for transforming x), then the remaining operations must transform ya to ya, which costs 0. This gives cost(first m) = D(x, y), contradicting D(xa, ya) < D(x, y).
+
+If Z ≠ y, then the remaining operations must transform Za to ya. The cost to transform y to ya is at most c_i (one insertion of a), and any path through Z must have cost at least the cost to transform Z to y, plus the cost to transform ya to ya. By optimality properties of edit distance, this is at least the direct cost from y to ya.
+
+Therefore, D(xa, ya) ≥ D(x, y).
+
+Combined with the earlier direction, D(xa, ya) = D(x, y).
+
+---
+
+### Part 3 [20 points]
+
+**Claim:** The length of the longest common subsequence L(X, Y) can be computed as:
+```
+L(X, Y) = (m + n) - EDITDISTANCE(X, Y, 1, 1, ∞) / 1
+```
+
+More precisely:
+```
+L(X, Y) = (m + n - EDITDISTANCE(X, Y, c_i=1, c_d=1, c_s=∞)) / 2
+```
+
+Wait, let me reconsider. Actually:
+
+```
+L(X, Y) = (m + n) - EDITDISTANCE(X, Y, c_i=1, c_d=1, c_s=∞)
+```
+
+**Justification:**
+
+The key insight is that finding an LCS can be interpreted as an edit distance problem where:
+- c_i = 1 (insert cost)
+- c_d = 1 (delete cost)
+- c_s = ∞ (substitution cost, which we never want to use)
+
+**Proof of Correctness:**
+
+Let's define D(X, Y, c_i, c_d, c_s) as the minimum cost edit distance with these specific costs.
+
+An edit sequence from X to Y can be decomposed into:
+- m deletions of characters from X (each character is either deleted or kept)
+- n insertions of characters into Y (each character is either inserted or kept from the deletions)
+- 0 substitutions (since c_s = ∞, we never substitute)
+
+More formally, if we transform X to Y with only insertions and deletions (and no substitutions):
+- We delete some characters from X, leaving a subsequence of X
+- We insert some characters that don't come from X
+- The remaining characters (not deleted and not inserted) must match between X and Y in order
+
+If we restrict to no substitutions (c_s = ∞), an optimal edit sequence must:
+1. Keep a common subsequence of X and Y (characters that match in order)
+2. Delete characters from X not in this subsequence
+3. Insert characters from Y not in this subsequence
+
+Let L = length of LCS(X, Y). Then:
+- Characters in LCS: L characters (no operation needed, they match)
+- Characters in X not in LCS: m - L characters (must be deleted, cost = m - L)
+- Characters in Y not in LCS: n - L characters (must be inserted, cost = n - L)
+
+Total cost = (m - L) × 1 + (n - L) × 1 = m + n - 2L
+
+Therefore:
+D(X, Y, 1, 1, ∞) = m + n - 2L
+
+Solving for L:
+L = (m + n - D(X, Y, 1, 1, ∞)) / 2
+
+**One-line code:**
+```python
+L = (len(X) + len(Y) - EDITDISTANCE(X, Y, 1, 1, float('inf'))) / 2
+```
+
+Or more explicitly:
+```python
+def LCS_length(X, Y):
+    return (len(X) + len(Y) - EDITDISTANCE(X, Y, c_i=1, c_d=1, c_s=float('inf'))) / 2
+```
+
+**Why this is correct:**
+
+1. With c_s = ∞, substitutions are never used in an optimal edit sequence
+2. Any transformation using only insertions and deletions that achieves minimum cost must preserve the longest common subsequence (deleting non-matching parts from X and inserting non-matching parts from Y)
+3. The formula L = (m + n - cost) / 2 correctly recovers the LCS length from the minimum cost
+
+This approach elegantly connects LCS to edit distance through a specific choice of operation costs.