Project 2 — Build a Dynamic Array

“Everyone then who hears these words of mine and does them will be like a wise man who built his house on the rock.” — Matthew 7:24

Chapter: 2 — Arrays and the Memory You Can Feel Due: End of Week 2 Submit: A link to a public GitHub repo containing dynamic_array.py, your test file, your benchmark scripts, and README.txt. Real toolchain, real git this term — see Appendix A for the Python + git setup. Allowed tools: Python 3.10+, the standard library (time, sys, tracemalloc, unittest/pytest), a real editor, the textbook. AI: Phase 1 (wk 1–8): AI is OFF. No assistants, no autocomplete-beyond-a-word, no “explain this.” You cannot reason about the cost of a structure you have never built yourself — and the entire point of this project is to build it so that in Phase 2 you can direct an agent who builds structures for you and know when it chose badly. Phase 2 (wk 9–16) will turn agentic AI on and require an agent-log.txt. Not yet.

The Setup

A small ministry is building a tool that ingests a stream of incoming items — prayer requests as they arrive, attendees as they check in, verses as a study group adds them — and the count is never known in advance. Sometimes it’s twelve. Sometimes it’s twelve thousand. The lead developer, who learned to code the year Python hid all the memory, keeps saying “just use a list, append is free.”

She’s mostly right. But “mostly free” has a shape, and the architect’s job is to know the shape — to know why append is usually instant and occasionally stalls, and to be able to say what it would cost to grow differently. The only way to know that cold is to build the thing list does for you. So you will.

You are going to implement a growable array on top of a fixed-capacity buffer — the exact structure CPython runs under list — and you are going to prove its costs with measurements, not assertions. By the end you will never again be surprised by why a real-time append loop occasionally hiccups, and you will be able to defend a growth policy the way the person who wrote your standard library had to.

This is the rock under every house you build the rest of the term. Found it well.

Learning Targets

By completing this project, you will demonstrate that you can:

• Implement a dynamic array on a raw fixed-capacity buffer, managing capacity and length as separate invariants.
• Implement doubling growth and explain — and measure — why append is amortized O(1).
• Distinguish amortized from worst-case cost with real timings of individual operations.
• Implement and measure the O(n) cost of middle insert/delete and contrast it with O(1) append.
• Compare growth policies empirically and make a justified default recommendation, the way a standard-library author must.
• Write a measurement memo that relates measured curves to the cost table from §2.6 — the Phase 1 deliverable.

Normal Tier

Goal: Implement a DynamicArray class backed by a fixed-capacity buffer, with doubling growth, and prove the doubling and the amortized O(1) cost with tests.

Required features

1. Raw storage, not a Python list-as-list. Your backing store is a Python list pre-sized with None and used purely as a fixed-capacity buffer — like a C array. You may write self._buffer = [None] * capacity and index it (self._buffer[i]). You may not call self._buffer.append(...), .insert(...), .pop(...), +=, slicing-to-grow, or anything else that lets Python’s own dynamic array do your growth for you. The growth is your job — that’s the project.
2. Core operations:
   • __init__(self) — start with a small capacity (1 or 2) and length 0.
   • __len__(self) — return the current length (number of elements in use), O(1).
   • get(self, i) / __getitem__ — return element i, O(1); raise IndexError for out-of-range i.
   • set(self, i, value) / __setitem__ — overwrite element i, O(1); raise IndexError for out-of-range i.
   • append(self, value) — add to the end; double the capacity when the buffer is full, copying existing elements one at a time in an explicit loop.
   • __str__(self) — a readable representation of the elements in use (not the None padding): e.g. DynamicArray([10, 20, 30]).
3. Invariant discipline. 0 <= length <= capacity holds after every operation. Grow before writing when length == capacity. (See the Common Bugs section of the chapter — this is the off-by-one that corrupts memory in C.)
4. Tests that prove the behavior (use unittest or pytest):
   • Append n items; len is n, and get(i) == i for all i.
   • Capacity doubles: expose capacity (a property or _capacity you read in the test) and assert that after appending 1, 2, 3, 5, 9 items the capacity is 1→2→4→8→16 (or your chosen start, doubling). The grader checks you tested the doubling explicitly.
   • Amortized O(1): count total element-copies across n appends (instrument _resize) and assert the total is < 2 * n for several n including n = 1_000_000. This is the amortized proof in code.
   • get/set raise IndexError out of range; set then get round-trips a value.

Example output

A tiny driver (python3 dynamic_array.py) should be able to do this:

