Skip to content

CSCI3160

Design and Analysis of Algorithms

Correctness and divide and conquer, amortized and randomized analysis, dynamic programming, greedy algorithms and matroids, shortest paths, network flows and matching, and NP-completeness.

9 chapters · 45 sectionsEN · 繁 · 简
My course notes

Your progress

0/ 45 sections marked complete

Next section: Correctness, cost models, and divide and conquer

Completion marks are saved in this browser.

This course in the web

In the CSCI3160 notes

Theorem cards
111
Definitions
84
Counterexamples
61
Concept lenses
30
Histories of ideas
1
Proof X-rays
53

Sections with a history of an idea

None of these is on the timeline yet.

No concept lens from this course is recorded in the web yet.

Open this course in the knowledge map

Counts cover the 45 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 111 · Definitions 84 · Counterexamples 61 · Concept lenses 30 · Histories of ideas 1 · Proof X-rays 53

None of these is on the timeline yet.

No concept lens from this course is recorded in the web yet.

Open this course in the knowledge map

Counts cover the 45 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 · 12 sections

Correctness and divide and conquer

Correctness and divide and conquer

Theorems 25 · Definitions 19Counterexamples 15Lenses 9Proof X-rays 13

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 1.1

    Correctness, cost models, and divide and conquer

    Prove iterative and recursive algorithms correct, distinguish input sizes and running-time bounds, and derive merge sort's recurrence.

  2. 1.2

    Binary counters and amortized analysis

    Prove a sequence bound by aggregate counting and a potential, including wraparound and mixed-operation limits.

  3. 1.3

    Binary search through a feasibility boundary

    Prove boundary search for a monotone predicate, then minimize the largest contiguous block sum using a proved greedy feasibility test.

  4. 1.4

    The master theorem with asymptotic tolls

    Prove three common recurrence regimes and the role of the regularity condition.

  5. 1.5

    Divide-and-conquer recurrence trees

    Derive the three cases of a power-toll recurrence by summing work across levels.

  6. 1.6

    Karatsuba multiplication

    Derive three-product multiplication and analyze rounded recursive sizes.

  7. 1.7

    Fast Fourier transforms and convolution

    Derive radix-two butterflies, inversion and zero-padded polynomial multiplication.

  8. 1.8

    Comparison sorting lower bounds

    Prove the decision-tree lower bound and distinguish comparison sorting from counting sort.

  9. 1.9

    Expected comparisons in randomized quicksort

    Derive quicksort's exact expected comparison count from pair indicators.

  10. 1.10

    Worst-case linear-time selection

    Choose a pivot from medians of five and prove a linear comparison bound.

  11. 1.11

    Randomized selection and expected linear work

    Prove an expected linear bound for quickselect using balanced pivot phases.

  12. 1.12

    Amortized analysis of dynamic arrays

    Use aggregate and potential arguments to bound the cost of doubling an array.

Chapter 2 · 11 sections

Dynamic programming and greedy algorithms

Dynamic programming and greedy algorithms

Theorems 24 · Definitions 18Counterexamples 15Lenses 10Proof X-rays 12

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 2.1

    Longest common subsequences

    Derive a prefix dynamic program and reconstruct an optimal common subsequence.

  2. 2.2

    Matrix-chain dynamic programming

    Derive, compute and reconstruct an optimal parenthesization of matrix products.

  3. 2.3

    Greedy choices and dynamic programming

    Prove interval scheduling by exchange, derive weighted interval and knapsack recurrences, and explain state design and reconstruction.

  4. 2.4

    Longest increasing subsequences: states, tails and reconstruction

    Prove a quadratic dynamic program and a binary-search method for strict increasing subsequences, including an actual witness.

  5. 2.5

    Reading a weighted scheduling trace

    Compare predecessor prefixes and reconstruction decisions in a six-job example.

  6. 2.6

    Single-machine scheduling and adjacent exchanges

    Prove due-date and processing-to-weight rules under explicit scheduling assumptions.

  7. 2.7

    Huffman coding and the greedy exchange

    Prove optimality of merging the two least weights in a binary prefix code.

  8. 2.8

    Greedy optimization over matroids

    Prove the weighted greedy theorem using augmentation and basis exchange.

  9. 2.9

    Knapsack: fractional greedy and zero-one dynamic programming

    Prove the fractional density rule, derive a zero-one capacity dynamic program, and reconstruct selected items.

  10. 2.10

    Edit distance and dynamic programming

    Derive the edit-distance recurrence and reconstruct an optimal sequence of edits.

  11. 2.11

    Optimal binary search trees

    Use interval dynamic programming for successful and unsuccessful search costs.

