Skip to content

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.

19 chapters · 30 sectionsEN · 繁 · 简
My course notes

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.

Open this course in the knowledge map

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.

Open this course in the knowledge map

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.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

  1. 2.1

    A FIFO queue built from two stacks

    Prove the queue invariant and account for occasional expensive transfers.

  2. 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.

  3. 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

  1. 3.1

    Binary min-heaps and priority queues

    Prove binary min-heap invariants and analyze insertion and removal of a minimum.

  2. 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

  1. 4.1

    Selecting by rank in a search tree

    Prove rank selection and maintain subtree counts under insertion, deletion and rotations.

  2. 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

  1. 5.1

    Separate chaining and expected collision cost

    Trace chained lookup and prove expected bounds under a pairwise collision assumption.

  2. 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

  1. 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

  1. 7.1

    Trie prefixes, terminal markers and safe pruning

    Maintain exact string membership and prefix enumeration, and prove deletion preserves shared paths.

  2. 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

  1. 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

  1. 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

  1. 10.1

    Sentinel lists and node splicing

    Reason from local links to global membership and account for search and size costs.

  2. 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

  1. 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

  1. 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

  1. 13.1

    Breadth-first search: queues and shortest paths

    Trace discovery-time marking, prove the layer invariant and reconstruct shortest unweighted paths.

  2. 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

  1. 14.1

    Kruskal's algorithm: union–find and spanning forests

    Prove the forest invariant and the greedy cut exchange, then trace union by size.

  2. 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

  1. 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.

  2. 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

  1. 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

  1. 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

  1. 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.

  2. 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

  1. 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.

Vercel visit statistics and public-page performance measurements each require separate consent. Neither is needed to use the website.

Website function storage (used when needed)

Security, sign-in and your chosen preferences use storage when needed. This is separate from optional statistics.

Withdrawing stops future statistics. The page reloads if analytics code needs unloading. It does not delete data already sent.

Read Cookie and storage details