>>> da = DynamicArray()
>>> for x in [10, 20, 30, 40, 50]: da.append(x)
>>> print(da)
DynamicArray([10, 20, 30, 40, 50])
>>> len(da)
5
>>> da.capacity            # internal, exposed for the lesson
8
>>> da.get(2)
30
>>> da.set(2, 99); da.get(2)
99
>>> da.get(5)
IndexError: index 5 out of range for length 5

And your amortized proof, run directly, should print something like:

n=        1  copies=        0  ratio=0.000
n=       16  copies=       15  ratio=0.938
n=  1000000  copies=   999999  ratio=1.000
PASS: total copies < 2n for all tested n  (amortized O(1) confirmed)

Normal-tier rubric (out of 100)

Medium Tier (+up to 25% extra credit)

M1. insert(i, x) and delete(i), built right

Add:

• insert(self, i, value) — insert at index i, shifting elements i..length-1 one slot to the right (growing first if full). Valid i is 0..length. Shift right-to-left so you don’t overwrite elements you haven’t moved yet.
• delete(self, i) — remove element i, shifting elements i+1..length-1 one slot left to close the gap, then decrement length. (Optionally null out the now-unused tail slot.) Valid i is 0..length-1.

Write tests for both, including front insert/delete (the most-shifting case), end insert/delete, and out-of-range errors.

M2. Measure that insert/delete are O(n) and append is amortized O(1)

Write a benchmark (benchmark_ops.py) that times append, insert(0, x) (front), and delete(0) (front) at increasing sizes (e.g. 1k, 2k, 4k, 8k, 16k operations). Produce a table of size vs time-per-operation. Show that per-operation time for front insert/delete grows with n (O(n) each → O(n²) for the loop) while append’s per-operation time stays roughly flat (amortized O(1)). Include the table in your README and write two sentences relating it directly to the cost table in §2.6.

Hard Tier (+up to 25% additional extra credit)

H1. Pluggable growth policy

Add a growth-policy parameter to __init__: DynamicArray(growth="double") where the choices are at least:

• "double" — new capacity = old * 2.
• "fixed_k" — new capacity = old + k for a fixed k you pick (e.g. 1024). Grow by a constant amount, not a factor.
• "one_point_five" — new capacity = old + old // 2 (1.5x; the policy Java’s ArrayList actually uses).

All three must keep append correct. The point is to measure them, not just to support them.

H2. The million-append showdown

Write benchmark_growth.py. For each policy, append 1,000,000 elements and measure two things:

• Time: total wall-clock to do the million appends (median of a few runs).
• Space/work: total number of element-copies performed across all resizes (instrument _resize), and peak capacity reached (a proxy for wasted memory). Optionally use tracemalloc to confirm peak memory.

Produce a results table like:

fixed_k should be visibly catastrophic (O(n²) copies — on the order of billions — and far slower). Don’t be surprised if you have to cut its n down to keep the run finite; if you do, document the smaller n and the projected cost at a million. That impracticality is the finding.

H3. The recommendation memo (the judgment piece)

Write MEMO.docx (half a page to a page). Using your own measured numbers, answer the question a standard-library author actually faces:

1. Which growth policy would you make the default, and why? Weigh time (fewer copies) against wasted memory (higher peak capacity).
2. Why is fixed_k disqualified outright? Name its asymptotic class and cite your numbers.
3. Java’s ArrayList grows by 1.5x; many C++ vector implementations grow by 2x (some by ~1.5x). Given your data, why might a real library pick 1.5x over 2x even though 2x does fewer copies? (Hint: think about what happens to freed memory blocks and whether the next allocation can reuse them — the memory-reuse argument is the real reason 1.5x is popular, and it’s a judgment an agent can’t make for you without the constraint.)
4. State the constraint under which you’d switch your recommendation (e.g., “if peak memory is the binding constraint, I’d choose …; if append latency variance is binding, I’d choose …”).

This memo is the heart of the Hard tier. The numbers are necessary; the judgment about which number matters under which constraint is the architect’s work, and it’s exactly the work no tool does for you.

Submission

Submit one URL: a public GitHub repo.

What the repo must contain

1. dynamic_array.py — the DynamicArray class, with the example driver under if __name__ == "__main__":.
2. test_dynamic_array.py — your tests (the Normal-tier proofs at minimum; insert/delete tests for Medium). Confirm they pass before submitting (python3 -m pytest or python3 -m unittest).
3. benchmark_ops.py (Medium) and benchmark_growth.py (Hard) — your measurement scripts, runnable.
4. MEMO.docx (Hard) — the growth-policy recommendation.
5. README.txt — your reflection:

