Reference Tables, Teaching Sequence and Glossary

References for further study and the course glossary.

Reference Tables

Common data-structure complexity overview Array / vector Index O(1), search O(n) End O(1) amortized; middle O(n) Singly linked list Position lookup costs O(n) Enqueue O(1) Dequeue O(1) Expected O(1) Worst case can be O(n) Assumes maintained balance Extract O(log n) Not a general sorted search structure O(L) typical L is key length Amortized O(α(n))

With path compression + union by size/rank Prefix query O(log n) Update O(log n) Supports suitable aggregate operations Range query O(log n) Point update O(log n)

Lazy propagation supports selected range updates Common algorithm complexity overview Extra space / note O(1) iterative Usually O(n) for arrays Average O(n log n), worst O(n²) Depends on implementation O(1) auxiliary for in-place variant O(V) visited/stack/queue Dijkstra with binary heap Commonly O((V+E) log V) Depends on graph representation O(V) beyond graph storage DSU + edge sorting O(m) prefix table Standard 0/1 knapsack DP Can be reduced to O(W) space Segment tree query/update O(n) storage, usually

Recommended Teaching Sequence

Introduction, correctness, and complexity.

Math and bitwise foundations.

Arrays, strings, and hashing.

Searching and sorting.

Linked lists, stacks, queues, and deques.

Recursion, backtracking, and divide and conquer.

Trees, BSTs, balanced trees, heaps, and tries.

Prefix sums, two pointers, sliding windows, and monotonic structures.

Dynamic programming from basic to advanced.

Graph representation, BFS, DFS, topology, shortest paths, and MST.

DSU, SCC, bridges, articulation points, flow, and matching.

Fenwick trees, segment trees, sparse tables, and offline queries.

String algorithms from KMP to suffix structures.

Number theory, combinatorics, geometry, and randomized algorithms.

Specialized structures, advanced DP optimization, and competitive programming.

Interview practice, timed revision, and capstone projects.

The modules are numbered in the course's original order; this sequence interleaves them. For example, step 4 (searching and sorting, Modules 17–18) comes before linked lists (Module 7) in this sequence.

Glossary

Abstract data type (ADT): a set of values and operations specified by behaviour, independent of implementation.

Adjacency list: a graph representation storing, for each vertex, its neighbours; O(V + E) memory.

Amortized cost: average cost per operation over any sequence of operations.

Articulation point: a vertex whose removal increases the number of connected components.

AVL tree: a binary search tree in which sibling subtree heights differ by at most one.

Backtracking: systematic search that builds a solution step by step and undoes choices that cannot succeed.

Big-O: an asymptotic upper bound on growth.

Binary heap: a complete binary tree in array form where each parent is ordered before its children.

Binary search: repeatedly halving a sorted range or the domain of a monotone predicate.

Bloom filter: a bit array with several hash functions that answers “definitely absent” or “possibly present”.

Bridge: an edge whose removal disconnects its component.

Cache locality: the tendency of fast code to access memory addresses near recently used ones.

Cut property: the lightest edge crossing any cut belongs to some minimum spanning tree.

DAG: a directed acyclic graph.

Dynamic programming: solving overlapping subproblems once each and combining their results.

Exchange argument: a proof that transforms an optimal solution into the greedy one without making it worse.

Fenwick tree: an array-based structure for prefix sums with point updates in O(log n).

Hash collision: two different keys mapping to the same bucket or hash value.

In-place: using only a small, typically constant, amount of extra memory.

Invariant: a property that holds before and after every step of an algorithm.

Load factor: elements divided by buckets in a hash table.

Loop invariant: an invariant used to prove a loop correct.

Lowest common ancestor (LCA): the deepest node that is an ancestor of two given nodes.

Memoization: caching the results of recursive calls.

Minimum spanning tree (MST): a spanning tree of minimum total edge weight.

Monotonic stack: a stack kept in sorted order by popping elements that can no longer be answers.

Path compression: making every node on a find path point directly to the root in union-find.

Prefix function: for each position, the length of the longest proper prefix that is also a suffix.

Prefix sum: the sum of the first i elements, enabling O(1) range sums.

Quickselect: a partition-based algorithm for the k-th smallest element in expected O(n).

Residual graph: the graph of remaining capacities and reverse edges used by max-flow algorithms.

Segment tree: a tree over array intervals supporting range queries and updates in O(log n).

Sliding window: a contiguous range whose ends move monotonically across an array.

Sparse table: a precomputed table answering static idempotent range queries in O(1).

Stable sort: a sort that keeps equal elements in their original relative order.

Strongly connected component: a maximal set of vertices in a directed graph that are mutually reachable.

Suffix array: the starting positions of all suffixes of a string in sorted order.

Topological order: an ordering of a DAG's vertices in which every edge points forward.

Trie: a tree of characters in which each path from the root spells a key prefix.

Union-find (DSU): a structure maintaining disjoint sets under merging with near-constant-time operations.