diff --git a/writeup.md b/writeup.md
index daaca40..5e55075 100644
--- a/writeup.md
+++ b/writeup.md
@@ -2,8 +2,214 @@
 
 ## Student Responses
 
-<!-- Write your solutions below. Add sections for each problem as needed. -->
-<!-- Use proper mathematical notation where applicable. -->
+---
 
-[Your solutions here]
+## Problem 1: Hashing with Chaining [20 Points]
 
+**Procedure:**
+
+1. Pick a slot $j$ uniformly at random from $\{1, \ldots, m\}$: $O(1)$ time.
+2. Pick an index $i$ uniformly at random from $\{1, \ldots, L\}$: $O(1)$ time.
+3. If $\text{len}(\text{chain}[j]) \geq i$, traverse chain $j$ to its $i$-th element and return it: $O(L)$ time.
+4. Otherwise, **reject** and go back to step 1.
+
+**Correctness (uniform distribution):**
+
+For any key $k$ stored at slot $j^*$ at position $i^*$ within its chain:
+
+$$\Pr[\text{key } k \text{ selected in one trial}] = \Pr[\text{pick slot } j^*] \cdot \Pr[\text{pick index } i^*] = \frac{1}{m} \cdot \frac{1}{L} = \frac{1}{mL}$$
+
+This probability is identical for all $n$ keys regardless of which slot or position they occupy. Therefore, conditioned on a trial succeeding (i.e., not being rejected), each key is equally likely to be returned, giving a uniform distribution over all $n$ keys.
+
+**Expected running time:**
+
+The probability that a trial succeeds (i.e., the chosen $(j, i)$ pair corresponds to an actual key) is:
+
+$$\Pr[\text{success}] = \frac{n}{mL} = \frac{\alpha}{L}$$
+
+since exactly $n$ of the $mL$ possible $(j, i)$ pairs correspond to actual stored keys.
+
+- Each **failed** trial costs $O(1)$ (just pick $j$ and $i$, check $\text{len}(\text{chain}[j])$, and reject).
+- The **successful** trial costs $O(L)$ to traverse up to $L$ elements.
+- The expected number of trials is $\frac{1}{\Pr[\text{success}]} = \frac{L}{\alpha}$ (geometric distribution).
+
+Total expected cost:
+
+$$O(1) \cdot \frac{L}{\alpha} + O(L) = O\!\left(\frac{L}{\alpha} + L\right) = O\!\left(L \cdot \left(1 + \frac{1}{\alpha}\right)\right)$$
+
+This matches the required bound. $\square$
+
+---
+
+## Problem 2: Longest-Probe Bound for Hashing [40 Points]
+
+### Part (a)
+
+**Claim:** For $i = 1, 2, \ldots, 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 all of the first $k$ probe positions it tries are already occupied. Before the $i$-th insertion, there are exactly $i - 1$ occupied slots and $m - (i-1)$ empty slots.
+
+With independent uniform permutation hashing, each probe sequence is an independent random permutation of $\{1, \ldots, m\}$. Given that the first $j$ probes were all occupied, the $(j+1)$-th probe is chosen uniformly from the remaining $m - j$ unprobed positions, of which at most $i - 1 - j$ are occupied. Thus:
+
+$$\Pr[\text{$j$-th probe is occupied} \mid \text{first } j-1 \text{ probes occupied}] = \frac{i-1-(j-1)}{m-(j-1)} = \frac{i-j}{m-j+1}$$
+
+So the probability that the first $k$ probes are all occupied is:
+
+$$\Pr[X_i > k] = \prod_{j=1}^{k} \frac{i-j}{m-j+1}$$
+
+We claim each factor is at most $1/2$. Since $n \leq m/2$, we have $i \leq n \leq m/2$, so $i - 1 \leq m/2 - 1 < m/2$. For each $j = 1, \ldots, k$:
+
+$$\frac{i - j}{m - j + 1} \leq \frac{i - 1}{m - 1 + 1} = \frac{i-1}{m} \leq \frac{m/2 - 1}{m} < \frac{1}{2}$$
+
+Wait, more carefully: we want $\frac{i - j}{m - j + 1} \leq \frac{1}{2}$, i.e., $2(i - j) \leq m - j + 1$. Since $i \leq m/2$, we have $2i \leq m$, so $2i - 2j \leq m - 2j \leq m - j + 1$ for $j \geq 1$. Thus each factor is $\leq 1/2$, and:
+
+$$\Pr[X_i > k] \leq \left(\frac{1}{2}\right)^k = 2^{-k} \qquad \square$$
+
+### Part (b)
+
+**Claim:** $\Pr[X_i > 2\log_2 n] = O(1/n^2)$.
+
+**Proof:**
+
+Setting $k = 2\log_2 n$ in part (a):
+
+$$\Pr[X_i > 2\log_2 n] \leq 2^{-2\log_2 n} = (2^{\log_2 n})^{-2} = n^{-2} = \frac{1}{n^2} = O\!\left(\frac{1}{n^2}\right) \qquad \square$$
+
+### Part (c)
+
+**Claim:** $\Pr[X > 2\log_2 n] = O(1/n)$, where $X = \max_{1 \leq i \leq n} X_i$.
+
+**Proof:**
+
+$$\Pr[X > 2\log_2 n] = \Pr\!\left[\bigcup_{i=1}^{n} \{X_i > 2\log_2 n\}\right]$$
+
+Applying the union bound:
+
+$$\leq \sum_{i=1}^{n} \Pr[X_i > 2\log_2 n] \leq n \cdot O\!\left(\frac{1}{n^2}\right) = O\!\left(\frac{1}{n}\right) \qquad \square$$
+
+### Part (d)
+
+**Claim:** $E[X] = O(\log_2 n)$.
+
+**Proof:**
+
+We use the identity $E[X] = \sum_{t=0}^{\infty} \Pr[X > t]$ and split the sum at threshold $t^* = 2\lfloor \log_2 n \rfloor$:
+
+$$E[X] = \sum_{t=0}^{t^*} \Pr[X > t] + \sum_{t=t^*+1}^{\infty} \Pr[X > t]$$
+
+**First sum:** Since $\Pr[X > t] \leq 1$, the first sum is at most $t^* + 1 = O(\log n)$.
+
+**Second sum:** For $t > t^*$, by union bound and part (a):
+
+$$\Pr[X > t] \leq \sum_{i=1}^{n} \Pr[X_i > t] \leq n \cdot 2^{-t}$$
+
+Therefore:
+
+$$\sum_{t=t^*+1}^{\infty} \Pr[X > t] \leq \sum_{t=t^*+1}^{\infty} n \cdot 2^{-t} = n \cdot \frac{2^{-(t^*+1)}}{1 - 1/2} = n \cdot 2^{-t^*}$$
+
+Since $t^* = 2\lfloor \log_2 n \rfloor \geq 2(\log_2 n - 1) = 2\log_2 n - 2$:
+
+$$n \cdot 2^{-t^*} \leq n \cdot 2^{-(2\log_2 n - 2)} = n \cdot \frac{4}{n^2} = \frac{4}{n} = O(1)$$
+
+Combining:
+
+$$E[X] = O(\log n) + O(1) = O(\log_2 n) \qquad \square$$
+
+---
+
+## Problem 3: Randomized Coloring [15 Points]
+
+**Algorithm:**
+
+Assign each vertex $v \in V$ a color $c(v)$ chosen independently and uniformly at random from $\{1, 2, 3\}$. This takes $O(|V|)$ time, which is polynomial.
+
+**Analysis:**
+
+For any edge $(u, v) \in E$, the probability that it is satisfied (i.e., $c(u) \neq c(v)$) is:
+
+$$\Pr[c(u) \neq c(v)] = 1 - \Pr[c(u) = c(v)]$$
+
+Since $c(u)$ and $c(v)$ are chosen independently and uniformly from $\{1, 2, 3\}$:
+
+$$\Pr[c(u) = c(v)] = \sum_{j=1}^{3} \Pr[c(u) = j] \cdot \Pr[c(v) = j] = 3 \cdot \frac{1}{3} \cdot \frac{1}{3} = \frac{1}{3}$$
+
+Therefore $\Pr[\text{edge $(u,v)$ satisfied}] = \frac{2}{3}$.
+
+Let $S$ be the random variable counting the number of satisfied edges. By linearity of expectation:
+
+$$E[S] = \sum_{(u,v) \in E} \Pr[(u,v) \text{ satisfied}] = \frac{2}{3}|E|$$
+
+**Bounding against $c^*$:**
+
+Since the optimal coloring satisfies at most $|E|$ edges (each edge is either satisfied or not), we have $c^* \leq |E|$. Therefore:
+
+$$E[S] = \frac{2}{3}|E| \geq \frac{2}{3} c^*$$
+
+The expected number of satisfied edges is at least $\frac{2}{3}c^*$, as required. $\square$
+
+---
+
+## Problem 4: Analysis of Selection Using Recurrence [25 Points]
+
+**Setting up the recurrence:**
+
+Let $T(n)$ be the worst-case expected number of comparisons for SELECT on an array of size $n$. Each call partitions the array using $n - 1$ comparisons. The pivot's rank $r$ is uniformly distributed in $\{1, \ldots, n\}$ (since the pivot is chosen uniformly at random and all elements are distinct).
+
+For a given $k$, the recursive subproblem has size:
+- $0$ if $r = k$ (pivot is the desired element),
+- $r - 1$ if $r > k$ (recurse on the left part),
+- $n - r$ if $r < k$ (recurse on the right part).
+
+In either case, the subproblem size is at most $\max(r-1, n-r)$. As an upper bound over all choices of $k$:
+
+$$T(n) \leq (n-1) + \frac{1}{n} \sum_{r=1}^{n} T(\max(r-1, n-r))$$
+
+**Simplifying the sum:**
+
+For $r$ from $1$ to $n$, the value $\max(r-1, n-r)$ takes each value from $\lfloor n/2 \rfloor$ to $n-1$ exactly twice (by symmetry: $r$ and $n+1-r$ give the same max). Therefore:
+
+$$\sum_{r=1}^{n} T(\max(r-1, n-r)) = 2\sum_{j=\lfloor n/2 \rfloor}^{n-1} T(j)$$
+
+So the recurrence becomes:
+
+$$T(n) \leq (n-1) + \frac{2}{n} \sum_{j=\lfloor n/2 \rfloor}^{n-1} T(j)$$
+
+**Proving $T(n) \leq 4n$ by induction:**
+
+**Base cases:** $T(0) = T(1) = 0 \leq 4 \cdot 1$. ✓
+
+**Inductive step (even $n = 2m$):** Assume $T(j) \leq 4j$ for all $j < n$. Then:
+
+$$\sum_{j=m}^{2m-1} j = m + (m+1) + \cdots + (2m-1) = \frac{m(3m-1)}{2}$$
+
+$$T(2m) \leq (2m-1) + \frac{2}{2m} \cdot 4 \cdot \frac{m(3m-1)}{2} = (2m-1) + 2(3m-1) = 8m - 3 < 8m = 4n \checkmark$$
+
+**Inductive step (odd $n = 2m+1$):**
+
+$$\sum_{j=m}^{2m} j = m + (m+1) + \cdots + 2m = \frac{3m(m+1)}{2}$$
+
+$$T(2m+1) \leq 2m + \frac{2}{2m+1} \cdot 4 \cdot \frac{3m(m+1)}{2} = 2m + \frac{12m(m+1)}{2(2m+1)}$$
+
+We verify $2m + \frac{6m(m+1)}{2m+1} \leq 4(2m+1) = 8m+4$:
+
+$$\frac{6m(m+1)}{2m+1} \leq 6m+4 \iff 6m(m+1) \leq (6m+4)(2m+1) = 12m^2 + 14m + 4$$
+
+$$6m^2 + 6m \leq 12m^2 + 14m + 4 \iff 0 \leq 6m^2 + 8m + 4 \checkmark$$
+
+So $T(n) \leq 4n$ for all $n$. ✓
+
+**Showing $c = 3$ is insufficient:**
+
+From the induction, we need $c \geq \frac{2(2m-1)}{m+1}$ for all $m \geq 1$ (from even $n = 2m$). For $m = 6$ ($n = 12$):
+
+$$\frac{2(11)}{7} = \frac{22}{7} \approx 3.14 > 3$$
+
+So $c = 3$ fails for $n = 12$.
+
+**Conclusion:**
+
+The requirement $c \geq \frac{2(2m-1)}{m+1}$ approaches $4$ as $m \to \infty$ (and is always strictly less than $4$ for finite $m$). Therefore, $c = 3$ is insufficient, while $c = 4$ is both sufficient and necessary.
+
+$$\boxed{c = 4}$$