Skip to content

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.

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

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.

Open this course in the knowledge map

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.

Open this course in the knowledge map

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

  2. 1.2

    Segment trees for assignment and range minimum

    Prove segment-tree invariants and logarithmic range-minimum queries under point assignment.

  3. 1.3

    Segment trees: associative summaries and ordered range queries

    Develop ordered segment queries for associative summaries and distinguish point updates from lazy propagation.

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

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

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

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

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

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

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

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

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

  2. 8.2

    Orientation and closed-segment intersection

    Classify exact intersections, including collinear and degenerate segments.

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

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

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

  1. 10.1

    Iterative low-link traversal and bridge forests

    Trace iterative low-link computation with edge IDs and construct the forest left by bridges.

  2. 10.2

    Strong components, finishing order and condensation

    Derive the two-pass directed DFS algorithm and its acyclic condensation.

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

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

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

  1. 13.1

    Heavy-light paths and query boundaries

    Prove the light-edge bound and split vertex and edge paths into range-query intervals.

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

  1. 14.1

    Subset states, Hamiltonian tours and optimal witnesses

    Derive an exact visited-set dynamic program and reconstruct an optimal directed tour.

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

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

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

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

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

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

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

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

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

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