Find a concept by its name or browse concepts by topic.
All sixteen topics have aligned self-reading explanations; Topics 14–15 are optional extensions beyond the lecture inventory. The integrated application adapts the common structure to questions, models, methods and interpretation.
Browse by topic¶
Find a concept alphabetically¶
This index covers developed explanations in Topics 1–16. Entries link directly to the relevant section.
A¶
B¶
C¶
D¶
E¶
F¶
G¶
H¶
I¶
K¶
L¶
M¶
N¶
O¶
P¶
Q¶
R¶
S¶
T¶
U¶
W¶
Spatial operation extensions¶
| Concept | Explanation |
|---|---|
| K-d deletion / axis minimum | Replacement without changing depth |
| Point-quadtree deletion | Rebuild an affected subtree |
| Cell distance lower bound | Point-to-box squared distance |
| PR nearest search | Bounds and bucket tests |
| PR deletion and merging | Remove and coalesce siblings |
| R-tree insertion / splitting | Least enlargement and overflow |
| R-tree exact geometry lookup | Object equality after filtering |
| R-tree nearest search | Exact distance after MBR bounds |
| R-tree CondenseTree | Underflow and reinsertion |
Sorting implementation choices¶
| Concept | Explanation |
|---|---|
| Merge sort | Sorting contract, choices and costs |
| Natural run / Timsort | Reuse ordered stretches |
| Powersort | Run lengths and merge scheduling |
| Mutation versus in-place space | Separate interface and storage guarantees |
| Sorting implementation comparison | Version-specific costs and guarantees |
Graph and disjoint-set operation routes¶
Analysis reasoning routes¶
Recursion reasoning routes¶
Foundation reasoning routes¶
Design and string operation routes¶
Concepts grouped by topic¶
1. Foundations and Python’s object model¶
Data structures and algorithms
Objects and references
Mutation and copying
Collections and classes
2. Analysing algorithms¶
Counting work
Growth rates
Cases and bounds
Code and space
3. Recursion and divide-and-conquer¶
Recursive calls and termination
The call stack
Divide, conquer and combine
Recursion trees and costs
Implementation costs
4. Sorting¶
5. Sequences, stacks, queues and deques¶
ADTs and contracts
Stacks: newest first
Queues and deques
Arrays and positional operations
Dynamic arrays: length, capacity and resizing
Linked structures and safe updates
Circular-array queues
Linked queues
Choosing an ADT and representation
6. Maps, sets and hashing¶
Maps
Sets
Hashing
Separate chaining
Open addressing
Performance
Choosing a structure
7. Searching and binary search trees¶
Binary search and candidate intervals
Trees and whole-subtree ordering
BST lookup and insertion
Traversal and ordered operations
BST deletion without losing subtrees
Search costs and representation choices
8. Balanced search trees¶
Heights, balance factors and AVL invariants
Rotations and subtree transfer
LL, RR, LR and RL cases
AVL insertion
AVL deletion and upward repair
9. Spatial search and indexing¶
Self-reading support: use the topic’s check-by-concept table to find prediction questions and expandable explanations.
Split rules and k-d-tree construction
Exact-point search and coordinate ties
Range search and safe pruning
Shape, median construction and limitations
Nearest-neighbour search and backtracking
Spatial queries, bounds and a reference scan
Point quadtrees: split through a stored point
Point-region quadtrees: split the region at its midpoint
PR-quadtree insertion, lookup and range reporting
R-trees: group objects inside enclosing rectangles
Query an R-tree, then refine the candidates
Compare spatial-search representations
10. Priority queues and heaps¶
Priority queues: select by importance
Heap order, complete shape and array indices
Insertion and sift-up
Root removal and sift-down
Bottom-up heap construction
Python heaps, records and ties
Heapsort, operation costs and choices
11. Graphs and traversal¶
Graph concepts and modelling
Adjacency lists and matrices
Breadth-first search: layers and a FIFO frontier
Depth-first search: active paths and returns
Reachability and connected components
Traversal costs and algorithm choice
12. Union–find¶
Partitions and representatives
Parent forests and finding a root
Union by size and path compression
Connectivity, cycle checks and limits
13. Graph ordering, paths and spanning trees¶
DAGs and topological order
Shortest paths and relaxation
Dijkstra’s algorithm and lazy heap entries
Shortest paths in a DAG
Spanning trees and safe edges
Prim: grow a tree across a cut
Kruskal: sort edges and merge components
Compare graph objectives before selecting an algorithm
14. Algorithm design and sequence patterns¶
Choose a strategy from the problem
Greedy design and exchange reasoning
Dynamic programming: states, reuse and reconstruction
Backtracking and safe pruning
Prefix sums, two pointers and sliding windows
Complexity, output size and practical limits
15. Strings, tries and pattern matching¶
String models and query contracts
Trie representation and complete keys
Maintaining a trie string set
Prefix reporting and longest stored prefixes
A substring-search baseline
KMP: reuse information after a mismatch
Rolling hashes: filter, then verify
Choosing a string method
16. Integrated applications¶
Model places, links and two kinds of cost
A visitor asks for the fewest links
A visitor asks for the least travel time
An operator asks whether places are connected
A planner asks for the cheapest connecting network
Compare the answers before making a decision
Review additions to Topics 2 and 7¶
Correctness, termination and evidence
Binary-search boundaries and duplicate runs
Ordered range queries in a BST