Overview
Coursera Flash Sale
40% Off Coursera Plus for 3 Months!
Grab it
This course covers elementary discrete mathematics for science and engineering, with a focus on mathematical tools and proof techniques useful in computer science. Topics include logical notation, sets, relations, elementary graph theory, state machines and invariants, induction and proofs by contradiction, recurrences, asymptotic notation, elementary analysis of algorithms, elementary number theory and cryptography, permutations and combinations, counting tools, and discrete probability.
Syllabus
- Lecture 1: Predicates, Sets, and Proofs
- Lecture 2: Contradiction and Induction
- Lecture 3: Casework and Strong Induction
- Lecture 4: State Machines
- Lecture 5: Sums
- Lecture 6: Asymptotics
- Lecture 7: Recurrences
- Lecture 8: Divisibility
- Lecture 9: Modular Arithmetic
- Lecture 10: Cryptography
- Lecture 11: Graphs and Coloring
- Lecture 12: Matching
- Lecture 13: Connectivity and Trees
- Lecture 14: Digraphs and DAGs
- Lecture 15: Relations and Counting
- Lecture 16: Counting Techniques
- Lecture 17: More Counting Techniques
- Lecture 18: Probability
- Lecture 19: Conditional Probability
- Lecture 20: Independence
- Lecture 21: Random Variables
- Lecture 22: Expectation
- Lecture 23: Expectation and Variance
- Lecture 24: Large Deviations: Chebyshev and Chernov Bound, Wrap Up
Taught by
Dr. Zachary Abel, Dr. Brynmor Chapman, and Prof. Erik Demaine