Discrete Mathematics

General Information

Term: Fall 2021.

Lectures: MWF, 10: 20 - 11: 10 am (MST). Office Hours: TBD.

Topics:

Propositional logic: motivation, syntax, and semantics. Modeling with propositional logic. The algebra of logic. Satisfiability solvers: Z3 via Python. Predicate logic: motivation, syntax, and semantics. Modeling with predicate logic. Satisfiability modulo theories: Z3. Quantifiers. Proof systems and inference rules.
Sets and Functions: Naive set theory: basic notions, definitions, and properties. Russell's Paradox. Set algebra. Functions: basic notions. Injective, surjective, and bijective functions. Infinite sets: cardinality and bijection. Countable and uncountable sets. Diagonalization, the Halting Problem, and reductions.
From Computability to Complexity: Growth of functions: asymptotics and practical considerations. Complexity of algorithms and decision problems. Complexity classes, tractability. Reducibility among problems, completeness.
Induction: Weak and strong induction on the natural numbers. Induction and axiomatic theories of arithmetic. Well-orders. Inductive definitions. Recursive algorithms. Program correctness: introduction to Hoare Logic. Inductive invariants.
Models of Computation: Formal languages and grammars. Regular expressions. Finite-State Automata. Limitations of finite-state models of computation. Beyond finite state: machines with stacks and tapes. The Church-Turing thesis.
Intro to Number Theory and Cryptography: Divisibility and modular arithmetic. Prime numbers and the Euclidean algorithm. Linear congruences and Fermat's little theorem. Private and public-key cryptography.The RSA cryptosystem.
Intro to Combinatorics: Basic counting principles. The pigeonhole principle. Permutations and combinations. The binomial coefficients. Generalized permutations. Distribution problems.