Skip to content

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.

11 chapters · 29 sectionsEN · 繁 · 简
My course notes

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.

Open this course in the knowledge map

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.

Open this course in the knowledge map

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

    Inclusion–exclusion and onto functions

    Count overlapping exceptions by tracking each object’s contribution.

  2. 1.2

    Counting configurations up to symmetry

    Prove the fixed-point average and count cyclic binary strings.

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

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

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

  1. 3.1

    Greedy choices, divide and conquer, and dynamic programming

    Compare algorithm design principles using scheduling and merge sort.

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

  1. 4.1

    Kruskal's algorithm and a cut exchange

    Build a minimum spanning tree and prove each greedy edge can belong to an optimum.

  2. 4.2

    Bellman–Ford and reachable negative cycles

    Derive bounded-edge shortest walks and identify distances made unbounded by negative cycles.

  3. 4.3

    Topological order and cycle certificates

    Prove a queue-based ordering algorithm and extract a directed-cycle witness.

  4. 4.4

    Disjoint-set forests and union by size

    Maintain growing components and prove a logarithmic bound by doubling.

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

  1. 5.1

    GCDs, modular inverses, and fast powers

    Prove Euclid, linear congruences and repeated squaring.

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

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

  1. 6.1

    Prefix functions and overlapping string matches

    Derive KMP fallback, prove a linear scan and retain overlapping occurrences.

  2. 6.2

    Edit distance and optimal alignment

    Derive a prefix dynamic program for edit distance, prove it correct and reconstruct an optimal edit sequence.

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

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

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

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

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

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

  1. 12.1

    Propositional equivalence, normal forms and resolution

    Translate finite Boolean formulas into normal forms, eliminate variables by resolution and distinguish equivalence from equisatisfiability.

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

  3. 12.3

    Logic, counting, and algorithmic invariants

    Use quantified statements, induction, bijections and inclusion-exclusion to prove discrete claims and verify a counting algorithm.

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

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

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

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