# Project 2 — Build a Dynamic Array

**Tier targeted:**  Normal / Medium / Hard
**Features done:**  (list)
**How append stays amortized O(1):**  (two sentences, in your own words)
**Amortized proof:**  (where in the tests; the largest n you proved it at)
**Measured costs:**  (paste your Medium/Hard tables if applicable)
**Growth-policy recommendation:**  (one line; full reasoning in MEMO.docx)
**What I learned:**  (one paragraph)
**What I'd change:**  (one sentence)
**AI usage:**  NONE — Phase 1.  Signed: <your name>

6. Reflection comment block at the top of dynamic_array.py — same fields as the README, condensed.
7. The code left runnable — python3 dynamic_array.py runs the driver and the amortized proof without errors.

Hints (Read Before You Begin)

• Capacity and length are different numbers. Tattoo this on your brain. Capacity is how big the buffer is; length is how much you’ve used. Almost every bug in this project is a confusion between the two. Grow when length == capacity, write at index length, then increment length.
• Grow before you write. If you write self._buffer[self._length] = value while the buffer is full, you go out of bounds. Check-and-grow first, always. (In Python you get an IndexError; in C this is the classic buffer overflow.)
• _resize copies one element at a time, on purpose. You could new[:length] = old[:length], but don’t — the explicit for i in range(self._length) loop is the O(n) work you’re studying, and seeing it is the point. Slicing hides the cost you’re here to measure.
• For insert, shift right-to-left. Move the last element first, then work backward toward i. If you shift left-to-right you’ll overwrite elements before you’ve moved them. Trace insert(0, x) on paper for a 3-element array before you code it.
• Instrument, don’t assume. To prove amortized O(1), add a counter to _resize (self._copies += self._length) and read it in the test. Numbers you generated beat claims you repeated.
• Time with time.perf_counter(), run it more than once, report the median. The first run is cold. For the million-append benchmark, disable any debug printing inside the loop — printing dominates the timing and ruins the measurement.

What Mastery Looks Like (Beyond the Rubric)

A great Project 2 has a DynamicArray whose append you can read in ten seconds and immediately see the invariant: full? double. then write. then bump length. The _resize is an explicit copy loop with no cleverness. The tests don’t just check that it works — they prove the cost claims: a test named test_capacity_doubles and a test named test_append_amortized_constant that fails loudly if someone “optimizes” the growth into something quadratic.

A great Hard tier produces a memo that a real standard-library maintainer would nod at. It doesn’t just say “double is fastest.” It weighs copies against wasted memory, disqualifies fixed_k with its O(n²) class and the measured billions of copies, and engages honestly with why 1.5x is so common despite doing more copies than 2x — the memory-reuse argument. That last point is judgment under a constraint, and it is the whole reason Phase 1 makes you build and measure before Phase 2 lets you delegate.

Coach’s Note — Students are tempted to make _resize “smart” — slice, comprehend, batch. Resist. The unclever explicit copy is what makes the cost visible, and visibility is the entire deliverable. You are not building the fastest dynamic array on earth; CPython already did that in C. You are building the one whose every cost you can see and defend. That second thing is what makes you an architect. The first is just a faster house on a foundation you don’t understand.

When You’re Done

1. Run python3 dynamic_array.py. Confirm the driver and the amortized proof both print clean.
2. Run your tests. All green. Then deliberately break _resize to grow by +1 instead of *2, re-run the amortized test, and watch it fail (copies blow past 2n). Restore. This is the red-green discipline from Coding 2 applied to a cost claim.
3. (Hard) Run benchmark_growth.py, paste the table into MEMO.docx, and write the recommendation.
4. Read your own append and _resize slowly. Could a stranger see the doubling and the invariant from the code alone? If not, simplify.
5. Commit, push, submit the repo URL.
6. Read Chapter 3. Linked lists next — the structure that claims to beat the array’s O(n) middle. You’ll benchmark whether it actually does, and the cache lesson from §2.2 will have something to say about the answer.

A theological footnote. The wise builder in Matthew 7 was not wiser because his house was bigger. He was wiser because he understood what his house stood on — and built accordingly when the easier, sandier ground was right there. You spent this week refusing the easy ground. You did not type list.append and move on; you built the thing it does, measured what it costs, and now you understand the rock the rest of the term stands on. The storms — the scale, the latency spike, the memory ceiling — come for every program. The house founded on understood costs is the one still standing when they do. Build on the rock.

See you next week.