CSCI2740
Competitive Programming
Range queries and segment trees, graph traversal, connectivity and shortest paths, string matching, number theory, computational geometry, dynamic programming, greedy methods and impartial games.
Your progress
0/ 33 sections marked complete
Next section: Binary indexed trees: intervals, updates, and prefix sums
Completion marks are saved in this browser.
This course in the web
In the CSCI2740 notes
- Theorem cards
- 97
- Definitions
- 54
- Counterexamples
- 50
- Concept lenses
- 17
- Histories of ideas
- 0
- Proof X-rays
- 47
No concept lens from this course is recorded in the web yet.
Counts cover the 33 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 97 · Definitions 54 · Counterexamples 50 · Concept lenses 17 · Proof X-rays 47
No concept lens from this course is recorded in the web yet.
Counts cover the 33 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 · 5 sections
Range queries
Derive Fenwick tree queries and updates from their stored-interval invariant, prove the logarithmic bounds, and distinguish addition from assignment and minimum queries.
Theorems 12 · Definitions 5Counterexamples 7Lenses 4Proof X-rays 5
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 1.1
Binary indexed trees: intervals, updates, and prefix sums
Derive Fenwick tree queries and updates from their stored-interval invariant, prove the logarithmic bounds, and distinguish addition from assignment and minimum queries.
- 1.2
Segment trees for assignment and range minimum
Prove segment-tree invariants and logarithmic range-minimum queries under point assignment.
- 1.3
Segment trees: associative summaries and ordered range queries
Develop ordered segment queries for associative summaries and distinguish point updates from lazy propagation.
- 1.4
Two-dimensional prefix sums and rectangle differences
Derive four-corner sum queries and offline rectangle additions, with half-open boundaries, empty rectangles and explicit preprocessing costs.
- 1.5
Square-root blocks: lazy additions and range sums
Maintain interleaved interval additions and sum queries by proving the relationship between stored entries, deferred block additions and true block totals.
Chapter 2 · 1 section
2. Static range queries
Precompute power-of-two intervals for static range minima.
Theorems 3 · Definitions 2Counterexamples 3Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 2.1
Sparse tables for static range minimum
Prove the power-of-two invariant and explain why overlapping minimum queries work.
Chapter 3 · 1 section
Graph connectivity
DFS low links and bridges in undirected multigraphs.
Theorems 2 · Definitions 2Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 3.1
DFS bridges in an undirected multigraph
Prove the low-link bridge criterion while preserving parallel-edge identities.
Chapter 4 · 1 section
Range updates
Endpoint differences for range additions and point values.
Theorems 1 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 4.1
Difference arrays and range-add endpoints
Prove the endpoint invariant for offline range addition and connect it to Fenwick point queries.
Chapter 5 · 1 section
Impartial games
Finite normal play, mex and xor.
Theorems 3 · Definitions 2Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 5.1
Mex values and the xor of impartial games
Prove the xor rule for finite impartial normal-play games and trace a subtraction game.
Chapter 6 · 1 section
Divisor sieves
Möbius divisor sums and counting coprime pairs.
Theorems 3 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 6.1
Möbius divisor sums and coprime pairs
Prove the divisor indicator and count coprime index pairs by a multiple sieve.
Chapter 7 · 1 section
Weighted interval scheduling
Build a dynamic program from compatible prefixes.
Theorems 1 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 7.1
Weighted interval scheduling
Derive the predecessor recurrence, reconstruction and complexity for weighted intervals.
Chapter 8 · 3 sections
Computational geometry
Use orientation and signed area to classify points relative to a convex polygon.
Theorems 9 · Definitions 5Counterexamples 4Lenses 2Proof X-rays 4
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 8.1
Signed area and points in a convex polygon
Use cross products, boundary tests and shoelace sums, with explicit convexity and integer-range assumptions.
- 8.2
Orientation and closed-segment intersection
Classify exact intersections, including collinear and degenerate segments.
- 8.3
Monotone-chain hulls and collinearity
Construct extreme hull vertices and prove the grouped-column monotone chain.
Chapter 9 · 2 sections
String algorithms
Use borders and fallback to search for overlapping string matches.
Theorems 9 · Definitions 4Counterexamples 3Lenses 1Proof X-rays 4
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 9.1
KMP string matching: borders, fallback and overlapping matches
Derive the prefix function from nested borders, prove linear-time pattern search, preserve overlaps, and recover the minimum period from the final border.
- 9.2
Z-arrays, box reuse and exact string matching
Prove linear prefix-match reuse and apply Z-values to exact matching, borders and periods.
Chapter 10 · 3 sections
Graph traversal and connectivity
Low links, bridges, directed components and vertex deletion.
Theorems 7 · Definitions 5Counterexamples 6Lenses 1Proof X-rays 7
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 10.1
Iterative low-link traversal and bridge forests
Trace iterative low-link computation with edge IDs and construct the forest left by bridges.
- 10.2
Strong components, finishing order and condensation
Derive the two-pass directed DFS algorithm and its acyclic condensation.
- 10.3
Articulation vertices, DFS roots and deletion counts
Derive the low-link vertex-deletion criterion and count remaining components.
Chapter 11 · 1 section
Binary exponentiation
Loop invariants, modular powers and matrix applications.
Theorems 2 · Definitions 1Counterexamples 2Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 11.1
Binary powers: loop invariants, matrix recurrences and walk counts
Prove binary exponentiation without commutativity and apply matrix powers.
Chapter 12 · 1 section
Monotone queues
Window extrema, dominance and amortized cost.
Theorems 3 · Definitions 1Counterexamples 2Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 12.1
Sliding-window minima: dominance, expiry and monotone deques
Prove dominance, handle duplicate witnesses and bound total deque work.
Chapter 13 · 2 sections
Heavy-light decomposition
Tree paths, subtree sizes and range-query boundaries.
Theorems 8 · Definitions 4Counterexamples 4Proof X-rays 4
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 13.1
Heavy-light paths and query boundaries
Prove the light-edge bound and split vertex and edge paths into range-query intervals.
- 13.2
Ancestor doubling, kth ancestors and lowest common ancestors
Compose powers of the parent map, prove the simultaneous-jump invariant for LCA, and answer static tree queries without inventing ancestors above the root.
Chapter 14 · 2 sections
Subset dynamic programming
Exact visited-set states, route costs and witnesses.
Theorems 8 · Definitions 3Counterexamples 3Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 14.1
Subset states, Hamiltonian tours and optimal witnesses
Derive an exact visited-set dynamic program and reconstruct an optimal directed tour.
- 14.2
Increasing subsequences: minimum tails and valid witnesses
Prove the minimum-tail invariant, handle equal values, and reconstruct an actual subsequence without treating the tail array as a witness.
Chapter 17 · 2 sections
Number theory
Congruences, the Chinese remainder theorem and the linear sieve.
Theorems 5 · Definitions 3Counterexamples 3Lenses 2Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 17.1
Exact algorithms: congruences and geometric orientation
Solve linear congruences with extended Euclid, combine congruences without assuming coprime moduli, and keep exact boundary checks for orientation tests and modular powers.
- 17.2
A linear sieve: smallest prime factors and repeated factorization
Prove a unique-generation rule for composite numbers, build a smallest-prime-factor table, and extract prime factors with explicit preprocessing, output and arithmetic costs.
Chapter 16 · 3 sections
Shortest paths
Bellman-Ford with negative cycles, and 0-1 BFS with a deque.
Theorems 13 · Definitions 7Counterexamples 4Lenses 3Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 16.1
Synchronous Bellman–Ford: Shortest Walks, Negative Cycles, and What an Extra Round Proves
Prove the bounded-length recurrence behind Bellman-Ford, classify distances as finite, infinite or negative-infinite, and read what the extra round establishes.
- 16.2
0–1 BFS: why a deque can replace a priority queue
Compute shortest distances when every edge costs 0 or 1 using a deque, with a proof of the two-key invariant, stale entries and complexity.
- 16.3
Dijkstra and Floyd–Warshall: Single-Source and All-Pairs Shortest Paths
Prove Dijkstra's algorithm for nonnegative weights, see exactly where negative edges break it, and derive the Floyd–Warshall recurrence for all-pairs distances.
Chapter 15 · 1 section
Searching and answer search
Binary search on a monotone feasibility predicate.
Theorems 2 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 15.1
Binary search on a capacity: prove the feasibility test first
Turn a minimization problem into a monotone yes-or-no test, prove the greedy feasibility check, and binary search the answer with safe bounds and arithmetic.
Chapter 18 · 1 section
Minimum spanning trees
Disjoint sets, Kruskal and Prim, and the cut property.
Theorems 3 · Definitions 3Counterexamples 1Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 18.1
Disjoint Sets, Kruskal's Algorithm and Prim's Algorithm
Prove the cut property for minimum spanning trees, implement Kruskal's algorithm on a disjoint-set union structure, and compare it with Prim's algorithm.
Chapter 19 · 1 section
Greedy algorithms
Exchange arguments for interval scheduling and job orders.
Theorems 3 · Definitions 3Counterexamples 2Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 19.1
Greedy Algorithms and Exchange Arguments: Interval Scheduling and Optimal Job Orders
State the greedy-choice pattern, prove it by exchange arguments for interval scheduling and for ordering jobs by weighted completion time, and see why plausible greedy rules fail.