diff --git a/writeup.md b/writeup.md
index 76d2b84..98e9071 100644
--- a/writeup.md
+++ b/writeup.md
@@ -2,8 +2,182 @@
 
 ## 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
 
+**Claim:** The greedy algorithm (pack boxes in arrival order; send the truck when the next box does not fit) minimizes the number of trucks.
+
+**Proof.** Let boxes arrive with weights w₁, w₂, ..., wₙ, and let W be the truck capacity. Because company policy requires shipping boxes in order, every valid solution partitions the sequence of boxes into consecutive groups (trucks), where each group's total weight is at most W.
+
+Let the greedy solution partition the boxes into groups ending at positions g₁ < g₂ < ... < gₖ = n (so the first truck carries boxes 1 through g₁, the second carries g₁+1 through g₂, etc.). Let any other feasible solution (in particular, an optimal solution OPT) partition the boxes into groups ending at positions o₁ < o₂ < ... < oₘ = n.
+
+**Lemma:** For every i such that both gᵢ and oᵢ are defined, gᵢ ≥ oᵢ.
+
+*Proof of Lemma by induction on i:*
+
+**Base case (i = 1):** The greedy algorithm loads boxes 1, 2, ..., g₁ onto the first truck, where g₁ is the largest index such that w₁ + w₂ + ... + w_{g₁} ≤ W. Any feasible solution's first truck carries boxes 1, ..., o₁ with total weight ≤ W, so o₁ ≤ g₁ since g₁ is the maximum such index.
+
+**Inductive step:** Assume gᵢ ≥ oᵢ. Consider the (i+1)-th truck in each solution.
+
+- The greedy's (i+1)-th truck starts at box gᵢ + 1 and loads the maximum number of consecutive boxes that fit, ending at g_{i+1}.
+- The optimal's (i+1)-th truck starts at box oᵢ + 1 and carries boxes oᵢ + 1, ..., o_{i+1}.
+
+Since gᵢ ≥ oᵢ, the set {gᵢ + 1, ..., o_{i+1}} is a subset of {oᵢ + 1, ..., o_{i+1}}. Thus the total weight of boxes gᵢ + 1, ..., o_{i+1} is at most the total weight of boxes oᵢ + 1, ..., o_{i+1}, which is ≤ W (since they fit on one truck in OPT). Therefore boxes gᵢ + 1, ..., o_{i+1} all fit on one truck. Since the greedy loads the maximum number of boxes, g_{i+1} ≥ o_{i+1}. This completes the inductive step.
+
+**Main argument.** The greedy finishes all n boxes using k trucks, so gₖ = n. Suppose for contradiction that k > m. Then by the Lemma, gₘ ≥ oₘ = n. This means the greedy has shipped all n boxes using only m trucks, contradicting that the greedy uses k > m trucks. Therefore k ≤ m.
+
+Since OPT is any feasible solution, the greedy uses the minimum number of trucks. **∎**
+
+---
+
+## Problem 2: Smallest Set of Intervals Containing Points
+
+**Algorithm:**
+
+Input: A set of points {x₁, x₂, ..., xₙ} on the real line.
+
+1. Sort the points in increasing order: x₍₁₎ ≤ x₍₂₎ ≤ ... ≤ x₍ₙ₎.
+2. Initialize the set of intervals S = ∅ and set i = 1.
+3. While i ≤ n:
+   - Place the interval I = [x₍ᵢ₎, x₍ᵢ₎ + 1]. Add I to S.
+   - Advance i past all points covered by I: set i to the smallest index j > i such that x₍ⱼ₎ > x₍ᵢ₎ + 1. (If no such j exists, stop.)
+4. Return S.
+
+The algorithm greedily places each interval's left endpoint at the leftmost uncovered point, which extends coverage as far right as possible.
+
+**Proof of Correctness.** We prove the greedy solution G = {I₁, I₂, ..., Iₖ} has minimum cardinality.
+
+Let O = {J₁, J₂, ..., Jₘ} be any optimal solution with m intervals. We show k ≤ m.
+
+Let the greedy intervals be I₁ = [x_{a₁}, x_{a₁} + 1], I₂ = [x_{a₂}, x_{a₂} + 1], ..., where x_{a₁} is the leftmost point, and x_{a_j} is the leftmost point not covered by I₁, ..., I_{j-1}.
+
+We prove by induction that for each j, the right endpoint of Iⱼ is at least as large as the right endpoint of the j-th interval in any optimal solution (when optimal intervals are sorted by left endpoint).
+
+**Base case (j = 1):** The interval J₁ in OPT that covers the leftmost point x_{a₁} must satisfy l₁ ≤ x_{a₁}, where J₁ = [l₁, l₁ + 1]. Thus J₁'s right endpoint is l₁ + 1 ≤ x_{a₁} + 1, which is I₁'s right endpoint. Since x_{a₁} is the leftmost point, there are no points to the left of x_{a₁}, so I₁ covers every point that J₁ covers (among our point set), and possibly more (since its right endpoint extends at least as far).
+
+**Inductive step:** Assume I₁, ..., Iⱼ together cover all points covered by J₁, ..., Jⱼ. Then x_{a_{j+1}} (the leftmost uncovered point after the first j greedy intervals) is also not covered by J₁, ..., Jⱼ. Therefore OPT needs a distinct interval J_{j+1} to cover x_{a_{j+1}}. Since J_{j+1} must contain x_{a_{j+1}}, its left endpoint is ≤ x_{a_{j+1}}, so its right endpoint is ≤ x_{a_{j+1}} + 1 = I_{j+1}'s right endpoint. Hence I_{j+1} covers all points that J_{j+1} covers, maintaining the inductive invariant.
+
+Since each greedy interval Iⱼ maps to a distinct interval Jⱼ in OPT, we get k ≤ m. As OPT is optimal, k = m, so the greedy solution is optimal. **∎**
+
+---
+
+## Problem 3: All Spanning Trees from Kruskal's
+
+**Claim:** For every minimum spanning tree T of a graph G, there exists an ordering of G's edges (consistent with non-decreasing weight) such that Kruskal's algorithm returns T.
+
+**Proof.** Given an MST T, define the following edge ordering: sort edges by non-decreasing weight, and among edges of the same weight, place edges in T before edges not in T (breaking remaining ties arbitrarily).
+
+We show that Kruskal's algorithm with this ordering accepts exactly the edges of T.
+
+Partition the edges of G into weight classes W₁ < W₂ < ... < Wₚ. We prove by induction on j that after processing all edges in weight classes W₁, ..., Wⱼ, Kruskal's forest F consists of exactly the edges of T with weight ≤ Wⱼ.
+
+**Base case (j = 0):** Before processing any edges, F = ∅, which equals the set of T-edges with weight less than W₁. ✓
+
+**Inductive step:** Assume that after processing weight classes W₁, ..., W_{j-1}, the forest F consists exactly of the T-edges with weight < Wⱼ. Now we process weight class Wⱼ.
+
+*T-edges are accepted:* Within weight class Wⱼ, edges in T come first in our ordering. Adding these edges one by one to F always produces a subset of T's edge set (since F ⊆ T by the inductive hypothesis). Since T is a tree (hence acyclic), every subset of T's edges is acyclic. So Kruskal accepts every T-edge in weight class Wⱼ.
+
+*Non-T edges are rejected:* After accepting all T-edges of weight Wⱼ, the forest is F' = {all edges of T with weight ≤ Wⱼ}. Consider a non-T edge f with w(f) = Wⱼ. Since T is a spanning tree and f ∉ T, adding f to T creates a unique cycle C. Every edge of C other than f belongs to T. We claim every edge e ∈ C \ {f} has w(e) ≤ Wⱼ.
+
+Suppose for contradiction that some edge e ∈ C ∩ T has w(e) > Wⱼ = w(f). Then T' = T − {e} ∪ {f} is a spanning tree (removing e from cycle C disconnects T into two components, and f reconnects them). Its total weight is w(T) − w(e) + w(f) < w(T), contradicting the minimality of T.
+
+Therefore all edges of C \ {f} have weight ≤ Wⱼ, so they are all in F'. This means f creates a cycle with the edges in F', and Kruskal rejects f.
+
+By induction, Kruskal accepts exactly the edges of T, so it returns T. **∎**
+
+---
+
+## Problem 4: Oscillating Subsequence
+
+Recall: a sequence X[1..n] 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: high, low, high, low, ... (the first step is a decrease, the second is an increase, and so on alternating).
+
+**Greedy Algorithm:**
+
+```
+LONGEST-OSCILLATING(A[1..n]):
+    if n = 0: return 0
+    length = 1
+    last = A[1]
+    state = "need_decrease"    // position 1 is odd, so X[1] > X[2]
+
+    for i = 2 to n:
+        if state = "need_decrease" and A[i] < last:
+            length = length + 1
+            last = A[i]
+            state = "need_increase"
+        else if state = "need_increase" and A[i] > last:
+            length = length + 1
+            last = A[i]
+            state = "need_decrease"
+        else:
+            // Greedily update last to a more extreme value
+            if state = "need_decrease":
+                last = max(last, A[i])   // higher peak → easier descent
+            else:
+                last = min(last, A[i])   // lower valley → easier ascent
+
+    return length
+```
+
+**Description:** We scan A from left to right maintaining the last value selected and the direction of the next required step. At each position:
+
+- If the current element satisfies the required direction (decrease or increase) relative to `last`, we extend the subsequence and flip the required direction.
+- Otherwise, we greedily update `last`: if we need a decrease next, we replace `last` with a higher value (to make a future decrease more likely); if we need an increase, we replace `last` with a lower value (to make a future increase more likely).
+
+**Correctness Argument:**
+
+The algorithm is correct because of two key observations:
+
+1. **Extending is always optimal.** When we can extend the oscillating subsequence, we should—delaying can only cause us to miss an opportunity, never create a better one. Adding an element now does not prevent future extensions.
+
+2. **Updating `last` is safe and optimal.** When we cannot extend but encounter an element that is more extreme in the desired direction (a higher peak or a lower valley), replacing `last` with this element is safe: the new value appears later in A than the previous `last`, and it still satisfies the oscillating property with respect to all preceding chosen elements. Having a more extreme value strictly increases (or does not decrease) the chance of extending the subsequence later.
+
+More formally, let L(i) be the length of the longest oscillating subsequence of A[1..i] that the algorithm produces after processing position i. By the above reasoning, L(i) is optimal at each step, and the greedy choices maintain an optimal "state" (the best possible endpoint value) for future extensions.
+
+The algorithm runs in O(n) time and O(1) extra space.
+
+---
+
+## Problem 5: Coin Changing
+
+### Part (a)
+
+**Available denominations:** c⁰ = 1, c¹, c², ..., cᵏ, where c > 1 and k ≥ 1 are integers.
+
+**Greedy Algorithm:**
+
+```
+COIN-CHANGE(n, c, k):
+    coins_used = 0
+    remaining = n
+    for i = k down to 0:
+        coins_used = coins_used + ⌊remaining / cⁱ⌋
+        remaining = remaining mod cⁱ
+    return coins_used
+```
+
+At each step, use as many coins as possible of the largest remaining denomination.
+
+**Proof of Optimality.**
+
+**Observation:** The greedy algorithm produces the base-c representation of n. Specifically, if n = aₖcᵏ + a_{k-1}c^{k-1} + ... + a₁c + a₀, where 0 ≤ aᵢ ≤ c − 1 for all i < k and aₖ ≥ 0, then the greedy uses exactly aᵢ coins of denomination cⁱ. This is the standard base-c digit decomposition.
+
+**Lemma:** In any optimal solution, the number of coins used of denomination cⁱ (for i = 0, 1, ..., k−1) is at most c − 1.
+
+*Proof of Lemma:* Suppose an optimal solution uses c or more coins of denomination cⁱ for some i < k. Then we can replace c coins of denomination cⁱ with a single coin of denomination cⁱ⁺¹ (since c · cⁱ = cⁱ⁺¹), producing the same total value with c − 1 fewer coins. This contradicts optimality. **∎**
+
+**Main Proof:** Since any optimal solution uses at most c − 1 coins of each denomination below cᵏ, it corresponds to a representation n = a'_k · cᵏ + a'_{k-1} · c^{k-1} + ... + a'₀ · c⁰, where 0 ≤ a'ᵢ ≤ c − 1 for i < k. But the base-c representation of n with this constraint is unique: the digits a₀, a₁, ..., a_{k-1} are uniquely determined, and consequently aₖ is also uniquely determined. Therefore the optimal solution must use exactly the same coin counts as the greedy algorithm.
+
+Since the greedy solution is the unique representation using at most c − 1 coins of each denomination below cᵏ, and every optimal solution must also have this property, the greedy algorithm is optimal. **∎**
+
+### Part (b)
+
+**Counterexample denominations:** {1, 3, 4}.
+
+Consider making change for **n = 6 cents**:
+
+- **Greedy:** Choose the largest denomination ≤ 6, which is 4. Remaining = 2. Then use two 1-cent coins. Total: **3 coins** (4 + 1 + 1).
+- **Optimal:** Use two 3-cent coins. Total: **2 coins** (3 + 3).
+
+The greedy algorithm yields 3 coins, but the optimal solution uses only 2 coins. Therefore, the greedy algorithm does not yield an optimal solution for the denomination set {1, 3, 4}. **∎**