CSCI2100
Data Structures
Linked lists, stacks and queues, dynamic arrays, hashing, priority queues, binary, balanced and multiway search trees, tries, disjoint sets, sorting, graph algorithms and algorithm analysis.
Your progress
0/ 30 sections marked complete
Next section: Disjoint sets: partitions, forests and union–find
Completion marks are saved in this browser.
This course in the web
In the CSCI2100 notes
- Theorem cards
- 69
- Definitions
- 41
- Counterexamples
- 39
- Concept lenses
- 20
- Histories of ideas
- 0
- Proof X-rays
- 35
No concept lens from this course is recorded in the web yet.
Counts cover the 30 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
In the webTheorem cards 69 · Definitions 41 · Counterexamples 39 · Concept lenses 20 · Proof X-rays 35
No concept lens from this course is recorded in the web yet.
Counts cover the 30 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
Chapter 1 · 1 section
Disjoint sets
Partitions and union–find
Theorems 3 · Definitions 1Counterexamples 2Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 1.1
Disjoint sets: partitions, forests and union–find
Represent merging groups with a parent forest, prove root linking and path compression correct, and analyze union by size.
Chapter 2 · 3 sections
Linear data structures
Queue invariants, amortized analysis and linked-list cycle detection.
Theorems 7 · Definitions 3Counterexamples 4Lenses 2Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 2.1
A FIFO queue built from two stacks
Prove the queue invariant and account for occasional expensive transfers.
- 2.2
Finding a linked-list cycle without a visited set
Trace Floyd's pointers, prove why they meet, and locate and safely remove a cycle.
- 2.3
Two-stack queues: invariants and amortized cost
Trace front observers, transfer loops and amortized costs.
Chapter 3 · 2 sections
Priority queues
Heap invariants, insertion and minimum removal.
Theorems 6 · Definitions 2Counterexamples 2Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 3.1
Binary min-heaps and priority queues
Prove binary min-heap invariants and analyze insertion and removal of a minimum.
- 3.2
Building a min-heap from the bottom up
Prove sift-down correctness and the linear-time bound for building a heap in place.
Chapter 4 · 2 sections
Order statistics in search trees
Maintain subtree sizes and select a key by rank.
Theorems 2 · Definitions 2Counterexamples 2Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 4.1
Selecting by rank in a search tree
Prove rank selection and maintain subtree counts under insertion, deletion and rotations.
- 4.2
Selecting the smallest k records
Select exactly k records with a rank threshold and explicit ties, order and cost.
Chapter 5 · 2 sections
Hashing
Separate chaining and expected collision costs.
Theorems 3 · Definitions 5Counterexamples 2Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 5.1
Separate chaining and expected collision cost
Trace chained lookup and prove expected bounds under a pairwise collision assumption.
- 5.2
Linear probing and tombstone deletion
Trace bounded probing and prove the deletion and duplicate-key invariants.
Chapter 6 · 1 section
Probabilistic membership
Bloom filters, guarantees and false-positive models.
Theorems 2 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 6.1
Bloom filters and false positives
Distinguish the deterministic membership guarantee from an idealized false-positive model.
Chapter 7 · 2 sections
String tries
Exact membership, prefix enumeration and safe pruning.
Theorems 4 · Definitions 2Counterexamples 2Lenses 2Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 7.1
Trie prefixes, terminal markers and safe pruning
Maintain exact string membership and prefix enumeration, and prove deletion preserves shared paths.
- 7.2
Tracing exact lookup and prefix completion
Follow a trie query character by character and distinguish reached nodes from stored keys.
Chapter 8 · 1 section
Multiway search trees
Maintain B-tree occupancy and search invariants during insertion.
Theorems 3 · Definitions 1Counterexamples 2Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 8.1
B-trees: invariants, splitting and top-down insertion
Define a multiway search-tree contract, prove child splitting and insertion correct, trace a degree-two tree, and distinguish height, comparison and block-access costs.
Chapter 9 · 1 section
Self-adjusting search trees
Splay rotations and an amortized access proof.
Theorems 3 · Definitions 2Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 9.1
Splaying: rotations and the access lemma
Trace splaying and prove an unweighted amortized access bound.
Chapter 10 · 2 sections
Linked-list invariants
Sentinel rings, node ownership and the costs of splicing.
Theorems 3 · Definitions 2Counterexamples 3Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 10.1
Sentinel lists and node splicing
Reason from local links to global membership and account for search and size costs.
- 10.2
Recursive deletion and the returned head
Prove a recursive deletion contract while tracking node ownership and metadata.
Chapter 11 · 1 section
Dynamic arrays
Geometric resizing and amortized costs.
Theorems 2 · Definitions 1Counterexamples 2Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 11.1
Dynamic arrays and amortized cost
Trace resizing and prove an amortized update bound.
Chapter 12 · 1 section
Searching sorted arrays
Boundary search and loop invariants.
Theorems 3 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 12.1
Binary search: boundaries and loop invariants
Prove lower and upper bounds, handle duplicates and account for access costs.
Chapter 13 · 2 sections
Graph traversal
Queues, discovery and shortest paths in unweighted graphs.
Theorems 5 · Definitions 3Counterexamples 4Lenses 2Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 13.1
Breadth-first search: queues and shortest paths
Trace discovery-time marking, prove the layer invariant and reconstruct shortest unweighted paths.
- 13.2
Graph representations and depth-first search
Compare adjacency matrices and lists, then analyze depth-first search: timestamps, edge classification, cycle detection and topological order.
Chapter 14 · 2 sections
Graph algorithms
Minimum spanning forests and disjoint sets.
Theorems 7 · Definitions 4Counterexamples 3Lenses 2Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 14.1
Kruskal's algorithm: union–find and spanning forests
Prove the forest invariant and the greedy cut exchange, then trace union by size.
- 14.2
Weighted graph frontiers: Dijkstra and Prim
Trace Dijkstra's algorithm with a lazy heap and Prim's algorithm on one weighted graph, and prove why each finalizes or accepts safely.
Chapter 15 · 2 sections
Balanced search trees
AVL and red-black trees: height bounds and repair after updates.
Theorems 5 · Definitions 2Counterexamples 2Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 15.1
AVL trees: height, rotations and deletion
Prove the logarithmic height bound, preserve search order with rotations, and follow insertion and cascading deletion repairs.
- 15.2
Red-black trees: black height and insertion repair
Derive logarithmic search depth from color invariants, prove each insertion repair, and separate recoloring from rotations.
Chapter 16 · 1 section
Hash tables and universal hashing
Chaining, expected chain length and universal hash families.
Theorems 2 · Definitions 2Counterexamples 2Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 16.1
Hash tables: chaining, universal hashing and expected cost
Preserve a map through collisions, prove expected chain-length bounds with indicators, and construct a universal family using arithmetic modulo a prime.
Chapter 17 · 1 section
Binary search trees
Ordering invariant and deletion in an ordinary binary search tree.
Theorems 2 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 17.1
BST deletion: successor, subtree return and node identity
Delete from a binary search tree by successor replacement, return the new subtree root, and check the ordering invariant and cost.
Chapter 18 · 2 sections
Sorting
Merge sort on linked lists, array merge sort, quicksort and the comparison-sorting lower bound.
Theorems 5 · Definitions 4Counterexamples 2Lenses 2Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 18.1
Merge sort on linked lists: correctness is also about links
Merge sorted linked lists destructively and stably, split a list with slow and fast pointers, and analyze linked-list merge sort.
- 18.2
Comparison sorting: merge sort, quicksort and the lower bound
Analyze array merge sort and quicksort with invariants and recurrences, and prove that every comparison sort needs on the order of n log n comparisons.
Chapter 19 · 1 section
Analysis of algorithms
Cost models and asymptotic notation.
Theorems 2 · Definitions 2Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 19.1
Asymptotic notation and cost models
Fix a cost model, define O, Omega and Theta with explicit constants, and derive the growth classes of simple loop code.