diff --git a/writeup.md b/writeup.md
index 76d2b84..b9f6ba5 100644
--- a/writeup.md
+++ b/writeup.md
@@ -1,9 +1,285 @@
 # COMP382 Homework 5
 
-## Student Responses
+## Problem 1: Greedy Trucking [20 points]
 
-<!-- Write your solutions below. Add sections for each problem as needed. -->
-<!-- Use proper mathematical notation where applicable. -->
+**Claim:** The greedy algorithm that packs boxes in order of arrival and sends trucks when the next box doesn't fit minimizes the number of trucks needed.
 
-[Your solutions here]
+**Proof:**
+
+Let G be the solution produced by the greedy algorithm using k trucks, and let O be any other valid solution using k* trucks (satisfying the constraint that boxes are shipped in arrival order).
+
+We prove by exchange argument that k ≤ k*, i.e., greedy is optimal.
+
+**Key observation:** When greedy sends truck i, it contains boxes from position s_i to position e_i (in arrival order) such that:
+- The total weight of these boxes fits in capacity W
+- The total weight of these boxes PLUS the next box (at position e_i + 1) exceeds W
+
+Formally: Σ(w_j : s_i ≤ j ≤ e_i) ≤ W and Σ(w_j : s_i ≤ j ≤ e_i + 1) > W
+
+**Exchange argument:**
+
+Since boxes must be shipped in arrival order in any valid solution, consider the partition created by greedy: {boxes 1..m₁}, {boxes (m₁+1)..m₂}, ..., {boxes (m_{k-1}+1)..n}.
+
+For the first partition {boxes 1..m₁}:
+- These boxes cannot fit together with box (m₁ + 1) in a single truck: w₁ + ... + w_{m₁} + w_{m₁+1} > W
+- Therefore, in any solution, truck(s) carrying boxes 1..m₁ cannot also carry box m₁ + 1
+- This means any solution must "complete" the delivery of boxes 1..m₁ before starting on subsequent boxes
+
+By induction on the remaining boxes, the greedy choice (completing the first partition as much as possible before starting a new truck) is optimal. Any solution that deviates from this partition uses at least as many trucks.
+
+Therefore, the greedy algorithm minimizes the number of trucks. ∎
+
+---
+
+## Problem 2: Smallest Set of Intervals Containing Points [20 points]
+
+**Algorithm:**
+
+Input: Set of points {x₁, x₂, ..., x_n} on the real line
+Output: Minimum set of unit-length closed intervals covering all points
+
+1. Sort the points: x₁ ≤ x₂ ≤ ... ≤ x_n
+2. Let I = [] (list of intervals)
+3. i ← 1
+4. While i ≤ n:
+   - Create interval I_current ← [x_i, x_i + 1]
+   - Add I_current to I
+   - While i ≤ n and x_i ≤ x_i + 1 (all points still covered): i ← i + 1
+   - (This skips all points covered by I_current)
+5. Return I
+
+**Proof of Correctness:**
+
+We prove that this greedy algorithm produces an optimal solution using an exchange argument.
+
+**Claim:** For any set of points, there exists an optimal solution where one of the intervals has its left endpoint at some point's position.
+
+**Proof:** Consider any optimal solution O with intervals [a₁, a₁+1], [a₂, a₂+1], ..., [a_k, a_k+1]. If some interval [a_i, a_i+1] doesn't have a point at its left endpoint, we can shift it left until a point touches the left endpoint, without losing coverage. This transformation cannot increase the number of intervals, so we can assume OPT has this property.
+
+**Main argument:**
+
+Let G = {I₁, I₂, ..., I_k} be the greedy solution and O = {J₁, J₂, ..., J_{k*}} be an optimal solution.
+
+Our greedy algorithm chooses I₁ = [x₁, x₁+1], which:
+- Covers all points up to x₁ + 1
+- Is the optimal choice for covering x₁ (the leftmost uncovered point)
+  - Any interval covering x₁ must have left endpoint ≤ x₁
+  - To maximize coverage to the right, we choose left endpoint = x₁, giving [x₁, x₁+1]
+  - This covers the maximum possible range starting from x₁
+
+By the principle of optimality, any optimal solution covering x₁ covers at most the same set of points with one interval as our greedy choice.
+
+If O covers the same points up to x₁+1 with one interval, then removing these points from both solutions and applying induction:
+- The remaining problem (covering remaining points) requires at least k* - 1 intervals in any solution
+- Greedy solves the remaining problem optimally (by induction)
+- Therefore k = 1 + (k-1) ≤ 1 + (k* - 1) = k*
+
+If O uses fewer intervals than greedy for the same set of points, it contradicts the optimality of O.
+
+Therefore, the greedy algorithm produces an optimal solution. ∎
+
+---
+
+## Problem 3: All Spanning Trees with Kruskal's Algorithm [20 points]
+
+**Claim:** For each minimum spanning tree T of graph G, there exists a sorting of the edges such that Kruskal's algorithm returns T.
+
+**Proof:**
+
+Recall that Kruskal's algorithm:
+1. Sorts edges by weight in non-decreasing order
+2. For each edge in this order, adds it to the current forest if it doesn't create a cycle
+3. Stops when n-1 edges are added
+
+When multiple edges have equal weight, Kruskal's result depends on the order in which edges of equal weight are considered.
+
+**Construction of sorting:**
+
+Given any MST T of G, we construct a sorting as follows:
+
+Partition edges by weight: E_w₁, E_w₂, ..., E_w_m where edges in E_w_i all have weight w_i and w₁ < w₂ < ... < w_m.
+
+Sort the edges with the following rule:
+- All edges in E_w₁ come before all edges in E_w₂, etc. (by original weights)
+- Within each weight class E_w_i:
+  - Edges in T ∩ E_w_i come before edges in E_w_i \ T
+  - The order within T ∩ E_w_i is arbitrary
+  - The order within E_w_i \ T is arbitrary
+
+**Verification that Kruskal returns T:**
+
+When Kruskal processes edges in this order:
+
+1. **For edges in T ∩ E_w_i:**
+   - These are processed first within weight class w_i
+   - Each edge in T ∩ E_w_i doesn't create a cycle in T (since T is acyclic)
+   - Therefore, Kruskal adds each edge in T ∩ E_w_i to its forest
+
+2. **For edges in E_w_i \ T:**
+   - These are processed after all edges in T ∩ E_w_i
+   - Consider any edge e ∈ E_w_i \ T
+   - By the cycle property of MSTs: since e ∉ T, adding e to T creates a unique cycle C
+   - At least one edge in C \ {e} is not in the current forest (by construction of the proof)
+   - When Kruskal processes e, there is already a path connecting e's endpoints using edges from T
+   - Therefore, e creates a cycle and is correctly rejected by Kruskal
+
+3. **Result:**
+   - Kruskal adds exactly the edges in T
+   - Since T is an MST with the same total weight as any other MST, Kruskal's output is an MST
+   - Kruskal's output is exactly T
+
+Therefore, for any MST T, there exists an edge sorting that makes Kruskal return T. ∎
+
+---
+
+## Problem 4: Longest Oscillating Subsequence [20 points]
+
+**Definition:** A sequence is oscillating if elements alternate between increasing and decreasing:
+- Either: x₁ < x₂ > x₃ < x₄ > ... (down-up pattern)
+- Or: x₁ > x₂ < x₃ > x₄ < ... (up-down pattern)
+
+**Greedy Algorithm:**
+
+Input: Array A[1..n] of integers
+Output: Length of longest oscillating subsequence
+
+```
+if n ≤ 1: return n
+
+last_element ← A[1]
+length ← 1
+last_direction ← NONE  (indicates no comparison yet)
+
+for i ← 2 to n:
+    if last_direction = NONE:
+        if A[i] ≠ last_element:
+            last_element ← A[i]
+            if A[i] > A[i-1]:
+                last_direction ← UP
+            else:
+                last_direction ← DOWN
+            length ← length + 1
+    else if last_direction = UP:
+        // We need to go DOWN next
+        if A[i] < last_element:
+            last_element ← A[i]
+            last_direction ← DOWN
+            length ← length + 1
+    else:  // last_direction = DOWN
+        // We need to go UP next
+        if A[i] > last_element:
+            last_element ← A[i]
+            last_direction ← UP
+            length ← length + 1
+
+return length
+```
+
+**Proof of Correctness:**
+
+**Claim:** The greedy algorithm returns the maximum length of any oscillating subsequence.
+
+**Proof:**
+
+Let G be the length returned by greedy, and let O be the length of any optimal oscillating subsequence.
+
+We prove G ≥ O using the greedy choice property.
+
+**Key insight:** At each step, when the greedy algorithm selects an element to extend the oscillation, it picks the earliest element that continues the alternating pattern. This choice maximizes the number of future elements available for selection.
+
+**Exchange argument:**
+
+Suppose O selects a different set of indices j₁, j₂, ..., j_{|O|}, and let greedy select i₁, i₂, ..., i_{|G|}.
+
+Let k be the first position where greedy and O differ (if they differ at all). Specifically:
+- Up to position k-1, both greedy and O have selected the same elements
+- At position k, greedy selects element at index i_k, and O selects element at index j_k where j_k > i_k
+
+**Case 1:** j_k ≤ n and elements at both indices satisfy the oscillation pattern from position k-1:
+- Since i_k < j_k and both extend the oscillation, greedy's earlier choice leaves more elements available for future positions
+- We can replace j_k with i_k in O without breaking the oscillation pattern
+- This transformation leaves the count unchanged but brings O closer to greedy's choices
+
+**Case 2:** Continuing this exchange argument position by position:
+- Each time O makes a different choice than greedy, we can swap to greedy's (earlier) choice
+- These swaps maintain the oscillation property and don't reduce the length
+- Eventually, we transform O into an equivalent or shorter sequence than greedy
+
+By this exchange argument, any oscillating subsequence has length ≤ greedy's length.
+
+Therefore, the greedy algorithm finds the longest oscillating subsequence. ∎
+
+---
+
+## Problem 5: Coin Changing [20 points]
+
+### Part (a): Power-of-c Denominations
+
+**Given:** Coin denominations are c⁰, c¹, c², ..., c^k for integers c > 1 and k ≥ 1
+
+**Greedy Algorithm:**
+
+Input: Target amount n, denominations c⁰, c¹, ..., c^k
+Output: Minimum number of coins to make amount n
+
+```
+coins ← 0
+for i ← k down to 0:
+    coins ← coins + ⌊n / c^i⌋
+    n ← n mod c^i
+return coins
+```
+
+**Proof of Optimality:**
+
+We prove the greedy algorithm always yields an optimal solution.
+
+**Key insight:** The denominations c⁰, c¹, ..., c^k form a base-c number system. The greedy algorithm computes the base-c representation of n.
+
+**Theorem:** For any positive integer n, there exist unique non-negative integers a₀, a₁, ..., a_k with 0 ≤ a_i < c such that:
+n = a_k · c^k + a_{k-1} · c^{k-1} + ... + a₁ · c + a₀
+
+**Proof:**
+
+Suppose there exists another representation using coins from {c⁰, c¹, ..., c^k}:
+n = b_k · c^k + b_{k-1} · c^{k-1} + ... + b₁ · c + b₀
+
+where b_i are non-negative integers (not necessarily < c).
+
+**Claim:** For any representation with Σb_i > Σa_i (more coins), there exists a transformation that reduces the total coins.
+
+**Argument:** If any coefficient b_i ≥ c, we can write:
+- b_i · c^i = c · c^i + (b_i - c) · c^i = 1 · c^{i+1} + (b_i - c) · c^i
+
+This replaces c coins of denomination c^i with 1 coin of denomination c^{i+1}, reducing the total count by c - 1 > 0.
+
+By repeatedly applying this reduction, we transform any representation into one where each coefficient is < c.
+
+**Uniqueness:** When restricted to coefficients 0 ≤ b_i < c, the representation is unique (standard base-c property).
+
+**Conclusion:** The base-c representation (computed by greedy) is the unique representation with the minimum number of coins.
+
+Therefore, the greedy algorithm always yields an optimal solution for denominations that are powers of c. ∎
+
+### Part (b): Counterexample
+
+**Claim:** There exist coin denominations for which the greedy algorithm does not yield an optimal solution.
+
+**Counterexample:**
+
+Denominations: {1, 3, 4}
+Target amount: n = 6 cents
+
+**Greedy solution:**
+- Use 4 cents: leaves 2 cents remaining
+- Use 1 cent twice: leaves 0 cents
+- Total: **3 coins** (one 4-cent coin and two 1-cent coins)
+
+**Optimal solution:**
+- Use 3 cents twice: leaves 0 cents
+- Total: **2 coins** (two 3-cent coins)
+
+Since 2 < 3, the greedy algorithm (using 3 coins) does not produce an optimal solution (which uses 2 coins). ✓
+
+This counterexample satisfies the requirement that 1-cent coins are included (ensuring a solution exists for all values of n).