diff --git a/writeup.md b/writeup.md
index daaca40..c048f66 100644
--- a/writeup.md
+++ b/writeup.md
@@ -1,9 +1,254 @@
 # COMP382 Homework 4
 
-## Student Responses
+## Problem 1: Hashing with Chaining [20 Points]
 
-<!-- Write your solutions below. Add sections for each problem as needed. -->
-<!-- Use proper mathematical notation where applicable. -->
+**Setup:** We have n keys stored in a hash table of size m with chaining. We know the length l_j of each chain and the length L of the longest chain. We want to select a key uniformly at random in expected time O(L(1 + 1/α)), where α = n/m.
 
-[Your solutions here]
+**Algorithm (Rejection Sampling):**
 
+```
+UNIFORM-RANDOM-KEY(H, m, L):
+  repeat
+    1. Pick a slot j uniformly at random from {0, 1, ..., m-1}.
+    2. Pick an integer k uniformly at random from {1, 2, ..., L}.
+    3. If k ≤ l_j (the length of chain at slot j):
+         Walk to the k-th element in chain j and return it.
+    // Otherwise (k > l_j), reject and repeat.
+```
+
+**Correctness (Uniform Selection):**
+
+Consider any key x stored at position p in the chain at slot s (so 1 ≤ p ≤ l_s). In a single trial, x is selected if and only if j = s and k = p. The probability of this is:
+
+P(select x in one trial) = P(j = s) · P(k = p) = (1/m)(1/L)
+
+This probability is the same for every key in the table, regardless of which slot it is in or its position in the chain. Therefore, conditioned on acceptance, each of the n keys is equally likely to be returned. The algorithm selects a key uniformly at random.
+
+**Expected Running Time:**
+
+The probability of accepting (returning a key) in a single trial is:
+
+P(accept) = Σ_{j=0}^{m-1} P(j selected) · P(k ≤ l_j) = Σ_{j=0}^{m-1} (1/m)(l_j/L) = (1/(mL)) Σ_{j=0}^{m-1} l_j = n/(mL) = α/L
+
+So the expected number of trials until acceptance is L/α.
+
+Now we analyze the cost per trial:
+- **Rejection cost:** When k > l_j, the trial costs O(1) time (picking two random numbers and comparing k with l_j, which we know).
+- **Acceptance cost:** When k ≤ l_j, we walk to position k in the chain, which takes O(k) ≤ O(L) time.
+
+We accept exactly once (the last trial). All other trials are rejections. Therefore:
+
+E[total time] = (expected number of rejections) · O(1) + O(L)
+             = (L/α - 1) · O(1) + O(L)
+             = O(L/α) + O(L)
+             = O(L(1/α + 1))
+             = **O(L(1 + 1/α))**
+
+This matches the required bound. ∎
+
+---
+
+## Problem 2: Longest-Probe Bound for Hashing [40 Points]
+
+**Setup:** Open-addressed hash table of size m with n ≤ m/2 items, using independent uniform permutation hashing.
+
+### Part (a)
+
+**Claim:** For i = 1, 2, ..., n, the probability that the i-th insertion requires strictly more than k probes is at most 2^(-k).
+
+**Proof:**
+
+The i-th insertion requires more than k probes if and only if the first k probed positions are all occupied. When inserting the i-th element, there are i - 1 elements already in the table. Under uniform permutation hashing, the probe sequence is a random permutation of all m slots.
+
+P(X_i > k) = P(first k probes all hit occupied slots)
+            = ((i-1)/m) · ((i-2)/(m-1)) · ((i-3)/(m-2)) · ... · ((i-k)/(m-k+1))
+            = ∏_{j=0}^{k-1} (i - 1 - j)/(m - j)
+
+If i - 1 < k, then one of the numerators is zero or negative, so P(X_i > k) = 0 ≤ 2^(-k). ✓
+
+If i - 1 ≥ k, we bound each factor. Since i ≤ n ≤ m/2, for each j = 0, 1, ..., k-1:
+
+(i - 1 - j)/(m - j) ≤ (m/2 - 1 - j)/(m - j) = (m - 2 - 2j)/(2(m - j))
+
+Since m - 2 - 2j = (m - j) - (j + 2) < m - j, we have:
+
+(m - 2 - 2j)/(2(m - j)) < (m - j)/(2(m - j)) = 1/2
+
+Therefore each factor is strictly less than 1/2, and:
+
+P(X_i > k) = ∏_{j=0}^{k-1} (i - 1 - j)/(m - j) < (1/2)^k = 2^(-k) ∎
+
+### Part (b)
+
+**Claim:** P(X_i > 2 log₂ n) = O(1/n²).
+
+**Proof:**
+
+Setting k = 2 log₂ n in the result from Part (a):
+
+P(X_i > 2 log₂ n) ≤ 2^(-2 log₂ n) = (2^(log₂ n))^(-2) = n^(-2) = 1/n²
+
+Therefore P(X_i > 2 log₂ n) ≤ 1/n² = O(1/n²). ∎
+
+### Part (c)
+
+**Claim:** P(X > 2 log₂ n) = O(1/n), where X = max_{1 ≤ i ≤ n} X_i.
+
+**Proof:**
+
+By the union bound:
+
+P(X > 2 log₂ n) = P(∃ i ∈ {1,...,n} : X_i > 2 log₂ n)
+                 ≤ Σ_{i=1}^{n} P(X_i > 2 log₂ n)
+                 ≤ n · (1/n²)         [by Part (b)]
+                 = 1/n
+                 = O(1/n) ∎
+
+### Part (d)
+
+**Claim:** E[X] = O(log₂ n).
+
+**Proof:**
+
+We use the tail-sum formula for expectation of a non-negative integer-valued random variable:
+
+E[X] = Σ_{k=0}^{∞} P(X > k)
+
+We split this sum at t = ⌊2 log₂ n⌋:
+
+E[X] = Σ_{k=0}^{⌊2 log₂ n⌋} P(X > k) + Σ_{k=⌊2 log₂ n⌋+1}^{∞} P(X > k)
+
+**First sum:** Each probability is at most 1, so:
+
+Σ_{k=0}^{⌊2 log₂ n⌋} P(X > k) ≤ ⌊2 log₂ n⌋ + 1 ≤ 2 log₂ n + 1
+
+**Second sum:** For k > 2 log₂ n, we apply the union bound with Part (a):
+
+P(X > k) ≤ Σ_{i=1}^{n} P(X_i > k) ≤ n · 2^(-k)
+
+Therefore:
+
+Σ_{k=⌊2 log₂ n⌋+1}^{∞} P(X > k) ≤ Σ_{k=⌊2 log₂ n⌋+1}^{∞} n · 2^(-k)
+    = n · 2^{-(⌊2 log₂ n⌋+1)} · Σ_{j=0}^{∞} 2^(-j)
+    = n · 2^{-(⌊2 log₂ n⌋+1)} · 2
+
+Since ⌊2 log₂ n⌋ ≥ 2 log₂ n - 1:
+
+    ≤ 2n · 2^{-(2 log₂ n - 1 + 1)}
+    = 2n · 2^{-2 log₂ n}
+    = 2n · n^{-2}
+    = 2/n
+
+Combining both sums:
+
+E[X] ≤ (2 log₂ n + 1) + 2/n = O(log₂ n) ∎
+
+---
+
+## Problem 3: Randomized Coloring [15 Points]
+
+**Algorithm:**
+
+```
+RANDOM-3-COLOR(G = (V, E)):
+  For each vertex v ∈ V:
+    Assign color(v) ← uniform random choice from {1, 2, 3} (independently)
+  Return the coloring.
+```
+
+This runs in O(|V|) time, which is polynomial.
+
+**Analysis:**
+
+Consider any edge (u, v) ∈ E. Since color(u) and color(v) are chosen independently and uniformly from {1, 2, 3}:
+
+P(edge (u,v) is satisfied) = P(color(u) ≠ color(v))
+                            = 1 - P(color(u) = color(v))
+                            = 1 - 3 · (1/3)²
+                            = 1 - 1/3
+                            = 2/3
+
+Let S denote the number of satisfied edges. By linearity of expectation:
+
+E[S] = Σ_{(u,v) ∈ E} P(color(u) ≠ color(v)) = (2/3)|E|
+
+Since c* is the maximum number of satisfied edges over all 3-colorings, and no coloring can satisfy more edges than exist in the graph:
+
+c* ≤ |E|
+
+Therefore:
+
+E[S] = (2/3)|E| ≥ (2/3)c*
+
+The randomized algorithm produces a 3-coloring whose expected number of satisfied edges is at least (2/3)c*. ∎
+
+---
+
+## Problem 4: Analysis of Selection Using Recurrence [25 Points]
+
+**Goal:** Find the smallest integer constant c such that T(n) ≤ cn for all n, where T(n) is the expected number of comparisons performed by SELECT.
+
+**Setting up the recurrence:**
+
+When SELECT is called on an array of size n, the pivot is chosen uniformly at random. PARTITION uses n - 1 comparisons. After partitioning, the pivot ends up at some rank r (equally likely to be any value in {1, ..., n}), and we recurse on one side.
+
+For a specific rank-k query, when the pivot has rank r:
+- If r = k: we are done (no further recursion).
+- If r > k: we recurse on the left subarray of size r - 1.
+- If r < k: we recurse on the right subarray of size n - r.
+
+To find the worst case over k, consider k = ⌈n/2⌉ (the median query). This maximizes the expected recursive subproblem size because both the left and right recursions produce large subproblems.
+
+For k = n/2 (assuming n is even):
+- When r > k: subproblem sizes are r - 1 = n/2, n/2+1, ..., n-1 (for r = n/2+1, ..., n).
+- When r < k: subproblem sizes are n - r = n/2+1, n/2+2, ..., n-1 (for r = 1, ..., n/2-1).
+
+Size n/2 appears once, and each size from n/2+1 to n-1 appears twice. This gives the upper bound:
+
+T(n) ≤ (n - 1) + (2/n) Σ_{j=⌈n/2⌉}^{n-1} T(j)
+
+**Solving the recurrence by substitution:**
+
+We claim T(n) ≤ cn for all n ≥ 1. Assume inductively that T(j) ≤ cj for all j < n. Then:
+
+T(n) ≤ (n - 1) + (2/n) Σ_{j=⌈n/2⌉}^{n-1} cj
+     = (n - 1) + (2c/n) Σ_{j=⌈n/2⌉}^{n-1} j
+
+**Computing the sum** (for n even, with ⌈n/2⌉ = n/2):
+
+Σ_{j=n/2}^{n-1} j = Σ_{j=1}^{n-1} j - Σ_{j=1}^{n/2-1} j
+                   = n(n-1)/2 - (n/2 - 1)(n/2)/2
+                   = n(n-1)/2 - (n² - 2n)/8
+                   = (4n(n-1) - n² + 2n) / 8
+                   = (4n² - 4n - n² + 2n) / 8
+                   = (3n² - 2n) / 8
+
+Substituting:
+
+T(n) ≤ (n - 1) + (2c/n) · (3n² - 2n)/8
+     = (n - 1) + c(3n - 2)/4
+
+For the induction to go through, we need:
+
+(n - 1) + c(3n - 2)/4 ≤ cn
+
+Rearranging:
+
+n - 1 ≤ cn - 3cn/4 + c/2 = cn/4 + c/2 = c(n + 2)/4
+
+So: c ≥ 4(n - 1)/(n + 2)
+
+**Checking what values of c work:** Since 4(n-1)/(n+2) is increasing in n and approaches 4 as n → ∞ (but is strictly less than 4 for all finite n), we need c ≥ 4. Specifically:
+
+- For c = 3: The inequality requires 3 ≥ 4(n-1)/(n+2), i.e., 3n + 6 ≥ 4n - 4, i.e., n ≤ 10. This fails for n > 10, so c = 3 does not work.
+- For c = 4: The inequality requires 4 ≥ 4(n-1)/(n+2), i.e., 4n + 8 ≥ 4n - 4, i.e., 8 ≥ -4. This is always true. ✓
+
+**Verification with c = 4:**
+
+(n - 1) + 4(3n - 2)/4 = (n - 1) + (3n - 2) = 4n - 3 ≤ 4n ✓
+
+**Base case:** T(1) = 0 ≤ 4 · 1 = 4. ✓
+
+Therefore, by induction, T(n) ≤ 4n for all n ≥ 1, and since c = 3 fails for large n:
+
+**The smallest integer constant is c = 4.** ∎