Lecture Notes on Discrete Math in Computer Science
A first course on Discrete Math in Computer Science taught at Dartmouth.
- Jargon I: Sets
- Jargon II: Functions
- Jargon III: Propositional Logic
- Jargon IV: Predicate Logic
- Proofs: via Contradiction
- Proofs: Principle of Mathematical Induction
- Proofs: Strong Induction
- Proving Correctness of Programs
- Minimal Counterexamples: A Different Look at Induction
- Combinatorics: Product and Sum Principle
- Combinatorics: Using functions to count, Division Principle
- Combinatorics: The Four Fold Formula
- Combinatorics: Binomial Coefficients & Combinatorial Identities
- Probability: Basics
- Probability: Conditional Probability, Independence
- Probability: Bayes Rule
- Probability: Conditional Independence
- Probability: Random Variables and their Expectations
- Probability: Linearity of Expectation
- Probability: Variance
- Probability: Deviation Inequalities
- Graphs: Basics
- Graphs: Connectivity and Trees
- Graphs: Bipartite Graphs
- Graphs: Matchings and Hall's Theorem
- Graphs: Proof of Hall's Theorem
- Numbers: Modular Arithmetic
- Numbers: GCD and Bezout's Identity
- Numbers: Multiplicative Inverses
- Numbers: Fermat's Little Theorem
- Numbers: Public Key Crypto & RSA Algorithm
- Infinity: Countability
- Infinity: Uncountability, Undecidability, and the Halting Problem