CSCI3190
Introduction to Discrete Mathematics and Algorithms
Logic, sets and relations, counting and discrete probability, number-theoretic and string algorithms, graph algorithms, sorting, algorithm design and NP-completeness.
Your progress
0/ 29 sections marked complete
Next section: Inclusion–exclusion and onto functions
Completion marks are saved in this browser.
This course in the web
In the CSCI3190 notes
- Theorem cards
- 90
- Definitions
- 70
- Counterexamples
- 34
- Concept lenses
- 17
- Histories of ideas
- 1
- Proof X-rays
- 33
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 29 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 90 · Definitions 70 · Counterexamples 34 · Concept lenses 17 · Histories of ideas 1 · Proof X-rays 33
None of these is on the timeline yet.
No concept lens from this course is recorded in the web yet.
Counts cover the 29 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
Counting
Counting
Theorems 14 · Definitions 11Counterexamples 4Lenses 2Proof X-rays 5
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 1.1
Inclusion–exclusion and onto functions
Count overlapping exceptions by tracking each object’s contribution.
- 1.2
Counting configurations up to symmetry
Prove the fixed-point average and count cyclic binary strings.
- 1.3
Counting functions, choosing subsets, and reading recurrence trees
Distinguish ordered assignments from subsets, prove the pigeonhole principle, define asymptotic bounds and derive balanced recurrence costs from level sums.
- 1.4
Set partitions, surjections and Stirling recurrences
Count groups of distinct objects by separating labels from membership, prove Stirling and inclusion–exclusion formulas, and compute exact counts with a justified dynamic program.
- 1.5
Discrete probability, expectation and linearity
Define finite probability spaces, random variables and expectation, prove linearity of expectation and Markov's inequality, and use indicator variables to analyze randomized algorithms.
Chapter 3 · 2 sections
Algorithm design
Algorithm design
Theorems 7 · Definitions 6Counterexamples 2Lenses 1Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 3.1
Greedy choices, divide and conquer, and dynamic programming
Compare algorithm design principles using scheduling and merge sort.
- 3.2
Rounded subproblems and master recurrence bounds
Prove divide-and-conquer work bounds for exact integer ceiling and floor recurrences, account for leaves and geometric regimes, and derive the critical logarithmic-toll thresholds on exact powers.
Chapter 4 · 5 sections
Graph algorithms
Spanning trees, connectivity, shortest walks and ordering.
Theorems 16 · Definitions 10Counterexamples 6Proof X-rays 5
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 4.1
Kruskal's algorithm and a cut exchange
Build a minimum spanning tree and prove each greedy edge can belong to an optimum.
- 4.2
Bellman–Ford and reachable negative cycles
Derive bounded-edge shortest walks and identify distances made unbounded by negative cycles.
- 4.3
Topological order and cycle certificates
Prove a queue-based ordering algorithm and extract a directed-cycle witness.
- 4.4
Disjoint-set forests and union by size
Maintain growing components and prove a logarithmic bound by doubling.
- 4.5
Graph traversal, shortest paths, and spanning trees
Prove BFS and Dijkstra correct through their frontier invariants, derive the minimum-spanning-tree cut property, and separate three different optimization objectives.
Chapter 5 · 3 sections
Integer arithmetic
Integer arithmetic
Theorems 7 · Definitions 2Counterexamples 3Lenses 3History 1Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 5.1
GCDs, modular inverses, and fast powers
Prove Euclid, linear congruences and repeated squaring.
- 5.2
Universal hashing and fixed-key collision bounds
Prove a finite-field hash-family collision bound and apply it to chaining and randomized retries.
- 5.3
Fourier butterflies and polynomial convolution
Derive the discrete Fourier transform, its divide-and-conquer evaluation and the padding needed for ordinary convolution.
Chapter 6 · 3 sections
String algorithms
Prefix fallback and exact matching.
Theorems 10 · Definitions 6Counterexamples 3Lenses 2Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 6.1
Prefix functions and overlapping string matches
Derive KMP fallback, prove a linear scan and retain overlapping occurrences.
- 6.2
Edit distance and optimal alignment
Derive a prefix dynamic program for edit distance, prove it correct and reconstruct an optimal edit sequence.
- 6.3
Rolling polynomial fingerprints for string search
Derive the rolling update and a finite-field collision bound, with explicit verification and input assumptions.
Chapter 8 · 2 sections
Sorting algorithms
Sorting algorithms
Theorems 6 · Definitions 3Counterexamples 2Lenses 2Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 8.1
Inversions, randomized quicksort and stable radix sorting
Analyze insertion sort by inversions, derive randomized quicksort’s expected comparison count, and prove stable counting and radix sorting under explicit key models.
- 8.2
Binary heaps, linear construction and heapsort
Prove sift-down correctness, the linear bottom-up heap bound by summing node heights, and in-place heapsort, while separating heap order, stability and priority-queue allocation costs.
Chapter 9 · 1 section
Number-theoretic algorithms
Number-theoretic algorithms
Theorems 3 · Definitions 2Counterexamples 2Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 9.1
Chinese remainders and compositeness witnesses
Reconstruct modular data with a maintained CRT invariant, prove trial division, and derive a strong compositeness test while separating witnesses from unproved primality claims.
Chapter 10 · 1 section
Polynomial algorithms
Fast Fourier evaluation and coefficient convolution.
Theorems 3 · Definitions 2Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 10.1
FFT and polynomial convolution
Derive radix-2 Fourier evaluation and inversion, then multiply polynomials without cyclic aliasing.
Chapter 11 · 1 section
Euclidean algorithms and congruences
Extend Euclidean certificates to modular equations and compatible noncoprime remainder systems.
Theorems 3 · Definitions 2Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 11.1
Euclidean invariants and congruence certificates
Extend Euclidean certificates to modular equations and compatible noncoprime remainder systems.
Chapter 12 · 5 sections
Logic, sets and relations
Logic, sets and relations
Theorems 18 · Definitions 26Counterexamples 9Lenses 4Proof X-rays 7
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 12.1
Propositional equivalence, normal forms and resolution
Translate finite Boolean formulas into normal forms, eliminate variables by resolution and distinguish equivalence from equisatisfiability.
- 12.2
Predicate logic, witness dependencies and finite-model checking
Read variable scope precisely, justify quantifier proof rules and evaluate finite relational specifications without confusing model checking with validity.
- 12.3
Logic, counting, and algorithmic invariants
Use quantified statements, induction, bijections and inclusion-exclusion to prove discrete claims and verify a counting algorithm.
- 12.4
Sets, images, preimages and composition
Prove set identities element by element, distinguish images from preimages, and construct inverses with the correct finite-set and empty-set conditions.
- 12.5
Relations, equivalence classes and partial orders
Understand equivalence relations as partitions and finite partial orders as dependency structures.
Chapter 13 · 1 section
Complexity and NP-completeness
Complexity and NP-completeness
Theorems 3Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 13.1
Certificates, reductions, and NP completeness
Define efficient verification with polynomial witness bounds, prove reductions between graph problems, and construct the clause-to-clique reduction with both logical directions.