Chapter 3 · 10 sections

Graphs and network flows

Graphs and network flows

Theorems 24 · Definitions 23Counterexamples 15Lenses 4Proof X-rays 13

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 3.1

    Maximum flow and minimum cuts

    Use residual networks to prove optimality and compute maximum flows.

  2. 3.2

    Graph algorithms through their invariants

    Prove traversal, spanning-tree, and shortest-path algorithms with explicit graph, weight, and data-structure assumptions.

  3. 3.3

    Bipartite matching, Hall's condition and cover certificates

    Use alternating paths to construct optimality certificates and prove Hall's theorem.

  4. 3.4

    Topological order and shortest paths in DAGs

    Prove topological sorting and linear-time shortest paths with negative edges in acyclic graphs.

  5. 3.5

    Strongly connected components

    Prove the finishing-time ordering behind the two-pass component algorithm.

  6. 3.6

    All-pairs shortest paths by dynamic programming

    Derive the Floyd–Warshall recurrence and its in-place update under explicit hypotheses.

  7. 3.7

    Prim's minimum spanning tree algorithm

    Prove the growing-tree invariant and account for binary-heap operations.

  8. 3.8

    Disjoint-set forests and union by size

    Prove logarithmic tree height for union by size and apply the structure to Kruskal's algorithm.

  9. 3.9

    Shortest augmenting paths and polynomial flow

    Prove the Edmonds–Karp augmentation bound using residual distances.

  10. 3.10

    Bipartite matching and Hall certificates

    Find augmenting paths and derive matching, cover and Hall certificates.

Chapter 4 · 6 sections

Reductions and NP-completeness

Reductions and NP-completeness

Theorems 13 · Definitions 15Counterexamples 6Lenses 5History 1Proof X-rays 7

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 4.1

    Polynomial reductions and NP-completeness

    Separate verification from search, prove the direction of reductions, and construct complete reductions from 3-SAT to clique and vertex cover.

  2. 4.2

    From Boolean formulas to 3-SAT

    Construct gate clauses and long-clause chains, prove their exact assignment-extension property, and derive 3-SAT completeness from the stated SAT starting theorem.

  3. 4.3

    A reduction from 3-SAT to three-coloring

    Build and verify an explicit clause gadget for three-colorability.

  4. 4.4

    A reduction from 3-SAT to subset sum

    Encode variable choices and clause satisfaction in carry-free decimal columns.

  5. 4.5

    Hamiltonian paths, cycles and traveling-salesperson reductions

    Transform Hamiltonian witnesses between graph models and compare metric with arbitrary tour costs.

  6. 4.6

    Approximation algorithms: vertex cover and set cover

    Define approximation ratios, prove that a maximal matching gives a 2-approximate vertex cover, and prove the harmonic-number guarantee of greedy set cover.

Chapter 5 · 1 section

Prefix codes

Greedy merging and optimal weighted binary codes.

Theorems 4 · Definitions 2Counterexamples 2Lenses 1Proof X-rays 1

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 5.1

    Huffman coding and the greedy exchange

    Prove the two-smallest merge rule for nonnegative weighted binary prefix codes.

Chapter 6 · 1 section

Matroids and greedy algorithms

Use augmentation to prove a weighted greedy theorem.

Theorems 2 · Definitions 1Counterexamples 2Proof X-rays 1

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 6.1

    Why weighted greedy works for matroid bases

    Prove the maximum-weight basis theorem using prefix ranks, and distinguish bases from arbitrary independent sets.

Chapter 7 · 2 sections

Shortest paths

Prove relaxation with edge budgets and identify relevant negative cycles.

Theorems 10 · Definitions 4Counterexamples 3Proof X-rays 3

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 7.1

    Bellman–Ford: relaxation, edge budgets and negative cycles

    Derive shortest-path relaxation from a bounded-edge recurrence and distinguish reachable negative cycles.

  2. 7.2

    Dijkstra: settled vertices and lazy priority queues

    Prove nonnegative-edge finalization and track lazy heap witnesses.

Chapter 8 · 1 section

Dynamic programming: reconstruction

Reconstruct a longest common subsequence with explicit time and space accounting.

Theorems 6 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 8.1

    LCS: prefix invariants and space-aware reconstruction

    Derive the LCS recurrence and reconstruct a witness with explicit memory accounting.

Chapter 9 · 1 section

Divide and conquer applications

Geometric divide and conquer and ordering invariants.

Theorems 3 · Definitions 1Counterexamples 2Proof X-rays 2

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 9.1

    Closest pairs and strip packing

    Prove the strip bound and return exact squared-distance witnesses.

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