Advanced Topics in Computer Science Study Guide
Ten units from a Java and design bridge through the classic data structures to graphs and the consequences of computing. Each unit explains what to know, how to apply it, what typically goes wrong, and one study move that makes the material stick.
Ten units
From a Java and design bridge, through recursion and the classic data structures, to graphs and the social consequences of computing.
No national exam
This is an honors course set by the school rather than the College Board, so assessment is by class tests, projects, and implementation work.
Prerequisite
AP Computer Science A or equivalent Java fluency. The course assumes classes, arrays, ArrayList, and recursion are already familiar.
Where it leads
College data structures and algorithms, competitive programming, and technical interviews.
Units
Unit 1 is the largest by a wide margin. The rest move faster, and the last one is the bridge into calculus.
Unit 0 · Bridge unit
The bridge from AP CSA into honors work. It re-establishes Java fluency and then adds the habits the rest of the course assumes: designing before coding, testing deliberately, and explaining a decision in writing.
Unit 1 · Foundational
Solving a problem by defining a smaller version of itself. The unit is less about writing recursive code than about arguing that it terminates and that the recursive step actually covers the problem.
Unit 2 · Heavy
Where the course starts comparing solutions rather than just producing them. The sorts are the vehicle; asymptotic reasoning is the actual subject.
Unit 3 · Moderate
The first structure with no indexing. Everything is reached by following references, which trades constant-time access for cheap insertion and removal once you are already in position.
Unit 4 · Moderate
Two abstract data types defined by a restriction rather than a capability. The restriction is the point: limiting which element is reachable is what makes each fit a specific class of problem.
Unit 5 · Heavy
Lookup by key instead of by position. Hashing is the first place where average and worst case diverge sharply, which makes stating the case a required part of every answer.
Unit 6 · Heavy
The first genuinely recursive structure, where the recursion of the code mirrors the recursion of the data. Binary search trees are fast only while they stay balanced, and that caveat is the unit.
Unit 7 · Moderate
A tree with a weaker ordering than a BST, which is exactly what makes it cheap to maintain. The heap property constrains parents against their own children only, so the extreme value sits at the root and nothing else is sorted.
Unit 8 · Heavy
The most general structure in the course, and the one where the choice of representation changes the complexity of everything built on top of it.
Unit 9 · Assessed seriously
The consequences of the systems built in the other nine units. It is assessed with the same rigour as the technical material and rewards specific, traceable reasoning rather than general opinion.
Mathematical Practices
Four habits this course assesses directly: stating a guarantee, arguing correctness, comparing by growth, and tracing pointers carefully.
Before using a structure, say what it makes cheap and what it makes expensive. A stack is not merely a list with rules; it is a promise about which element is reachable, and that promise is why it fits some problems and not others.
A program that produces the right answer on your example is not yet shown correct. Name the invariant the loop maintains, or the base case and recursive step that cover every input.
Judge algorithms by how their work scales, not by how fast one run felt. Constant factors matter in practice, but the course assesses asymptotic reasoning.
Linked structures, trees, and graphs fail at the joins. Draw the nodes and redraw them after every reassignment rather than reasoning about the diagram in your head.
Assessment
Two lists: one for selected-response work, one for anything you have to write out.
Study plan
Four moves, in the order that pays off.
Most later units use recursion as a tool. Practise until you write the base case first by reflex and can state why it is reachable from every call.
For each structure, memorise what insertion, deletion, search, and access cost, and in which case. That table is the backbone of the whole course.
Insertion and deletion in linked lists, trees, and heaps are pointer choreography. Draw before coding and the code becomes transcription.
Write a stack, a queue, a binary search tree, and a hash map from scratch once. Nothing else produces the same understanding of their trade-offs.
Given a problem statement, name the structure and justify it before writing code. Selection is the skill the course actually assesses.
The societal unit is assessed with the same seriousness as the technical ones and rewards specific reasoning rather than opinion.
Curriculum scope
The organising idea is that a data structure is a set of guarantees, and choosing one is a decision about which operations must be fast. Every unit adds a structure, states what it makes cheap and what it makes expensive, and asks the student to justify the trade rather than memorise it.
Essential foundations
Included in this sequence
Compare with the school syllabus
Glossary
Abstract data type
A specification of operations and their meaning, independent of how they are implemented.
Invariant
A statement that remains true before and after each iteration or call, used to argue correctness.
Base case
The non-recursive branch that stops a recursion, which must be reachable from every call.
Amortised cost
The average cost per operation across a sequence, used when one operation is occasionally expensive.
Load factor
Entries divided by buckets in a hash table, which predicts collision frequency.
Collision
Two keys hashing to the same bucket, resolved by chaining or by probing.
Balanced tree
A tree whose height stays logarithmic in the number of nodes, guaranteeing fast search.
Heap property
The constraint that every parent compares correctly against its own children, which puts the extreme value at the root.
Adjacency list
A graph representation storing each vertex with its neighbours, using space proportional to vertices plus edges.
Topological order
An ordering of a directed acyclic graph in which every edge points forward.
