Today we will see how to model computational problems, such as computing running time, by using recurrences, and we will see how to find closed-form solutions for many recurrences.
Source: Zachary Abel, Mathematics for Computer Science (MIT: OpenCourseWare). Licensed under CC BY-NC-SA 4.0.
Hypha Learn
Free university lectures and educational content, curated and republished from public sources.
MIT 6.1200J: Mathematics for Computer Science
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.
-
Lecture 1: Predicates, Sets, and Proofs1:18:46 Free
-
Lecture 2: Contradiction and Induction1:19:37 Free
-
Lecture 3: Casework and Strong Induction1:24:09 Free
-
Lecture 4: State Machines1:21:15 Free
-
Lecture 5: Sums1:22:20 Free
-
Lecture 6: Asymptotics1:18:25 Free
-
Lecture 7: Recurrences1:13:23 Free
-
Lecture 8: Divisibility1:18:59 Free
-
Lecture 9: Modular Arithmetic1:19:45 Free
-
Lecture 10: Cryptography1:21:08 Free
-
Lecture 11: Graphs and Coloring1:21:15 Free
-
Lecture 12: Matching1:21:43 Free
-
Lecture 13: Connectivity and Trees1:22:02 Free
-
Lecture 14: Digraphs and DAGs1:19:01 Free
-
Lecture 15: Relations and Counting1:18:46 Free
-
Lecture 16: Counting Techniques1:15:13 Free
-
Lecture 17: More Counting Techniques1:20:56 Free
-
Lecture 18: Probability1:07:58 Free
-
Lecture 19: Conditional Probability1:20:44 Free
-
Lecture 20: Independence1:22:02 Free
-
Lecture 21: Random Variables1:10:47 Free
-
Lecture 22: Expectation1:20:30 Free
-
Lecture 23: Expectation and Variance1:18:16 Free
-
