logic,
relations,
functions,
basic set theory,
countability and counting arguments,
proof techniques,
mathematical induction,
graph theory,
combinatorics,
discrete probability,
recursion,
recurrence relations,
and number theory.
Emphasis is placed on providing a context for the application of the mathematics within computer science.
Lecture 01 What kinds of problems are solved in discrete math?
Lecture 02 Boolean Algebra and formal logic
Lecture 03 More logic: quantifiers and predicates
Lecture 04 Sets
Lecture 05 Diagonalization, functions and sums review
Lecture 06 Basic arithmetic and geometric sums, closed forms.
Lecture 07 Chinese rings puzzle
Lecture 08 Solving recurrence equations
Lecture 09 Solving recurrence equations (cont.)
Lecture 10 Mathematical induction
Lecture 11 Combinations and permutations
Lecture 12 Counting Problems
Lecture 13 Counting problems
Lecture 14 Counting problems using combinations, distributions
Lecture 15 Counting problems using combinations, distributions
Lecture 16 The pigeonhole principle and examples. The inclusion/exclusion theorem and advanced examples. A combinatorial card trick.
Lecture 17 Equivalence Relations and Partial Orders
Lecture 18 Euclid’s Algorithm
Lecture 19 Recitation — a combinatorial card trick
