diff --git a/writeup.md b/writeup.md
index 7d45f57..c138111 100644
--- a/writeup.md
+++ b/writeup.md
@@ -2,8 +2,444 @@
 
 ## 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 of Radix Tree [3 points]
+
+A **radix tree** is a rooted tree data structure defined as follows:
+
+**Definition:** A radix tree T is a rooted tree where:
+- Each node v has a label edge_label(v) representing a substring (or bit string) on the edge from its parent to v. The root node has no incoming edge and no label.
+- Each node v has a boolean flag is_terminal(v) indicating whether the path from the root to v represents a string in the set S.
+- From any node, there is at most one outgoing edge with a label beginning with any particular character/bit.
+- The concatenation of all edge labels along the path from the root to any node v represents the string corresponding to v.
+- A node can have multiple children, each with an outgoing edge labeled with a different character/bit string.
+
+More precisely, T = (V, E, label, is_terminal) where:
+- V is a set of nodes
+- E is a set of directed edges from parent to child
+- label: E → Σ* maps edges to strings over alphabet Σ (in this case Σ = {0, 1})
+- is_terminal: V → {true, false} marks which nodes represent complete strings in the set
+
+---
+
+### Part 2: Pseudocode for Search and Insert [10 points]
+
+#### RADIX-TREE-SEARCH(T, w)
+```
+Algorithm: RADIX-TREE-SEARCH(T, w)
+Input: Radix tree T, bit string w
+Output: true if w is in T, false otherwise
+
+1. current_node = T.root
+2. position = 0  // position in w
+3.
+4. while position < length(w):
+5.     // Find an outgoing edge from current_node that matches w[position:]
+6.     found_edge = false
+7.     for each edge e from current_node to child v:
+8.         edge_string = label(e)
+9.         // Check if w[position:] starts with edge_string
+10.        if length(edge_string) ≤ length(w) - position:
+11.            match = true
+12.            for i = 0 to length(edge_string) - 1:
+13.                if w[position + i] ≠ edge_string[i]:
+14.                    match = false
+15.                    break
+16.            if match:
+17.                position = position + length(edge_string)
+18.                current_node = v
+19.                found_edge = true
+20.                break
+21.
+22.    if not found_edge:
+23.        return false  // No matching path
+24.
+25. return is_terminal(current_node)
+```
+
+#### RADIX-TREE-INSERT(T, w)
+```
+Algorithm: RADIX-TREE-INSERT(T, w)
+Input: Radix tree T, bit string w
+Output: Modifies T to include w
+
+1. current_node = T.root
+2. position = 0  // position in w
+3.
+4. while position < length(w):
+5.     // Find an outgoing edge from current_node that may match w[position:]
+6.     matching_edge = null
+7.     matching_child = null
+8.     for each edge e from current_node to child v:
+9.         edge_string = label(e)
+10.        // Check for any match with w[position:]
+11.        if length(edge_string) > 0 and length(w) - position > 0:
+12.            if w[position] = edge_string[0]:
+13.                matching_edge = e
+13.                matching_child = v
+14.                break
+15.
+16.    if matching_edge = null:
+17.        // No edge matches: create new edge and leaf
+18.        new_leaf = CreateNode()
+19.        is_terminal(new_leaf) = true
+20.        new_edge = CreateEdge(current_node, new_leaf, w[position:])
+21.        AddEdge(T, new_edge)
+22.        return
+23.
+24.    edge_string = label(matching_edge)
+25.
+26.    // Find longest common prefix
+27.    lcp_length = 0
+28.    for i = 0 to min(length(edge_string), length(w) - position) - 1:
+29.        if edge_string[i] = w[position + i]:
+30.            lcp_length = lcp_length + 1
+31.        else:
+32.            break
+33.
+34.    if lcp_length = length(edge_string):
+35.        // Edge label is completely matched
+36.        position = position + lcp_length
+37.        current_node = matching_child
+38.
+39.    else:
+40.        // Need to split the edge
+41.        split_node = CreateNode()
+42.        is_terminal(split_node) = false
+43.
+44.        // Change existing edge to only contain matched part
+45.        label(matching_edge) = edge_string[0 : lcp_length]
+46.        old_parent = current_node
+47.        RemoveEdge(T, matching_edge)
+47.        new_edge1 = CreateEdge(old_parent, split_node, edge_string[0:lcp_length])
+48.        AddEdge(T, new_edge1)
+49.
+50.        // Create edge from split_node to old child with remainder
+51.        new_edge2 = CreateEdge(split_node, matching_child, edge_string[lcp_length:])
+52.        AddEdge(T, new_edge2)
+53.
+54.        // Handle remaining part of w
+55.        remaining_w = w[position + lcp_length:]
+56.        if length(remaining_w) > 0:
+56.            new_leaf = CreateNode()
+57.            is_terminal(new_leaf) = true
+58.            new_edge3 = CreateEdge(split_node, new_leaf, remaining_w)
+59.            AddEdge(T, new_edge3)
+60.        else:
+61.            is_terminal(split_node) = true
+62.        return
+63.
+64. is_terminal(current_node) = true
+```
+
+#### Time Complexity Justification
+
+**RADIX-TREE-SEARCH(T, w):**
+- The algorithm traverses from the root following edges that match prefixes of w.
+- At each step (lines 4-23), we match an edge label character-by-character with the remaining part of w.
+- Each character of w is examined exactly once across all edges traversed.
+- Since the total length of edge labels concatenated along any root-to-node path equals the length of the string represented at that node, we traverse edges with total label length |w|.
+- The while loop iterates as long as we haven't consumed all of w.
+- Total work: Θ(|w|) for character comparisons, plus O(degree) per node for finding the matching edge. Since the tree is compact (no internal nodes with single children except possibly at string terminations), this is Θ(|w|).
+- **Time complexity: Θ(|w|)**
+
+**RADIX-TREE-INSERT(T, w):**
+- Similar to search, we traverse edges matching w, which takes Θ(|w|) character comparisons.
+- When we need to split an edge (lines 40-62), we create new nodes and edges, but this is O(1) amortized per edge split, and there is at most one split.
+- All character comparisons and node/edge operations are proportional to |w|.
+- **Time complexity: Θ(|w|)**
+
+---
+
+### Part 3: Lexicographic Sorting Using Radix Tree [7 points]
+
+#### Algorithm
+
+**Step 1: Build the Radix Tree**
+Insert all strings from the set S into an initially empty radix tree. For each string s ∈ S, call RADIX-TREE-INSERT(T, s).
+
+**Step 2: In-order Traversal**
+Perform an in-order depth-first traversal of the radix tree. At each node v where is_terminal(v) = true, output the string represented by the path from the root to v.
+
+#### Why This Works (Correctness)
+
+The radix tree maintains strings in a compressed trie structure where the path from root to any node represents a unique string. The in-order traversal works as follows:
+
+- Edges from any node are naturally ordered by their first character (and recursively by subsequent characters).
+- When we visit children in lexicographic order of their incoming edge labels, we visit all strings in lexicographic order.
+- Since the tree is a trie variant, the lexicographic order of the paths (obtained by concatenating edge labels) equals the lexicographic order of strings.
+- For example, if a node has children with edges labeled "0" and "1", we visit the "0" subtree before the "1" subtree, ensuring strings starting with 0 come before strings starting with 1.
+
+#### Time Complexity Justification
+
+**Building the radix tree:**
+- For each string s ∈ S, RADIX-TREE-INSERT takes Θ(|s|) time.
+- Total time: Σ_{s ∈ S} Θ(|s|) = Θ(n), where n is the sum of all string lengths.
+
+**In-order traversal:**
+- We visit each node in the radix tree exactly once.
+- At each node, we examine the edge labels to determine visit order.
+- The number of nodes in the radix tree is at most 1 + Σ_{s ∈ S} 1 = O(|S|) (one node per unique string plus internal nodes).
+- More importantly, the total work during traversal is proportional to reading the edge labels, which sums to Θ(n) (since each character of each string appears in exactly one edge label).
+- We also do a constant amount of work per node for pointer following and ordering.
+
+**Total time complexity: Θ(n)**
+
+The algorithm is optimal because any comparison-based sorting must examine all characters, and we do exactly that by building and traversing the tree, without any wasted comparisons.
+
+---
+
+## Problem 2: Multisets [20 points]
+
+### Part 1: Multiset Data Structure with Basic Operations [10 points]
+
+#### Data Structure Design
+
+**Core Structure:**
+- Use a **balanced binary search tree (AVL or Red-Black tree)** as the primary data structure.
+- Each node in the tree stores:
+  - `element`: the actual element from K (the key for tree ordering)
+  - `count`: the multiplicity of this element in the multiset (integer ≥ 1)
+  - `subtree_sum`: the sum of counts in the subtree rooted at this node (augmented information)
+
+**Layout:**
+```
+Node structure:
+├── element (the key)
+├── count (multiplicity)
+├── subtree_sum (sum of counts in subtree)
+├── left (pointer to left child)
+├── right (pointer to right child)
+└── height (for AVL balancing)
+```
+
+The tree is ordered by element value (using the linear order on K). Nodes are augmented with subtree_sum to support range queries.
+
+#### Operation Implementations
+
+**CREATE(S):**
+- Initialize an empty tree with no nodes.
+- Time: O(1)
+
+**INSERT(S, k):**
+- Perform a standard BST search for element k.
+- If k is found: increment its count by 1, then update subtree_sum values for all ancestors.
+- If k is not found: create a new node with element=k, count=1, subtree_sum=1, and insert it into the tree, then rebalance (AVL rotations) and update subtree_sum for all affected nodes.
+- Time: O(log n) for BST search + O(log n) for rebalancing and updating subtree_sum values = O(log n)
+
+**GETCOUNT(S, k):**
+- Perform a standard BST search for element k starting from the root.
+- If k is found, return its count. If not found, return 0.
+- Time: O(log n) for BST search
+
+**DELETE(S, k):**
+- Perform a BST search for element k.
+- If k is not found, no action needed (or return error).
+- If k is found: decrement its count by 1.
+- If count becomes 0, remove the node from the tree (using standard BST node deletion) and rebalance.
+- Update subtree_sum for all affected ancestors.
+- Time: O(log n) by the given AVL tree deletion guarantee
+
+**GETCOUNTS≥(S, k):**
+- Perform a tree traversal starting from the root, accumulating counts of all elements ≥ k.
+- Starting at the root:
+  - If current node's element < k: recursively search only the right subtree (all elements in left subtree are < k).
+  - If current node's element ≥ k: add current node's count to the result, recursively search the left subtree (which has elements < current but possibly ≥ k), and recursively search the right subtree.
+  - Use subtree_sum to optimize: if we're at a node with element ≥ k, we can add the entire left subtree_sum + current count, then search right.
+- More efficient approach: At each node, if element ≥ k, add count + (left subtree's subtree_sum) to result, then go right. If element < k, just go right.
+- Time: O(log n) by visiting at most O(log n) nodes on a path from root to a leaf, with O(1) work per node.
+
+---
+
+### Part 2: Extended Multiset with Frequency Queries [10 points]
+
+#### Data Structure Extension
+
+**Build on Part 1 structure and add:**
+- A secondary **balanced BST T_freq** where each node stores:
+  - `count_value`: a count c (number of occurrences)
+  - `frequency`: the number of distinct elements in the multiset with exactly count_value occurrences
+  - Nodes are ordered by count_value
+
+**Maintaining Consistency:**
+- When we UPDATE the count of an element in the primary tree:
+  1. If the old count was c_old, decrement frequency[c_old] in T_freq by 1 (and remove the node if frequency becomes 0).
+  2. If the new count is c_new, increment frequency[c_new] in T_freq by 1 (create a new node if needed).
+
+**Example:** If we start with multiset {a, b, b, c, c, c}, the primary tree has (a:1), (b:2), (c:3). The secondary tree T_freq has (1:1) meaning "1 element has count 1", (2:1) meaning "1 element has count 2", (3:1) meaning "1 element has count 3".
+
+#### Operation Implementations (Building on Part 1)
+
+All operations from Part 1 remain unchanged in the primary tree, except we also update T_freq:
+
+**INSERT(S, k):**
+- [Same as Part 1, but after modifying count of k]
+- If this was a new insertion (count goes from 0 to 1): decrement frequency[0] (if tracking) and increment frequency[1].
+- If count incremented (e.g., from 2 to 3): decrement frequency[2] and increment frequency[3].
+- Time: O(log n) primary tree + O(log m) secondary tree = O(log n) where m ≤ n is the number of distinct counts
+
+**DELETE(S, k):**
+- [Same as Part 1, but after modifying count of k]
+- After decrementing the count, update T_freq accordingly (decrement old count's frequency, increment new count's frequency).
+- Time: O(log n)
+
+**GETCOUNT(S, k):**
+- [Same as Part 1]
+- Time: O(log n)
+
+**GETCOUNTS≥(S, k):**
+- [Same as Part 1]
+- Time: O(log n)
+
+**WITHCOUNT(S, c):**
+- Search T_freq for the node with count_value = c.
+- If found, return its frequency. If not found, return 0.
+- Time: O(log m) = O(log n) where m is the number of distinct counts (at most n)
+
+**FREQUENT(S, c):**
+- Find the node in T_freq with count_value = c.
+- Perform a range sum query: sum all frequencies for count_value ≥ c.
+- Use a similar approach as GETCOUNTS≥ in Part 1: traverse T_freq, accumulating frequencies of all count values ≥ c. Augment T_freq nodes with `subtree_frequency_sum` to support this in O(log m) time.
+- Time: O(log m) = O(log n)
+
+---
+
+## Problem 3: AVL Trees: Height & Size [10 points]
+
+### Best Upper Bound on AVL Tree Height
+
+**Result:** If an AVL tree has n nodes, then its height h satisfies:
+$$h \leq \lfloor 1.4405 \log_2(n+1) \rfloor$$
+
+Or more precisely, **h ≤ log_φ(√5(n+1)) ≈ 1.4405 log_2(n+1)**, where φ = (1+√5)/2 is the golden ratio.
+
+In the form c·log₂(n+k) + b, we have:
+$$h \leq 1.44 \log_2(n+1) + 0.328$$
+
+or more conservatively: **h ≤ 1.45 log₂(n+2)**
+
+---
+
+### Detailed Justification
+
+#### Step 1: Characterize Minimum-Size AVL Trees
+
+For an AVL tree of height h, we want to determine the **minimum number of nodes** N(h) needed to achieve height h.
+
+**Definition by recurrence:**
+- N(0) = 1 (a single node has height 0 under the definition where height = number of nodes in longest path; adjust: if height = 0 means a leaf, then N(0)=1, N(1)=2)
+  - Actually, let's be careful: the problem states "height of a tree is the number of nodes in the longest path from the root to a leaf."
+  - So a single node (leaf) has height 1.
+  - A tree with root and two leaves has height 2.
+
+**Re-defining with the given height definition:**
+Let h be the height (number of nodes in longest path, including root and leaf).
+- h = 1: single node, N(1) = 1
+- h = 2: root with at least one child, minimum is root + 1 child (which is a leaf), so N(2) = 2
+- h ≥ 3: an AVL tree of height h has a root with two subtrees. To be AVL-balanced, the heights of the two subtrees differ by at most 1.
+  - To minimize nodes while maximizing height h, we want one subtree to have height h-1 and the other to have height h-2.
+  - Thus: **N(h) = 1 + N(h-1) + N(h-2)** for h ≥ 3
+
+This is the **Fibonacci recurrence!**
+
+#### Step 2: Solve the Fibonacci Recurrence
+
+The recurrence N(h) = N(h-1) + N(h-2) with N(1) = 1, N(2) = 2 is related to the Fibonacci sequence.
+
+Let F_k denote the k-th Fibonacci number with F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, etc.
+
+Then: **N(h) = F_{h+2}**
+
+(Verification: N(1) = F_3 = 2... wait, let me recalculate.)
+
+Actually, let me redefine carefully:
+- F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8, ...
+- N(1) = 1, N(2) = 2, N(3) = 1 + 2 + 1 = 4... hmm, that doesn't match.
+
+Let me reconsider: with N(h) = N(h-1) + N(h-2), N(1) = 1, N(2) = 2:
+- N(1) = 1
+- N(2) = 2
+- N(3) = N(2) + N(1) = 2 + 1 = 3
+- N(4) = N(3) + N(2) = 3 + 2 = 5
+- N(5) = N(4) + N(3) = 5 + 3 = 8
+- N(6) = N(5) + N(4) = 8 + 5 = 13
+
+If F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8, F_7 = 13, then:
+**N(h) = F_{h+1}**
+
+#### Step 3: Use Binet's Formula
+
+The Fibonacci sequence grows exponentially. Binet's formula states:
+$$F_k = \frac{\phi^k - \psi^k}{\sqrt{5}}$$
+
+where φ = (1+√5)/2 ≈ 1.618 (the golden ratio) and ψ = (1-√5)/2 ≈ -0.618.
+
+Since |ψ| < 1, for large k, |ψ^k| becomes negligible, so:
+$$F_k \approx \frac{\phi^k}{\sqrt{5}}$$
+
+Thus:
+$$N(h) = F_{h+1} \approx \frac{\phi^{h+1}}{\sqrt{5}}$$
+
+#### Step 4: Invert to Get Height Bound
+
+If an AVL tree has n nodes, then:
+$$n = N(h) \approx \frac{\phi^{h+1}}{\sqrt{5}}$$
+
+Solving for h:
+$$\phi^{h+1} \approx \sqrt{5} \cdot n$$
+$$h+1 \approx \log_\phi(\sqrt{5} \cdot n)$$
+$$h \approx \log_\phi(\sqrt{5} \cdot n) - 1$$
+
+#### Step 5: Convert to Base-2 Logarithm
+
+Using change of base formula: $\log_\phi(x) = \frac{\log_2(x)}{\log_2(\phi)}$
+
+With $\log_2(\phi) = \log_2\left(\frac{1+\sqrt{5}}{2}\right) \approx 0.6942$:
+
+$$h \approx \frac{\log_2(\sqrt{5} \cdot n)}{\log_2(\phi)} - 1 = \frac{\log_2(\sqrt{5}) + \log_2(n)}{0.6942} - 1$$
+
+$$\approx \frac{2.322 + \log_2(n)}{0.6942} - 1 \approx 1.440 \log_2(n) + 1.34$$
+
+#### Step 6: More Precise Bound
+
+More rigorously, we have:
+$$n \geq F_{h+1}$$
+
+By properties of Fibonacci numbers:
+$$F_{h+1} > \phi^h / \sqrt{5} - 1$$
+
+So:
+$$n > \phi^h / \sqrt{5} - 1$$
+$$\phi^h < \sqrt{5}(n+1)$$
+$$h < \log_\phi(\sqrt{5}(n+1))$$
+
+Converting to base-2:
+$$h < \frac{\log_2(\sqrt{5}(n+1))}{\log_2(\phi)} = \frac{1.1610 + \log_2(n+1)}{0.6942}$$
+
+$$\approx 1.4405 \log_2(n+1) + \frac{1.1610}{0.6942} \approx 1.4405 \log_2(n+1) + 1.673$$
+
+Actually this gives a constant term that's quite large. A cleaner bound:
+
+**For practical purposes: h ≤ 1.45 log₂(n+2)**
+
+or in the requested form: **h ≤ 1.44 log₂(n+1) + 1.67** (approximately)
+
+The constants c ≈ 1.44, k = 1, b ≈ 1.67 provide a valid upper bound.
+
+#### Summary
+
+The height h of an AVL tree with n nodes satisfies:
+$$h \leq c \log_2(n+k) + b$$
+
+where we can choose:
+- **c = 1.44** (approximately 1/log₂(φ))
+- **k = 1** or **k = 2** (adjusting b accordingly)
+- **b ≈ 1.67** (precise value depends on k)
+
+The key insight is that AVL trees maintain balance using the height-balancing property (difference of at most 1), which forces the tree to grow with the Fibonacci sequence, leading to logarithmic height bounded by the golden ratio.
+
+---