diff --git a/writeup.md b/writeup.md
index 76d2b84..ce7f1f9 100644
--- a/writeup.md
+++ b/writeup.md
@@ -2,8 +2,233 @@
 
 ## Student Responses
 
-<!-- Write your solutions below. Add sections for each problem as needed. -->
-<!-- Use proper mathematical notation where applicable. -->
+---
 
-[Your solutions here]
+## Problem 1: Greedy Trucking [20 points]
 
+**Algorithm:** Pack boxes in the order they arrive. Whenever the next box would cause the current truck's load to exceed W, send the current truck and start a new one with that box.
+
+**Proof of Optimality:**
+
+Let the boxes be numbered 1 through n in arrival order. Let the greedy solution use g trucks with groups G_1, G_2, ..., G_g (contiguous, maximal: adding one more box would exceed W). Let OPT be any valid solution using k trucks with groups O_1, O_2, ..., O_k.
+
+Define last(G_j) = index of the last box on greedy truck j, and last(O_j) = index of the last box on OPT truck j.
+
+**Claim:** last(G_j) ≥ last(O_j) for all j ≤ min(g, k).
+
+**Proof by induction on j:**
+
+*Base case (j = 1):* The greedy loads boxes 1, 2, ..., last(G_1) where last(G_1) is the maximum index m such that w(1) + ... + w(m) ≤ W (greedy is maximal). Since O_1 is a valid group, w(1) + ... + w(last(O_1)) ≤ W. By maximality of the greedy's first truck, last(G_1) ≥ last(O_1). ✓
+
+*Inductive step:* Assume last(G_j) ≥ last(O_j). Greedy's (j+1)-th truck starts at box s_G = last(G_j) + 1; OPT's (j+1)-th truck starts at box s_O = last(O_j) + 1. Since last(G_j) ≥ last(O_j), we have s_G ≥ s_O.
+
+OPT's (j+1)-th truck carries boxes s_O, s_O+1, ..., last(O_{j+1}) with total weight ≤ W. The boxes s_G, s_G+1, ..., last(O_{j+1}) form a contiguous sub-range of OPT's (j+1)-th load (since s_G ≥ s_O), so their total weight is also ≤ W. Therefore, greedy's (j+1)-th truck can carry at least boxes s_G through last(O_{j+1}). Since the greedy is maximal, last(G_{j+1}) ≥ last(O_{j+1}). ✓
+
+**Conclusion:** By induction, last(G_k) ≥ last(O_k) = n (all n boxes are loaded by OPT's k-th truck). Since last(G_k) ≤ n, we conclude last(G_k) = n, meaning the greedy finishes all n boxes by its k-th truck. Therefore g ≤ k.
+
+Since this holds for any valid solution using k trucks, the greedy minimizes the number of trucks needed. □
+
+---
+
+## Problem 2: Smallest Set of Intervals Containing Points [20 points]
+
+**Algorithm:**
+
+1. Sort the points: x_{(1)} ≤ x_{(2)} ≤ ... ≤ x_{(n)}.
+2. Initialize an empty set of intervals S.
+3. While there are uncovered points:
+   a. Let p be the leftmost uncovered point.
+   b. Add interval [p, p+1] to S.
+   c. Mark all given points in [p, p+1] as covered.
+4. Return S.
+
+**Running time:** O(n log n) due to sorting; the main loop takes O(n) total.
+
+**Proof of Correctness:**
+
+Let GREEDY = {G_1, G_2, ..., G_g} be the greedy intervals (each G_j = [p_j, p_j+1] in the order placed, so p_1 < p_2 < ...). Let OPT = {I_1, I_2, ..., I_k} be any optimal solution sorted by left endpoint, with I_j = [a_j, a_j+1].
+
+**Invariant:** For each j, (i) right(G_j) ≥ right(I_j), and (ii) every given point covered by I_1,...,I_j is also covered by G_1,...,G_j.
+
+We prove this by induction on j.
+
+*Base case (j = 1):* Since I_1 covers x_{(1)} (the leftmost point), we have a_1 ≤ x_{(1)}, so right(I_1) = a_1 + 1 ≤ x_{(1)} + 1 = right(G_1). This gives (i). For (ii): every given point in I_1 = [a_1, a_1+1] satisfies x_{(1)} ≤ point ≤ a_1+1 ≤ x_{(1)}+1 (since all given points are ≥ x_{(1)}), so the point lies in G_1 = [x_{(1)}, x_{(1)}+1]. ✓
+
+*Inductive step:* Assume the invariant holds for j. By part (ii), every given point covered by OPT's first j intervals is also covered by greedy's first j intervals. Therefore, the leftmost given point uncovered by I_1,...,I_j satisfies q ≤ p_{j+1} (the leftmost uncovered by G_1,...,G_j), because anything uncovered by greedy is also uncovered by OPT.
+
+OPT's (j+1)-th interval I_{j+1} = [a_{j+1}, a_{j+1}+1] covers q, so a_{j+1} ≤ q ≤ p_{j+1}. Therefore:
+
+- right(G_{j+1}) = p_{j+1} + 1 ≥ q + 1 ≥ a_{j+1} + 1 = right(I_{j+1}), establishing (i). ✓
+
+- For (ii): given points in I_{j+1} that are not in I_1,...,I_j come from [q, a_{j+1}+1]. Points in [q, p_{j+1}-1] are covered by G_1,...,G_j (since p_{j+1} is the leftmost uncovered by greedy). Points in [p_{j+1}, a_{j+1}+1] ⊆ [p_{j+1}, p_{j+1}+1] are covered by G_{j+1}. ✓
+
+**Conclusion:** By induction, after GREEDY places g intervals and OPT uses k intervals, all given points are covered by OPT (after k steps). Since given points covered by I_1,...,I_k ⊆ given points covered by G_1,...,G_k, all n points are covered by greedy's first k intervals. Therefore g ≤ k, and greedy is optimal. □
+
+---
+
+## Problem 3: All Spanning Trees [20 points]
+
+**Claim:** For any MST T of G, sorting the edges so that tree edges (in T) come before non-tree edges of the same weight causes Kruskal's algorithm to return T.
+
+**Proof:**
+
+**Edge ordering:** Sort edges by (weight, indicator) where indicator = 0 for edges in T and 1 for edges not in T. This ensures tree edges of weight w precede non-tree edges of weight w.
+
+We show Kruskal's adds exactly the edges of T under this ordering.
+
+---
+
+**Part 1: Every tree edge e ∈ T is added.**
+
+Suppose for contradiction that when tree edge e = (u,v) ∈ T is processed, u and v are already connected in the Kruskal forest. Then there is a path Q in the Kruskal forest from u to v. Every edge on Q was processed before e, so every edge on Q has weight ≤ w(e). Moreover, non-tree edges of weight w(e) come *after* e in our ordering, so Q contains no non-tree edges of weight w(e). Therefore every edge on Q has either:
+- weight < w(e), or
+- weight = w(e) and is a tree edge in T.
+
+Can Q use only tree edges in T? If so, Q is a path in T from u to v using edges other than e. But T is a spanning tree, so the *unique* path from u to v in T is the single edge e. Since e has not been processed yet, it cannot be on Q. Contradiction: Q cannot exist using only T-edges (other than e).
+
+Therefore Q contains at least one non-tree edge f ∉ T with w(f) < w(e). (It cannot have weight = w(e) since those come after e in the ordering.)
+
+Consider the cut (S, V \ S) defined by removing e from T: T \ {e} has two components with u ∈ S and v ∈ V \ S. Edge e is the *unique* T-edge crossing this cut (since T is a tree). Path Q from u to v must cross this cut, so Q contains at least one edge crossing (S, V \ S). Let f be such an edge with f ∉ T and w(f) < w(e).
+
+Now consider T' = T \ {e} ∪ {f}. T' is a spanning tree (f reconnects the two components of T \ {e}), and weight(T') = weight(T) − w(e) + w(f) < weight(T). This contradicts T being a minimum spanning tree.
+
+Therefore u and v are in different components when e is processed, and Kruskal's adds e. ✓
+
+---
+
+**Part 2: Every non-tree edge f ∉ T is rejected.**
+
+When non-tree edge f = (u,v) ∉ T is processed, we show u and v are already connected.
+
+Since T is an MST, for the unique path P_T(u,v) in T from u to v, every edge e' on P_T(u,v) satisfies w(e') ≤ w(f). (If some e' had w(e') > w(f), we could replace e' with f to get a lighter spanning tree, contradicting optimality of T.)
+
+All edges on P_T(u,v) are tree edges with weight ≤ w(f). In our ordering, tree edges with weight ≤ w(f) all precede f (tree edges of weight w(f) come before non-tree edges of weight w(f), and f is a non-tree edge). By Part 1, all these tree edges have been added by Kruskal's. Therefore P_T(u,v) is in the Kruskal forest, and u, v are connected when f is processed. Kruskal's rejects f. ✓
+
+**Conclusion:** With this ordering, Kruskal's adds exactly the edges of T, returning T as the spanning tree. Since T was an arbitrary MST, every MST can be produced by some ordering of edges in Kruskal's algorithm. □
+
+---
+
+## Problem 4: Oscillating Subsequence [20 points]
+
+Recall: a sequence is *oscillating* if X[i] > X[i+1] for all odd i, and X[i] < X[i+1] for all even i. The pattern is: big, small, big, small, ... (the sequence starts high and alternates).
+
+**Algorithm:**
+
+```
+LongestOscillating(A[1..n]):
+  if n = 0: return 0
+
+  length ← 1
+  last ← A[1]
+  need ← "down"    // at odd position 1, the next move must be a descent
+
+  for j ← 2 to n do:
+    if need = "down":
+      if A[j] < last:
+        length ← length + 1       // extend: found the needed descent
+        last ← A[j]
+        need ← "up"
+      elif A[j] > last:
+        last ← A[j]               // greedy improvement: larger starting value helps future descent
+    else: // need = "up"
+      if A[j] > last:
+        length ← length + 1       // extend: found the needed ascent
+        last ← A[j]
+        need ← "down"
+      elif A[j] < last:
+        last ← A[j]               // greedy improvement: smaller valley helps future ascent
+
+  return length
+```
+
+**Intuition:** We greedily include elements at each direction change. When we cannot yet extend the subsequence (the current element goes the "wrong" way), we update the last element to be more extreme—making future extensions easier. Specifically: when needing a descent, we prefer a larger last element (easier to find something below it); when needing an ascent, we prefer a smaller last element.
+
+**Proof of Correctness (Greedy Stays Ahead):**
+
+We prove by induction on j that after processing A[1..j], the following invariant holds:
+
+> (I) The greedy achieves the maximum possible oscillating subsequence length L for A[1..j].
+>
+> (II) If need = "down": among all oscillating subsequences of A[1..j] of length L with "down" needed next, the greedy's last value is maximum.
+> If need = "up": among all such subsequences, the greedy's last value is minimum.
+
+*Base case (j = 1):* L = 1, last = A[1], need = "down". The only length-1 oscillating subsequence of A[1..1] is A[1] itself. The invariant holds trivially. ✓
+
+*Inductive step:* Assume the invariant holds after processing A[1..j]. We process A[j+1] with current state (L, last, need). Consider any competitor subsequence C of A[1..j+1] of maximum possible length.
+
+**Case 1: need = "down" and A[j+1] < last.**
+The greedy extends to (L+1, A[j+1], "up"). Any length-(L+1) oscillating subsequence of A[1..j+1] with "up" needed next must end with some element that was reached by a descent; this final element is ≤ last (by invariant (II) for need="down"). The greedy ends at A[j+1], so we need to show it is minimal. Among all length-(L+1) subsequences ending with need="up" in A[1..j+1], those that extended at step j+1 descend to some value ≤ last. Any subsequence that extended before j+1 already achieved length L+1 in A[1..j] — but that's impossible since OPT(j) = L (greedy had maximum length at j). Thus all length-(L+1) subsequences extend at j+1 and end at A[j+1]. The greedy's last value is A[j+1], satisfying (II). ✓
+
+**Case 2: need = "down" and A[j+1] > last.**
+The greedy updates last ← A[j+1] without changing length. No oscillating subsequence of A[1..j+1] exceeds length L: any such extension would require a descent at step j+1 (A[j+1] < last), which doesn't hold, or using A[j+1] as an ascent from a "up"-needed state, but an OPT with "up"-state and length L would need last ≤ previous OPT "up" minimum — since OPT(j) = L, this would require an entirely different subsequence also of length L with need="up", reaching some value. In any case, OPT(j+1) remains L. The greedy's new last = A[j+1] ≥ any previous value, preserving (II) for need="down". ✓
+
+**Case 3: need = "up" and A[j+1] > last.** Symmetric to Case 1 with "up" and "down" swapped. ✓
+
+**Case 4: need = "up" and A[j+1] < last.** Symmetric to Case 2. ✓
+
+**Case 5: A[j+1] = last.** No change; invariant preserved trivially. ✓
+
+By induction, the invariant holds for all j. At j = n, the greedy's length L equals the length of the longest oscillating subsequence of A[1..n]. □
+
+**Example:** A = [5, 1, 9, 7, 23, 30, 3].
+- j=1: last=5, need=down, length=1.
+- j=2: 1 < 5 (need down): extend. last=1, need=up, length=2.
+- j=3: 9 > 1 (need up): extend. last=9, need=down, length=3.
+- j=4: 7 < 9 (need down): extend. last=7, need=up, length=4.
+- j=5: 23 > 7 (need up): extend. last=23, need=down, length=5.
+- j=6: 30 > 23 (need down but 30 > 23): update last=30. length=5.
+- j=7: 3 < 30 (need down): extend. last=3, need=up, length=6.
+- Result: 6. Subsequence: [5, 1, 9, 7, 30, 3].
+
+---
+
+## Problem 5: Coin Changing [20 points]
+
+### Part (a): Powers of c
+
+**Algorithm (Greedy-Change):** At each step, use as many coins of the largest denomination that does not exceed the remaining amount. Formally:
+
+```
+Greedy-Change(n, c, k):
+  for i ← k downto 0:
+    use floor(n / c^i) coins of denomination c^i
+    n ← n mod c^i
+  return the collection of coins used
+```
+
+**Claim:** This greedy algorithm always yields an optimal solution.
+
+**Proof:**
+
+**Step 1 (Reduction to canonical form):** We first show that in any optimal solution, the number of coins of denomination c^i used is at most c − 1, for each i < k.
+
+Suppose some solution uses m ≥ c coins of denomination c^i (i < k). Then c coins of denomination c^i can be replaced by 1 coin of denomination c^{i+1}, reducing the coin count by c − 1 ≥ 1. This gives a solution with fewer coins, contradicting optimality. Therefore any optimal solution uses at most c − 1 coins of each denomination c^i for i < k.
+
+**Step 2 (Uniqueness of representation):** Consider the representation of n in base c:
+
+n = n_0 · c^0 + n_1 · c^1 + ... + n_k · c^k
+
+where each digit 0 ≤ n_i ≤ c − 1 for i < k (and n_k ≥ 0). This base-c representation is unique. The greedy algorithm produces exactly this representation: at each step i, it takes floor((n mod c^{i+1}) / c^i) = n_i coins of denomination c^i.
+
+**Step 3 (Optimality):** Let (m_0, m_1, ..., m_k) be any optimal solution with Σ m_i · c^i = n. By Step 1, m_i ≤ c − 1 for all i < k. By uniqueness of base-c representation, the coefficients satisfying Σ m_i · c^i = n with 0 ≤ m_i ≤ c − 1 for i < k are exactly m_i = n_i for all i. Therefore every optimal solution uses exactly n_i coins of denomination c^i, the same as the greedy. The greedy is optimal. □
+
+**Note:** The total number of greedy coins is Σ n_i (sum of base-c digits of n), which is minimized.
+
+---
+
+### Part (b): Counterexample
+
+**Denominations: {1, 3, 4} with n = 6.**
+
+- **Greedy:** Uses the largest denomination ≤ remaining amount.
+  - 4 ≤ 6: use one 4-cent coin. Remaining: 2.
+  - 3 > 2: skip. 1 ≤ 2: use one 1-cent coin. Remaining: 1.
+  - 1 ≤ 1: use one 1-cent coin. Remaining: 0.
+  - Total: **3 coins** (4 + 1 + 1).
+
+- **Optimal:** Use two 3-cent coins: 3 + 3 = 6.
+  - Total: **2 coins**.
+
+The greedy uses 3 coins while the optimal uses only 2. Therefore the greedy does not yield an optimal solution for denominations {1, 3, 4}.
+
+(Note: The set {1, 3, 4} includes a penny (1-cent coin), so there is a valid solution for every value of n ≥ 0.)