Exercises + milestone requirements owned by this stage
Evidence and gate
0 · 0/9
Artifacts · checked requirements
Why it matters
Purpose of this stage
Understand core CS structures
Subjects
3 subjects · 24 canonical topics
Each subject states what you should be able to do, an order to work through it in, what to watch for, and the questions a reviewer should be able to ask you at the end. None of it is tracked or scored.
How to work through this subject
An order that works, not a checklist. Nothing here is tracked — the steps sequence this subject’s own topics and add none.
For each structure, write down the operations it makes cheap before writing any code.
Implement a stack and a queue from scratch, without the library versions.
Build a frequency table with a hash map and reason about why lookup does not scan.
Represent the same small dataset as a list, a set and a tree, and note what each one makes easy.
Read the concepts you are not implementing — linked list, binary search tree, heap — and say what each is for.
Finish by picking a structure for a problem you invent, and defending the choice by its operations, not its name.
What to watch for
Implement them yourself before using the built-in. The point is understanding the trade, not having the structure.
Python's dict is a hash map — most 'algorithm' problems at this level are really 'use the right structure' problems.
Every structure is fast at something and slow at something else. If you cannot name the slow side, you do not know it yet.
A graph is a shape, not a class: nodes with edges. Adjacency is just a dict of lists once you see it.
Concept-level topics here are recognition, not implementation. Know what a heap is for; you do not need to write one.
The question that picks a structure is 'what will I ask of this data most often', not 'which one is fastest'.
Curriculum topics
list/array
An ordered sequence with fast access by position, and costly insertion at the front.
stack
Last in, first out. Push and pop happen at the same end, both cheaply.
queue
First in, first out. Items are added at one end and removed from the other.
hash map
A key-to-value structure with roughly constant-time lookup, because a hash of the key locates the slot directly.
set
An unordered collection of unique values with fast membership testing.
linked list concept
A chain of nodes each pointing to the next — cheap to insert into, but with no fast access by position.
tree
A hierarchy of nodes with one root, where each node has children but no cycles.
binary search tree concept
A tree keeping values ordered so search can discard half the remaining nodes at each step.
heap concept
A tree-shaped structure that keeps the smallest (or largest) item instantly available, used for priority queues.
graph
Nodes connected by edges, with no hierarchy required and cycles allowed — the model for networks and dependencies.
Resources for this subject
REFERENCEOpenDSA — Data Structures and Algorithms Virginia Tech A complete open textbook with interactive visualisations, covering every structure and algorithm Stage 5 requires you to implement.Open
Need another explanation?2 more references
REFERENCEVisuAlgo visualgo.net Step-by-step animations of sorting, traversal, BFS and DFS. Use it to check your mental model after implementing, not before.Open
REFERENCEData Structures — Python Tutorial Python Software Foundation What Python's built-ins actually guarantee. Read after implementing your own, to see which trade-offs the standard library already made.Open
A reviewer should be able to answer these
Answer from memory, out loud, before moving on. These are not tracked and do not affect the gate — they tell you whether you actually understand this subject.
What operations does a stack make cheap, and what does it make impossible?
Why is lookup in a hash map faster than scanning a list, and when is it not?
What does a tree give you that a flat list does not?
When would you use a queue instead of a stack, and what real problem forces that?
What is the cost of inserting at the front of an array-backed list, and why?
What does a set enforce that a list does not, and what does that cost?
What is a graph made of, and how would you store one in a dictionary?
What is a heap for, and what question does it answer quickly?
Exercises
Demonstrated practice · 35% base weight
stack
warmup ~40 min
Implement a stack from scratch with explicit push, pop and peek.
What to implement
Implement push, pop, peek and is_empty.
Raise a clear error when popping from empty.
Do not use a library implementation.
State the complexity of each operation.
Add a size operation and keep it O(1).
Done when
Tests cover the empty case, single element and many elements.
You can state why each operation is O(1).
Popping from an empty stack raises the error you designed, not an incidental one.
Your tests would fail if push and pop were reversed.
One hint, available after you have made a real attempt.
queue
core ~45 min
Implement a FIFO queue and confront the cost of removing from the front.
What to implement
Implement enqueue, dequeue and is_empty.
Handle dequeue from empty explicitly.
Measure or reason about the cost of removing from the front of a list.
State the complexity of each operation.
Implement a second version using a structure with cheap removal at the front, and compare.
Done when
You can explain why the naive list-based dequeue is not O(1).
Tests cover ordering across many operations.
You have measured or reasoned about both versions and can state the difference.
Ordering is verified across interleaved enqueue and dequeue calls, not just sequential ones.
One hint, available after you have made a real attempt.
hash-based frequency table using Python dict
core ~40 min
Build a frequency table with a dict and explain why lookup does not scan.
What to implement
Count occurrences across a sequence.
Handle the first-occurrence case cleanly.
Return the top N by count.
Explain why dict lookup is roughly constant time.
Handle keys that are not strings and say what a key must support.
Done when
Counts are correct on a large input.
You can describe what a hash function is doing on your behalf.
You can state what property a key needs for the structure to work.
Your top-N result is stable for equal counts under a rule you chose.
One hint, available after you have made a real attempt.
binary search
core ~50 min
Implement binary search and prove it is correct at the boundaries.
What to implement
Implement it iteratively.
Return the index, or a clear not-found signal.
Test the first element, last element, absent element and empty list.
State and check the precondition.
Handle duplicates explicitly, and state which occurrence you return.
Done when
Every boundary case has a passing test.
You can state the precondition the algorithm depends on.
A two-element list and a one-element list both behave correctly.
You can hand-trace the loop for an absent value and reach the not-found path.
One hint, available after you have made a real attempt.
insertion/selection sort for learning
core ~60 min
Implement two quadratic sorts to feel why they do not scale.
What to implement
Implement insertion sort and selection sort.
Verify both produce the same result as the built-in sort.
Count comparisons for inputs of growing size.
Explain the growth you observed.
Test both on already-sorted and reverse-sorted input.
Done when
Comparison counts show quadratic growth.
You can explain when insertion sort beats selection sort.
You can explain why one of them is much faster on nearly-sorted input.
Your comparison counts are reproducible for the same input.
One hint, available after you have made a real attempt.
tree traversal
core ~60 min
Build a small tree and traverse it in more than one order.
What to implement
Define a node structure with children.
Implement at least two traversal orders.
Show the visit order differs and explain why.
Handle an empty tree.
Implement one traversal iteratively as well as recursively.
Done when
Two traversals of the same tree produce different, explainable orders.
The empty case does not crash.
The recursive and iterative versions produce identical orders.
A single-node tree and a deeply unbalanced tree both work.
One hint, available after you have made a real attempt.
BFS
core ~60 min
Implement breadth-first search over a graph and handle cycles.
What to implement
Represent a graph with adjacency.
Traverse level by level using a queue.
Track visited nodes so cycles terminate.
Return nodes in visit order.
Record the distance from the start node to each node you visit.
Done when
A graph containing a cycle terminates.
The visit order is genuinely level-by-level.
A disconnected graph reports the unreachable nodes rather than looping.
Distances match a hand-drawn version of the same graph.
One hint, available after you have made a real attempt.
DFS
core ~60 min
Implement depth-first search and compare it directly against BFS.
What to implement
Implement DFS on the same graph as BFS.
Track visited nodes.
Implement it once recursively and once iteratively.
Compare the visit order against BFS and explain it.
Report the nodes reachable from the start, and confirm both versions agree.
Done when
Both implementations agree on reachability.
You can explain when depth-first risks a stack overflow.
The iterative version handles a graph deep enough to worry the recursive one.
You can explain the visit-order difference from BFS on the same graph.
One hint, available after you have made a real attempt.
Stage project
Only milestones owned by Stage 5 count here
No ladder milestone is assigned to this stage. Use the exercises and gate evidence as the implementation surface.
Resources
0% progress weight
Resource status is a convenience marker only. It cannot change competencies, gates, or stage completion — in any tier below.
Start here — no canonical resource for this stage
3 available
The curriculum names no resource for this stage. These are authored suggestions, not part of the canonical library.
REFERENCEOpenDSA — Data Structures and Algorithms Virginia TechA complete open textbook with interactive visualisations, covering every structure and algorithm Stage 5 requires you to implement.Stage 5 has no primary resource in the canonical library. This is the closest complete substitute.Open
REFERENCEVisuAlgo visualgo.netStep-by-step animations of sorting, traversal, BFS and DFS. Use it to check your mental model after implementing, not before.Open
REFERENCEBig-O Cheat Sheet bigocheatsheet.comA one-page comparison of operation costs across structures. Useful for checking the complexity claims your gate requires you to defend.Open
Need another explanation?2 supplementary resources · not part of the canonical library
Use these for a demonstrated gap, not as a parallel course. They are authored additions and can never be the primary resource for a subject.
REFERENCEData Structures — Python Tutorial Python Software FoundationWhat Python's built-ins actually guarantee. Read after implementing your own, to see which trade-offs the standard library already made.Open
OPTIONALNeetCode Roadmap neetcode.ioA structured problem sequence. Use sparingly — Stage 5 explicitly warns against becoming a LeetCode specialist.Bounded by the stage's own interview constraint: use problems to reinforce decomposition and complexity, not as the goal.Open
Stage gate
Readiness assessment
Not ready
Stage-specific requirements
Answer each prompt without notes. Expand a question only when you are ready to check your answer.
0/1
For a routine algorithm, explain why one implementation scales better than another
Answer
Name the operations each implementation performs as the input grows, and state the resulting growth class rather than a timing. Then say where the difference comes from: a hash lookup does not scan, binary search halves the space each step and so requires sorted input, a nested loop over the same collection grows quadratically. Finish with the caveat that constants and input size decide which one actually wins in practice.
Universal requirements
The eight conditions 01_LEARNING_RULES.md applies to every stage. Expand one to see what it actually asks for.
0/8
Core concepts can be explained from memory.
What this asks for
Every subject in this stage has review questions. The condition is met when you can answer them out loud, without notes and without looking anything up, in your own words rather than a recited definition. An explanation you can only give with the material open is recognition, not recall.
Required exercises are complete.
What this asks for
Complete means each exercise satisfies its stated requirements and its done-when criteria, not that you attempted it. Where an exercise says you should be able to explain or defend something, that explanation is part of completing it. A stage whose source lists no exercises meets this through its owned project milestone instead.
Stage project works.
What this asks for
Works means it runs end to end from a clean checkout, on the inputs it was built for, with the failure cases it claims to handle actually handled. It is not a notebook that produced a result once. Someone else following your README should be able to run it without asking you a question.
Tests or verification exist.
What this asks for
There is something that would fail if the behaviour regressed, and you have watched it fail. That can be automated tests or a written verification procedure with recorded results, depending on what the stage produces. A test that has only ever passed is evidence of nothing.
README explains decisions.
What this asks for
The README says what the project is, how to install, run and test it, and why it is built the way it is: the choices you made, the alternatives you rejected, and what you deliberately left out. A list of commands with no reasoning does not meet this condition.
You can reproduce the core implementation without copying.
What this asks for
Delete the central piece and write it again from an empty file, without your previous version, a tutorial, or generated code in front of you. It does not have to be identical, it has to work and you have to be able to explain every line. This is the condition that separates having finished from being able.
You pass the stage self-assessment at >= 80%.
What this asks for
Record a gate exam and score yourself honestly against the dimensions the roadmap defines: recall, implementation, debugging, testing and design judgment. Elapsed time, hours watched and completed resources count for nothing here. Checking the boxes without a recorded exam does not open the gate.
Claude/ChatGPT reviewer finds no foundational blocker.
What this asks for
Ask an AI reviewer to examine the work against this stage's concepts and report foundational misunderstandings, not style. A foundational blocker is a misconception that later stages would build on, such as leakage, a broken abstraction, or an explanation that is confidently wrong. Nothing in that class may remain open when you pass.
Recorded exam
No exam recorded. Checking every requirement is not sufficient.