diff --git a/writeup.md b/writeup.md
index 0ea5554..7919b87 100644
--- a/writeup.md
+++ b/writeup.md
@@ -2,8 +2,312 @@
 
 ## Student Responses
 
-<!-- Write your solutions below. Add sections for each problem as needed. -->
-<!-- Use proper mathematical notation where applicable. -->
+---
 
-[Your solutions here]
+## Problem 1: Persistent Dynamic Sets
 
+### Part (a)
+
+**Insert:** When inserting a node into a persistent BST, the nodes that need to change are exactly those on the path from the root to the insertion point (the leaf position where the new node is placed). Each node on this path must be copied because its child pointer (left or right) changes to point to the new copy of its child below it. Nodes not on this path remain unchanged and are shared between the old and new tree versions.
+
+**Delete:** The nodes that need to change depend on the deletion case:
+- **Node has 0 or 1 children:** All nodes on the path from the root to the deleted node must be copied. The deleted node's parent copy has its child pointer updated to NIL (0 children) or to the deleted node's single child (1 child).
+- **Node has 2 children:** We find the successor of the deleted node (go right, then all the way left). All nodes on the path from the root through the deleted node down to the successor must be copied. The deleted node's copy receives the successor's key, and the successor is removed by updating its parent's child pointer.
+
+In all cases, only nodes on the path from root to the physically removed position need to be copied.
+
+### Part (b)
+
+```
+PERSISTENT-TREE-INSERT(T, z)
+ 1  let T' be a new tree
+ 2  if T.root == NIL
+ 3      T'.root = z
+ 4      return T'
+ 5  T'.root = COPY-NODE(T.root)
+ 6  y = T'.root
+ 7  while TRUE
+ 8      if z.key < y.key
+ 9          if y.left == NIL
+10              y.left = z
+11              return T'
+12          else
+13              y.left = COPY-NODE(y.left)
+14              y = y.left
+15      else
+16          if y.right == NIL
+17              y.right = z
+18              return T'
+19          else
+20              y.right = COPY-NODE(y.right)
+21              y = y.right
+```
+
+**Explanation:** The procedure creates a new tree T' by copying only the nodes on the path from the root to the insertion point. Starting at the root, we copy the current node and descend toward the correct insertion position. At each level, we copy the next node on the path before descending into it. When we find a NIL child in the appropriate direction, we attach z there. Nodes not on the path are shared between T and T' (the copied nodes' other child pointers still reference the original, shared nodes).
+
+### Part (c)
+
+- **Time:** O(h). We traverse the path from the root to the insertion point, performing O(1) work (one COPY-NODE call plus pointer updates) at each of the O(h) levels.
+- **Space:** O(h). We create exactly one new node per level on the root-to-insertion path, plus the new node z. The number of nodes on this path is at most h + 1, so the space requirement is O(h).
+
+### Part (d)
+
+**Claim:** If parent pointers are included, PERSISTENT-TREE-INSERT requires Omega(n) time and space.
+
+**Proof:** Consider inserting a node z. We must copy all nodes on the root-to-insertion path (at least the root). When we copy a node c on this path, the copy c' replaces c in the new tree. Now consider a child d of c that is NOT on the insertion path. In the original tree, d.parent = c. In the new tree, d's parent should be c' (the copy), not c. However, d is shared between the old and new trees — we cannot modify d.parent to point to c' without corrupting the old tree. Therefore, we must also copy d (creating d') and set d'.parent = c'.
+
+But now d' has children whose parent pointers point to d, not d'. So we must copy d's children as well, and their children, and so on. This cascading copying extends to the entire subtree rooted at d.
+
+This cascading occurs for every off-path child of every node on the insertion path. Since every node in the tree is either on the path or in the subtree of some off-path child of a path node, we end up copying every node in the tree.
+
+Therefore, the total number of nodes copied is n, giving Omega(n) time and space. QED.
+
+### Part (e)
+
+We use a persistent red-black tree **without parent pointers** (as motivated by Part (d)). Red-black trees guarantee a height of O(log n), which directly gives us O(log n) worst-case time and space per insertion:
+
+1. **Path copying:** Since the height of a red-black tree with n nodes is at most 2 lg(n+1), the root-to-insertion path has O(log n) nodes. We copy each of these nodes as in Part (b), taking O(log n) time and space.
+
+2. **Maintaining ancestors for fixup:** Since we have no parent pointers, we store the path from the root to the inserted node in a stack/array as we descend. This uses O(log n) space (which does not increase the asymptotic space beyond what we already use for copying).
+
+3. **RB-INSERT-FIXUP on the persistent tree:** During fixup, we traverse back up the path (using our stored path) performing recolorings and rotations:
+   - **Recolorings (Case 1):** We recolor the parent, uncle, and grandparent, then move up two levels. The parent and grandparent are already on the path (already copied), so we can modify their colors freely. The uncle is NOT on the path, so we must create a copy of the uncle with the new color. We then update the grandparent's copy to point to this uncle copy. This adds at most one extra copy per Case 1 occurrence. Since Case 1 occurs at most O(log n) times, this contributes at most O(log n) additional copies.
+   - **Rotations (Cases 2 and 3):** At most 2 rotations are performed. The rotated nodes are on or adjacent to the copied path, and rotations involve O(1) pointer changes on already-copied nodes.
+
+4. **Total cost:** O(log n) path copies + O(log n) uncle copies + O(1) rotation work = **O(log n) time and O(log n) space** per insertion.
+
+Since the red-black tree height is always O(log n) regardless of the insertion sequence, this O(log n) bound is a **worst-case** guarantee, not merely amortized.
+
+---
+
+## Problem 2: Join Operation on Red-Black Trees
+
+### Part (a)
+
+**Maintaining T.bh:** We store the black-height as a single attribute T.bh on the tree object itself (not on individual nodes), requiring no extra storage in the nodes.
+
+During RB-INSERT, the black-height of the tree changes only when the root is recolored from red to black. This occurs at the very end of RB-INSERT-FIXUP (the final line: T.root.color = BLACK). We check: if the root was previously red (before being set to black), we increment T.bh by 1. This is O(1) additional work per insertion, so the asymptotic running time is unchanged.
+
+**Computing black-height during descent:** Starting at the root with bh = T.bh, we can determine the black-height of each visited node in O(1) time using the following rule:
+
+When moving from node x (with known black-height bh_x) to a child c:
+- If c is **black**: bh_c = bh_x - 1
+- If c is **red**: bh_c = bh_x
+
+This follows from the definition: the black-height of x counts the black nodes on any path from x (exclusive) to a leaf. If c is black, then c accounts for one of those black nodes, so the remaining count from c to a leaf is bh_x - 1. If c is red, it doesn't count toward x's black-height, so the count from c to a leaf is still bh_x.
+
+### Part (b)
+
+**Algorithm** to find black node y in T_1 with the largest key among those with black-height T_2.bh:
+
+```
+FIND-JOIN-POINT(T₁, T₂)
+ 1  y = T₁.root
+ 2  bh = T₁.bh
+ 3  // Descend the right spine of T₁, tracking black-height
+ 4  while bh ≠ T₂.bh or y.color ≠ BLACK
+ 5      y = y.right
+ 6      if y.color == BLACK
+ 7          bh = bh - 1
+ 8  return y
+```
+
+Note: If T_1.bh = T_2.bh, the root (which is always black) is returned immediately without entering the loop.
+
+**Correctness:** We descend along the right spine of T_1 (always going to the right child), tracking the black-height. Each time we pass through a black node, bh decreases by 1; red nodes leave bh unchanged. We stop at the first black node where bh = T_2.bh. Since we always go right, this node has the largest key among all black nodes at black-height T_2.bh (any other such node would be to the left in the tree and thus have a smaller key).
+
+**Running time:** O(log n). The path length is bounded by the height of T_1, which is at most 2 lg(n+1) = O(log n).
+
+### Part (c)
+
+Let y be the black node found in Part (b), and let p be y's parent in T_1. Since we descended via the right spine, y = p.right.
+
+We replace T_y (the subtree rooted at y) with a new subtree T as follows:
+
+1. Set x.left = y (the root of T_y)
+2. Set x.right = T_2.root
+3. Set p.right = x (replacing y with x as p's right child)
+
+This takes O(1) time (three pointer assignments).
+
+**BST property is maintained:**
+- **Within the new subtree rooted at x:** All keys in T_y (= x.left) are from T_1, so they are all ≤ x.key. All keys in T_2 (= x.right) are ≥ x.key. So the BST property holds at x.
+- **At p:** Previously p.right = y, and p.key < y.key (since y was p's right child). Now p.right = x, and p.key < y.key ≤ x.key, so the BST property still holds at p.
+- **All other nodes** are unchanged, so the BST property is preserved throughout the tree.
+
+### Part (d)
+
+**We color x RED.** This maintains:
+
+- **Property 1** (every node is red or black): x is colored red. ✓
+- **Property 3** (every leaf/NIL is black): x is an internal node, not a leaf. ✓
+- **Property 5** (all paths from a node to descendant leaves have the same number of black nodes): Since x is red, it does not contribute to black-height counts. The left subtree of x (= T_y) has black-height T_2.bh (by our choice of y), and the right subtree (= T_2) has black-height T_2.bh (by definition). So the black-heights are balanced at x. Furthermore, x replaced y (which had black-height T_2.bh) in T_1, and bh(x) = T_2.bh (same as y's was), so property 5 is maintained throughout the tree. ✓
+
+**Properties that may be violated:**
+
+- **Property 2** (root is black): If T_1.bh = T_2.bh, then y was the root of T_1, and x becomes the new root. Since x is red, property 2 is violated. **Fix:** Simply recolor the root black. This increases the black-height by 1 but doesn't violate any other properties. O(1) time.
+
+- **Property 4** (no two consecutive red nodes): If y's parent p is red, then we have p (red) → x (red), violating property 4. **Fix:** This is exactly the same violation that occurs after a standard RB-INSERT. We run RB-INSERT-FIXUP starting at x and proceeding upward. The fixup performs at most O(log n) recolorings and at most 2 rotations, so it runs in O(log n) time.
+
+### Part (e)
+
+**No generality is lost** because the two cases (T_1.bh ≥ T_2.bh and T_1.bh ≤ T_2.bh) are exhaustive. Every pair of red-black trees satisfies one of these conditions.
+
+**Symmetric case when T_1.bh ≤ T_2.bh:** We perform the mirror-image operations:
+
+1. Find a black node y in T_2 with the **smallest** key among those with black-height T_1.bh. This is done by descending the **left** spine of T_2 (always going to the left child), tracking black-height until we find a black node at bh = T_1.bh.
+
+2. Replace T_y with a new subtree: set x.left = T_1.root, x.right = y, and update y's parent to point to x.
+
+3. Color x red and run RB-INSERT-FIXUP from x upward to restore properties 2 and 4.
+
+The analysis is identical to Parts (b)–(d) by symmetry, and the running time is O(log n).
+
+### Part (f)
+
+The running time of RB-JOIN is O(log n), as shown by the following breakdown:
+
+| Step | Operation | Time |
+|------|-----------|------|
+| (a) | Maintain/compute black-heights | O(1) per node, O(log n) total |
+| (b) | Find join point y | O(log n) — descend one spine |
+| (c) | Replace subtree | O(1) — three pointer assignments |
+| (d) | Color x red | O(1) |
+| (d) | RB-INSERT-FIXUP | O(log n) — at most O(log n) recolorings + 2 rotations |
+
+**Total: O(log n).**
+
+More precisely, the cost of finding y (step b) is proportional to the difference in heights of T_1 and T_2, which is at most 2|T_1.bh - T_2.bh| ≤ O(log n). The cost of fixup (step d) is proportional to the height of the resulting tree above x, which is also O(log n). Both are bounded by O(log n), and the remaining steps are O(1). Therefore, the total running time of RB-JOIN is O(log n).
+
+---
+
+## Problem 3: Joining and Splitting 2-3-4 Trees
+
+### Part (a)
+
+**Maintaining x.height:** We store the height of the subtree rooted at each node x as an attribute x.height. In a 2-3-4 tree, all leaves are at the same depth, so the height of a node equals 1 + the height of any of its children. Leaf nodes (at the bottom level) have height 0.
+
+**During search:** No modifications are made to the tree, so heights are unchanged. Reading x.height is O(1) per node visited. The asymptotic running time O(log n) is unaffected.
+
+**During insertion:** We insert a key into a leaf node, potentially splitting nodes along the path from the leaf to the root. We maintain heights as follows:
+
+- When we **split** a node at height h, it produces two nodes, each also at height h (they have the same children as subsets of the original). The middle key is pushed up to the parent. The parent's height is unchanged (it remains 1 + the height of its children, which hasn't changed). This is O(1) work per split.
+- When the **root splits**, a new root is created with height = (old root's height) + 1. This is O(1).
+- All nodes not involved in splits retain their existing heights.
+
+Since insertion visits at most O(log n) nodes (the height of the tree) and does O(1) extra work per node to maintain heights, the asymptotic running time of insertion remains O(log n).
+
+### Part (b)
+
+**Join algorithm** for 2-3-4 trees T' (height h') and T'' (height h'') with key k:
+
+**Case 1: h' = h''.** Create a new root node (a 2-node) containing key k, with T'.root as its left child and T''.root as its right child. Set the new root's height to h' + 1. Time: O(1).
+
+**Case 2: h' > h''.** We attach T'' into T' at the appropriate level:
+
+1. Starting at T'.root, descend along the **rightmost** child pointer at each node. At each node encountered, if it is a 4-node, **split it** (push the middle key up to the parent, creating two 2-nodes). This top-down splitting ensures no node on our descent path is a 4-node.
+2. After descending exactly h' - h'' levels, we reach a node y at height h''. Let p be y's parent. Since we split 4-nodes on the way down, p is not a 4-node (it has at most 3 keys).
+3. Insert key k into p as a new key to the right of y's position, and make T''.root the new child to the right of k. Node y remains the child to the left of k.
+   - Since p had at most 3 keys and we added one, p now has at most 4 keys. But with top-down splitting, p had at most 3 children (a 2-node or 3-node), so after adding k and T'', it has at most 4 children — still a valid 2-3-4 tree node. (If p was a 3-node, it becomes a 4-node, which is valid.)
+4. Update height attributes along the path if necessary (each is O(1)).
+
+**Time:** O(h' - h''). We descend h' - h'' levels, doing O(1) work at each level (splitting and/or pointer updates). The insertion at the bottom is O(1).
+
+**Case 3: h'' > h'.** Symmetric to Case 2. Descend the **leftmost** spine of T'' for h'' - h' levels, splitting 4-nodes top-down. Attach T' and k on the left side.
+
+**Overall time:** O(1 + |h' - h''|).
+
+**Correctness of BST property:** All keys in T' are less than k (given), and all keys in T'' are greater than k (given). Node y is on the rightmost spine of T', so all keys in T_y (the subtree rooted at y) are among the largest in T'. Inserting k to the right of y in p, with T'' as k's right child, preserves the ordering: keys in T_y < k < keys in T''.
+
+### Part (c)
+
+Consider the path p from the root of T to key k. At each internal node on the path, the node contains some keys and has some children. One child leads to the next node on the path; the remaining keys and children are distributed to S' or S''.
+
+**How p breaks S' into trees and keys:**
+
+At each node n_i on the path (from root at depth 0 to the node containing k at depth d):
+- Let the keys in n_i be a_1 < a_2 < ... < a_t, and suppose the path follows child c_j (the child between a_j and a_{j+1}, or the leftmost/rightmost child).
+- Keys a_1, ..., a_j (those less than k at this node) are contributed to S'.
+- Their corresponding left subtrees (children c_0, ..., c_{j-1}) are also contributed to S'.
+
+Collecting all these contributions in order from smallest key to largest key, we get:
+
+**S' = T'_0, k'_1, T'_1, k'_2, T'_2, ..., k'_m, T'_m**
+
+where:
+- Each T'_i is an off-path subtree whose keys are all less than k.
+- Each k'_i is a key from a path node that is less than k.
+- For any y in T'_{i-1} and z in T'_i: y < k'_i < z. This follows from the BST property of the original 2-3-4 tree — the keys and subtrees are naturally ordered from left to right.
+
+**Relationship between heights:** height(T'_{i-1}) >= height(T'_i). The heights are **non-increasing**. This is because the trees are listed in order of increasing key value, and:
+- Trees collected from shallower depths (near the root) have larger heights and smaller keys (they come from the left side of high-level nodes).
+- Trees collected from deeper levels have smaller heights and keys closer to (but less than) k.
+
+More precisely, an off-path subtree whose root is at depth d+1 in the original tree T has height h - d - 1. Since we list subtrees from shallowest (smallest key, largest height) to deepest (largest key among those < k, smallest height), consecutive heights satisfy height(T'_{i-1}) - height(T'_i) in {0, 1}: they differ by 0 when both come from the same node (same depth), and by 1 when they come from nodes at adjacent depths.
+
+**S'' is broken symmetrically:** S'' = T''_0, k''_1, T''_1, ..., k''_{m''}, T''_{m''}
+
+where:
+- T''_0 has the smallest keys in S'' (closest to k) and the **smallest** height.
+- T''_{m''} has the largest keys in S'' and the **largest** height.
+- Heights are **non-decreasing**: height(T''_{i-1}) <= height(T''_i).
+
+This is because the trees with the smallest keys in S'' come from the deepest level (keys just above k), while the trees with the largest keys come from the shallowest level (rightmost subtrees near the root).
+
+### Part (d)
+
+**Split algorithm:**
+
+**Step 1: Walk the path and collect.** Search for k in T, following the path from root to the node containing k. At each node on the path, separate the keys and off-path subtrees into two collections:
+- **L** (for S'): trees T'_0, T'_1, ..., T'_m and keys k'_1, ..., k'_m (those less than k)
+- **R** (for S''): trees T''_0, T''_1, ..., T''_{m''} and keys k''_1, ..., k''_{m''} (those greater than k)
+
+This takes O(h) = O(log n) time.
+
+**Step 2: Assemble T' using joins.** Since heights of T'_0, T'_1, ..., T'_m are non-increasing, we join from right to left (starting with the smallest trees):
+
+```
+T' = T'_m
+for i = m down to 1:
+    T' = JOIN(T'_{i-1}, k'_i, T')
+```
+
+Each JOIN takes O(1 + |height(T'_{i-1}) - height(T')|) time.
+
+**Step 3: Assemble T'' using joins.** Since heights of T''_0, T''_1, ..., T''_{m''} are non-decreasing, we join from left to right (starting with the smallest trees):
+
+```
+T'' = T''_0
+for i = 1 to m'':
+    T'' = JOIN(T'', k''_i, T''_i)
+```
+
+**Running time analysis (telescoping argument):**
+
+For assembling T', let r_i denote the height of the result after the i-th join, with r_0 = height(T'_m).
+
+At step i (joining T'_{m-i} with the current result):
+- height(T'_{m-i}) >= height(T'_{m-i+1}) >= ... (non-increasing sequence)
+- Cost_i = O(1 + |height(T'_{m-i}) - r_{i-1}|)
+- After join: r_i <= max(height(T'_{m-i}), r_{i-1}) + 1
+
+Since height(T'_{m-i}) >= r_{i-1} in general (the new tree being joined is at least as tall as or taller than the current result), we have:
+- Cost_i = O(1 + height(T'_{m-i}) - r_{i-1})
+- r_i <= height(T'_{m-i}) + 1
+
+The total cost telescopes:
+
+Sum of costs = Sum_{i=1}^{m} O(1 + height(T'_{m-i}) - r_{i-1})
+
+Since r_{i-1} >= height(T'_{m-i+1}), the height differences telescope:
+
+Sum of (height(T'_{m-i}) - r_{i-1}) <= Sum of (height(T'_{m-i}) - height(T'_{m-i+1})) + m
+= height(T'_0) - height(T'_m) + m
+
+Since height(T'_0) <= h - 1 = O(log n) and m <= 3h (at most 3 subtrees per node on the path, with path length h), the total cost is:
+
+**O(m + h) = O(h) = O(log n)**
+
+The same telescoping argument applies to assembling T'' (symmetric case).
+
+**Total running time of split:** O(log n) for the search + O(log n) for assembling T' + O(log n) for assembling T'' = **O(log n)**.