diff --git a/writeup.md b/writeup.md
index 7d45f57..8e9c01b 100644
--- a/writeup.md
+++ b/writeup.md
@@ -2,8 +2,348 @@
 
 ## Student Responses
 
-<!-- Write your solutions below. Add sections for each problem as needed. -->
-<!-- Use proper mathematical notation where applicable. -->
+---
 
-[Your solutions here]
+## Problem 1: Radix Trees [20 points]
 
+### Part 1: Formal Definition [3 points]
+
+A **radix tree** for storing a set S of bit strings is a rooted tree T with the following properties:
+
+1. **Binary branching:** Each node v has at most two children: a left child (corresponding to bit 0) and a right child (corresponding to bit 1).
+
+2. **Membership flag:** Each node v has a boolean attribute v.member, which is TRUE if and only if the bit string represented by the path from the root to v belongs to S.
+
+3. **Implicit keys:** The key (bit string) associated with a node v is not stored explicitly. Instead, it is determined by the sequence of edge labels (0 for left, 1 for right) on the unique path from the root to v. The root represents the empty string ε.
+
+4. **No redundant leaves:** Every leaf node has v.member = TRUE. Internal nodes may have v.member = TRUE or FALSE. (A node with member = FALSE exists only because it lies on the path to some descendant with member = TRUE.)
+
+Formally, a bit string w = w₁w₂...wₖ belongs to S if and only if the node reached by starting at the root and following child w₁, then child w₂, ..., then child wₖ exists and has member = TRUE.
+
+---
+
+### Part 2: Pseudocode for Search and Insert [10 points]
+
+**RADIX-TREE-SEARCH(T, w):**
+
+```
+RADIX-TREE-SEARCH(T, w):
+    // w = w[1]w[2]...w[m] is a bit string of length m = |w|
+    node = T.root
+    for i = 1 to |w|:
+        if w[i] == 0:
+            node = node.left
+        else:
+            node = node.right
+        if node == NIL:
+            return FALSE
+    return node.member
+```
+
+**Time complexity justification:** The algorithm performs exactly |w| iterations of the for-loop. Each iteration does O(1) work: one comparison and one pointer traversal. The final check of node.member is O(1). Therefore, the total running time is **Θ(|w|)**.
+
+**RADIX-TREE-INSERT(T, w):**
+
+```
+RADIX-TREE-INSERT(T, w):
+    // w = w[1]w[2]...w[m] is a bit string of length m = |w|
+    node = T.root
+    for i = 1 to |w|:
+        if w[i] == 0:
+            if node.left == NIL:
+                node.left = new Node(member = FALSE, left = NIL, right = NIL)
+            node = node.left
+        else:
+            if node.right == NIL:
+                node.right = new Node(member = FALSE, left = NIL, right = NIL)
+            node = node.right
+    node.member = TRUE
+```
+
+**Time complexity justification:** The algorithm performs exactly |w| iterations of the for-loop. Each iteration does O(1) work: one comparison, possibly one node creation (which is O(1)), and one pointer traversal. Setting node.member = TRUE at the end is O(1). Therefore, the total running time is **Θ(|w|)**.
+
+Note: Both algorithms traverse exactly the path from the root to the node at depth |w|, performing constant work per level. Neither algorithm ever backtracks or visits additional nodes. Hence both run in Θ(|w|) time.
+
+---
+
+### Part 3: Sorting Bit Strings Using a Radix Tree [7 points]
+
+**Algorithm:**
+
+Given a set S of distinct bit strings whose lengths sum to n:
+
+1. **Build the radix tree:** Create an empty radix tree T (just a root with member = FALSE). For each string w ∈ S, call RADIX-TREE-INSERT(T, w).
+
+2. **Traverse the tree in pre-order, visiting 0-children before 1-children:** Perform a depth-first traversal starting from the root. At each node, first check if the node is a member (output its string if so), then recursively visit the left child (edge labeled 0), then recursively visit the right child (edge labeled 1). Maintain the current path string by appending the edge label when descending and removing it when backtracking.
+
+```
+RADIX-TREE-SORT(T):
+    result = empty list
+    path = empty string
+    TRAVERSE(T.root, path, result)
+    return result
+
+TRAVERSE(node, path, result):
+    if node == NIL:
+        return
+    if node.member == TRUE:
+        append path to result
+    TRAVERSE(node.left, path + "0", result)
+    TRAVERSE(node.right, path + "1", result)
+```
+
+**Correctness (lexicographic order):**
+
+The traversal produces strings in lexicographic order because:
+
+- **Rule (ii) — prefixes first:** Since we visit a node before its descendants (pre-order), if a string s is a prefix of a string s', then s is output before s'. This satisfies rule (ii) of lexicographic ordering: a shorter string that is a prefix of a longer string comes first.
+
+- **Rule (i) — 0 before 1:** At every node, we visit the left subtree (bit 0) before the right subtree (bit 1). This means that among two strings that first differ at position j, the one with bit 0 at position j is output first. Since 0 < 1, this satisfies rule (i).
+
+**Time complexity justification — Θ(n):**
+
+- **Insertion phase:** Each string wᵢ takes Θ(|wᵢ|) time to insert (as shown in Part 2). The total insertion time is Θ(Σᵢ |wᵢ|) = Θ(n).
+
+- **Traversal phase:** The traversal visits each node in the tree exactly once. The total number of nodes in the tree is at most n + 1 (the root plus at most one node created per bit across all insertions; shared prefixes only reduce this count). At each node, we do O(1) work (check membership, recursive calls). Thus the traversal takes O(number of nodes) = O(n) time. (Note: appending the current path to the result can be done in O(1) per node if we store strings as pointers into the path array, or the total copying cost across all output strings is Σ|wᵢ| = n, which is also O(n).)
+
+- **Total time: Θ(n) + O(n) = Θ(n).**
+
+The lower bound Ω(n) holds because we must read all n bits of input.
+
+---
+
+## Problem 2: Multisets [20 Points]
+
+### Part 1: Data Structure Design [10 points]
+
+**Data Structure:** An **augmented AVL tree** (keyed by element value) where each node stores additional information about the multiplicity of the element and the total count in its subtree.
+
+**Node structure:**
+- `key`: the element k
+- `count`: the number of occurrences of k in the multiset (multiplicity)
+- `subtree_total`: the sum of `count` values for all nodes in the subtree rooted at this node
+- `height`: the height of the subtree (for AVL balancing)
+- `left`, `right`: pointers to children
+
+The tree is ordered by key values (using the linear ordering of elements). We define `subtree_total(NIL) = 0`.
+
+**Invariant:** For every node v: `v.subtree_total = v.count + v.left.subtree_total + v.right.subtree_total`.
+
+**Operations:**
+
+**CREATE(S) — O(1):**
+Set S.root = NIL. This creates an empty multiset in O(1) time.
+
+**INSERT(S, k) — O(log n):**
+Search the AVL tree for key k.
+- *If k is found* at node v: Increment v.count by 1. Walk back up to the root, incrementing `subtree_total` by 1 for every ancestor of v (including v itself). No structural change to the tree. Time: O(log n) for the search + O(log n) for the ancestor updates = O(log n).
+- *If k is not found:* Insert a new node with key = k, count = 1, subtree_total = 1. Perform standard AVL rebalancing (rotations). After each rotation, update `subtree_total` for the O(1) affected nodes. Update `subtree_total` for all ancestors along the insertion path. Time: O(log n).
+
+Note: During AVL rotations, `subtree_total` can be recomputed in O(1) per rotation since each rotated node's `subtree_total` is just the sum of its children's `subtree_total` values plus its own `count`.
+
+**GETCOUNT(S, k) — O(log n):**
+Search the AVL tree for key k. If found at node v, return v.count. If not found, return 0. Time: O(log n) for the search.
+
+**DELETE(S, k) — O(log n):**
+Search the AVL tree for key k.
+- *If k is not found:* Do nothing (or report error).
+- *If k is found* at node v and v.count > 1: Decrement v.count by 1. Walk back up to the root, decrementing `subtree_total` by 1 for every ancestor (including v). Time: O(log n).
+- *If k is found* at node v and v.count = 1: Remove the node using standard AVL deletion (with rebalancing). Update `subtree_total` for all affected ancestors. Time: O(log n), using the known fact that AVL deletion takes O(log n) time. The `subtree_total` updates along the path and during rotations add only O(log n) overhead.
+
+**GETCOUNTS≥(S, k) — O(log n):**
+Return the total count of all elements ≥ k. Traverse from the root to a leaf, accumulating counts:
+
+```
+GETCOUNTS≥(S, k):
+    result = 0
+    node = S.root
+    while node ≠ NIL:
+        if node.key == k:
+            return result + node.count + node.right.subtree_total
+        else if node.key > k:
+            result = result + node.count + node.right.subtree_total
+            node = node.left
+        else:  // node.key < k
+            node = node.right
+    return result
+```
+
+**Justification:** At each step, we follow a single root-to-leaf path. When we encounter a node with key > k, all elements in its right subtree are also > k, so we add the node's count and its right subtree's total. When key < k, we go right. When key == k, we add the node's count and its right subtree's total, and we are done. Since the AVL tree has height O(log n), this traversal visits O(log n) nodes, doing O(1) work per node. Total time: **O(log n)**.
+
+---
+
+### Part 2: Extended Data Structure [10 points]
+
+**Additional Data Structure:** We maintain a **second augmented AVL tree** (the "count tree"), keyed by count values, alongside the primary tree from Part 1.
+
+**Count tree node structure:**
+- `key`: a count value c (a positive integer)
+- `frequency`: the number of unique elements in the multiset that have exactly this count
+- `subtree_freq`: the sum of `frequency` values for all nodes in the subtree
+- `height`, `left`, `right`: for AVL balancing
+
+**Invariant:** For every node u in the count tree: `u.subtree_freq = u.frequency + u.left.subtree_freq + u.right.subtree_freq`.
+
+The count tree has at most n nodes (one per distinct count value), and since there are at most n unique elements, there are at most n distinct count values. So operations on the count tree take O(log n) time.
+
+**Modified operations (INSERT and DELETE now also update the count tree):**
+
+**INSERT(S, k) — O(log n):**
+1. Search the primary tree for k.
+2. If k is found with current count = old_c:
+   - In the count tree, find node with key = old_c and decrement its frequency. If frequency becomes 0, delete this node from the count tree.
+   - Set new_c = old_c + 1. In the count tree, find node with key = new_c. If found, increment its frequency. If not found, insert a new node with key = new_c, frequency = 1.
+   - In the primary tree, set k's count to new_c and update subtree_total values.
+3. If k is not found:
+   - Insert k into the primary tree with count = 1.
+   - In the count tree, find node with key = 1. If found, increment its frequency. If not found, insert (key = 1, frequency = 1).
+4. Update subtree_freq values in the count tree along affected paths.
+5. **Total: O(log n)** for the primary tree operations + O(log n) for the count tree operations = O(log n).
+
+**DELETE(S, k) — O(log n):**
+1. Search the primary tree for k. If not found, do nothing.
+2. If found with current count = old_c:
+   - In the count tree, find node with key = old_c and decrement its frequency. If frequency becomes 0, delete this node.
+   - If old_c > 1: set new_c = old_c − 1. In the count tree, find or insert node with key = new_c and increment its frequency. Update k's count in the primary tree.
+   - If old_c = 1: remove k from the primary tree entirely.
+3. Update subtree_freq values in the count tree.
+4. **Total: O(log n).**
+
+**New operations:**
+
+**WITHCOUNT(S, c) — O(log n):**
+Search the count tree for key = c. If found at node u, return u.frequency. If not found, return 0. Time: O(log n) for the search.
+
+**FREQUENT(S, c) — O(log n):**
+Return the number of unique elements with count ≥ c. This is analogous to GETCOUNTS≥ but on the count tree, using subtree_freq instead of subtree_total:
+
+```
+FREQUENT(S, c):
+    result = 0
+    node = count_tree.root
+    while node ≠ NIL:
+        if node.key == c:
+            return result + node.frequency + node.right.subtree_freq
+        else if node.key > c:
+            result = result + node.frequency + node.right.subtree_freq
+            node = node.left
+        else:  // node.key < c
+            node = node.right
+    return result
+```
+
+**Justification:** Identical reasoning to GETCOUNTS≥ from Part 1. We traverse a single root-to-leaf path in the count tree (height O(log n)), doing O(1) work per node. When a node has key ≥ c, its right subtree also has keys ≥ c, so we accumulate frequency and the right child's subtree_freq. **Total time: O(log n).**
+
+**All operations from Part 1 (CREATE, GETCOUNT, GETCOUNTS≥) are unchanged** and still run in their specified time complexities.
+
+**Space:** O(n) for the primary tree + O(n) for the count tree = O(n) total, where n is the number of unique elements.
+
+---
+
+## Problem 3: AVL Trees: Height & Size [10 Points]
+
+**Claim:** An AVL tree with n nodes has height at most
+
+$$h \leq \frac{1}{\log_2 \varphi} \cdot \log_2(n + 2) + \left(\log_\varphi \sqrt{5} - 2\right)$$
+
+where φ = (1 + √5)/2 is the golden ratio. Numerically, this gives:
+
+**h ≤ 1.4404 · log₂(n + 2) − 0.3277**
+
+with c = 1/log₂(φ) ≈ 1.4404, k = 2, b = log_φ(√5) − 2 ≈ −0.3277.
+
+**Proof:**
+
+**Step 1: Recurrence for minimum number of nodes.**
+
+Using the convention that height = number of nodes on the longest root-to-leaf path, let N(h) denote the minimum number of nodes in an AVL tree of height h.
+
+- N(1) = 1 (a single node, which is both root and leaf).
+- N(2) = 2 (a root with one child).
+- For h ≥ 3: An AVL tree of height h has a root node whose two subtrees have heights that differ by at most 1. To minimize nodes, one subtree has height h − 1 and the other has height h − 2. Therefore:
+
+  N(h) = 1 + N(h − 1) + N(h − 2), for h ≥ 3.
+
+**Step 2: Relate N(h) to Fibonacci numbers.**
+
+Define F(h) = N(h) + 1. Then:
+- F(1) = N(1) + 1 = 2
+- F(2) = N(2) + 1 = 3
+- For h ≥ 3: F(h) = N(h) + 1 = 1 + N(h−1) + N(h−2) + 1 = (N(h−1) + 1) + (N(h−2) + 1) = F(h−1) + F(h−2).
+
+So F(h) satisfies the Fibonacci recurrence. Using the standard Fibonacci numbering where Fib(1) = 1, Fib(2) = 1, Fib(3) = 2, Fib(4) = 3, Fib(5) = 5, ..., we verify:
+
+- F(1) = 2 = Fib(3) ✓
+- F(2) = 3 = Fib(4) ✓
+- F(h) = F(h−1) + F(h−2) matches Fib(h+2) = Fib(h+1) + Fib(h) ✓
+
+Therefore **F(h) = Fib(h + 2)**, and so:
+
+**N(h) = Fib(h + 2) − 1.**
+
+**Step 3: Lower bound on Fibonacci numbers.**
+
+By the closed-form formula (Binet's formula):
+
+Fib(k) = (φ^k − ψ^k) / √5
+
+where φ = (1 + √5)/2 ≈ 1.618 and ψ = (1 − √5)/2 ≈ −0.618.
+
+Since |ψ| < 1, we have |ψ^k| < 1 for all k ≥ 1, and thus |ψ^k / √5| < 1/√5 < 1/2 for all k ≥ 1. Therefore:
+
+**Fib(k) > φ^k / √5 − 1/2, for all k ≥ 1.**
+
+**Step 4: Derive the height bound.**
+
+Since any AVL tree with n nodes and height h satisfies n ≥ N(h):
+
+n ≥ N(h) = Fib(h + 2) − 1
+
+So:
+
+n + 1 ≥ Fib(h + 2) > φ^(h+2) / √5 − 1/2
+
+Therefore:
+
+n + 3/2 > φ^(h+2) / √5
+
+Multiplying both sides by √5:
+
+√5 · (n + 3/2) > φ^(h+2)
+
+Since n + 3/2 ≤ n + 2, we can write the slightly looser but cleaner bound:
+
+√5 · (n + 2) > φ^(h+2)
+
+Taking log base 2 of both sides:
+
+log₂(√5) + log₂(n + 2) > (h + 2) · log₂(φ)
+
+Solving for h:
+
+h + 2 < [log₂(n + 2) + log₂(√5)] / log₂(φ)
+
+h < (1/log₂φ) · log₂(n + 2) + log₂(√5)/log₂(φ) − 2
+
+**Step 5: Compute the constants.**
+
+- φ = (1 + √5)/2 ≈ 1.6180
+- log₂(φ) ≈ 0.6942
+- c = 1/log₂(φ) = log_φ(2) ≈ 1.4404
+- log₂(√5) = (1/2)log₂(5) ≈ 1.1610
+- log₂(√5)/log₂(φ) = log_φ(√5) ≈ 1.6722
+- b = log_φ(√5) − 2 ≈ −0.3277
+
+**Step 6: Final result.**
+
+$$\boxed{h \leq \frac{1}{\log_2 \varphi} \cdot \log_2(n + 2) + (\log_\varphi\!\sqrt{5} - 2) \approx 1.4404 \cdot \log_2(n + 2) - 0.3277}$$
+
+where c = 1/log₂(φ) ≈ 1.4404, k = 2, and b = log_φ(√5) − 2 ≈ −0.3277.
+
+**Verification with small cases:**
+- h = 1, N(1) = 1, n ≥ 1: bound gives h ≤ 1.4404 · log₂(3) − 0.328 ≈ 1.4404 · 1.585 − 0.328 ≈ 1.955. So h = 1 ≤ 1.955 ✓
+- h = 2, N(2) = 2, n ≥ 2: bound gives h ≤ 1.4404 · log₂(4) − 0.328 = 1.4404 · 2 − 0.328 = 2.553. So h = 2 ≤ 2.553 ✓
+- h = 3, N(3) = 4, n ≥ 4: bound gives h ≤ 1.4404 · log₂(6) − 0.328 ≈ 1.4404 · 2.585 − 0.328 ≈ 3.396. So h = 3 ≤ 3.396 ✓
+- h = 7, N(7) = 32, n ≥ 32: bound gives h ≤ 1.4404 · log₂(34) − 0.328 ≈ 1.4404 · 5.087 − 0.328 ≈ 6.998. So h = 7 ≤ 6.998? Let me check: N(7) = Fib(9) − 1 = 34 − 1 = 33. So n ≥ 33: bound gives 1.4404 · log₂(35) − 0.328 ≈ 1.4404 · 5.129 − 0.328 ≈ 7.058. So h = 7 ≤ 7.058 ✓
+
+This confirms the bound is tight (close to being achieved by worst-case AVL trees), which demonstrates it is indeed a strong upper bound.