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.
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.
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.
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
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.
- 1.2
Binary counters and amortized analysis
Prove a sequence bound by aggregate counting and a potential, including wraparound and mixed-operation limits.
- 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.
- 1.4
The master theorem with asymptotic tolls
Prove three common recurrence regimes and the role of the regularity condition.
- 1.5
Divide-and-conquer recurrence trees
Derive the three cases of a power-toll recurrence by summing work across levels.
- 1.6
Karatsuba multiplication
Derive three-product multiplication and analyze rounded recursive sizes.
- 1.7
Fast Fourier transforms and convolution
Derive radix-two butterflies, inversion and zero-padded polynomial multiplication.
- 1.8
Comparison sorting lower bounds
Prove the decision-tree lower bound and distinguish comparison sorting from counting sort.
- 1.9
Expected comparisons in randomized quicksort
Derive quicksort's exact expected comparison count from pair indicators.
- 1.10
Worst-case linear-time selection
Choose a pivot from medians of five and prove a linear comparison bound.
- 1.11
Randomized selection and expected linear work
Prove an expected linear bound for quickselect using balanced pivot phases.
- 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
- 2.1
Longest common subsequences
Derive a prefix dynamic program and reconstruct an optimal common subsequence.
- 2.2
Matrix-chain dynamic programming
Derive, compute and reconstruct an optimal parenthesization of matrix products.
- 2.3
Greedy choices and dynamic programming
Prove interval scheduling by exchange, derive weighted interval and knapsack recurrences, and explain state design and reconstruction.
- 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.
- 2.5
Reading a weighted scheduling trace
Compare predecessor prefixes and reconstruction decisions in a six-job example.
- 2.6
Single-machine scheduling and adjacent exchanges
Prove due-date and processing-to-weight rules under explicit scheduling assumptions.
- 2.7
Huffman coding and the greedy exchange
Prove optimality of merging the two least weights in a binary prefix code.
- 2.8
Greedy optimization over matroids
Prove the weighted greedy theorem using augmentation and basis exchange.
- 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.
- 2.10
Edit distance and dynamic programming
Derive the edit-distance recurrence and reconstruct an optimal sequence of edits.
- 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
- 3.1
Maximum flow and minimum cuts
Use residual networks to prove optimality and compute maximum flows.
- 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
Bipartite matching, Hall's condition and cover certificates
Use alternating paths to construct optimality certificates and prove Hall's theorem.
- 3.4
Topological order and shortest paths in DAGs
Prove topological sorting and linear-time shortest paths with negative edges in acyclic graphs.
- 3.5
Strongly connected components
Prove the finishing-time ordering behind the two-pass component algorithm.
- 3.6
All-pairs shortest paths by dynamic programming
Derive the Floyd–Warshall recurrence and its in-place update under explicit hypotheses.
- 3.7
Prim's minimum spanning tree algorithm
Prove the growing-tree invariant and account for binary-heap operations.
- 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.
- 3.9
Shortest augmenting paths and polynomial flow
Prove the Edmonds–Karp augmentation bound using residual distances.
- 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
- 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.
- 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.
- 4.3
A reduction from 3-SAT to three-coloring
Build and verify an explicit clause gadget for three-colorability.
- 4.4
A reduction from 3-SAT to subset sum
Encode variable choices and clause satisfaction in carry-free decimal columns.
- 4.5
Hamiltonian paths, cycles and traveling-salesperson reductions
Transform Hamiltonian witnesses between graph models and compare metric with arbitrary tour costs.
- 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
- 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
- 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
- 7.1
Bellman–Ford: relaxation, edge budgets and negative cycles
Derive shortest-path relaxation from a bounded-edge recurrence and distinguish reachable negative cycles.
- 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
- 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
- 9.1
Closest pairs and strip packing
Prove the strip bound and return exact squared-distance witnesses.