Foundations of Computer Science (FOCS): Lecture-Slides

The lecture-slides are a companion to the textbook Discrete Mathematics and Computing (DMC), by Magdon-Ismail.
Part Ⅰ: Discrete Mathematics and Probability. (lectures 1-21)
Part Ⅱ: Theory of Computing. (lectures 22-29)
The slides can be used for self study and are also available to instructors who wish to teach a course based on the book.

The slides are available as is with no explicit or implied warranties.
The copyright for all material remains with the original copyright holder (in almost all cases the author of DMC).

Ⅰ. Discrete Mathematics and Probability
 Lecture 1. Introduction and Motivation What is discrete math? 3 Challenge problems. The hundred 27-digit numbers for the distinct subset sum problem. DMC Chapter 1,2 (handout version) Lecture 2. Discrete Objects and Proof Sets, sequences, graphs. Building an intuition for proof. DMC Chapter 1,2 (handout version) Lecture 3. Making Precise Statements Logicical propositions. Negation and quantification. Truth tables. DMC Chapter 3 (handout version) Lecture 4. Proof Methods. Proof patterns: if-then; if-and-only-if; for all; there exists. DMC Chapter 4 (handout version) Lecture 5. Induction Basics of Induction DMC Chapter 5 (handout version) Lecture 6. Strong Induction Harder inductions: stronger claims, leaping induction, strong induction. DMC Chapter 6 (handout version) Lecture 7. Recursion Recursive functions, recurrences, recursive sets, sequences, structures (trees). DMC Chapter 7 (handout version) Lecture 8. Proofs with Recursive Objects Structural induction: induction on recursively defined objects. DMC Chapter 8 (handout version) Lecture 9. Sums and Asymptotics (Order Notation) Tools for computing sums (runtime of algorithms). How to compare runtime function. DMC Chapter 9 (handout version) Lecture 10. Number Theory Primes, division and modular arithmetic and cryptography (RSA). DMC Chapter 10 (handout version) Lecture 11. Graphs Notation and basics. The hand-shaking lemma; Different types of graphs (planar, multigraphs, weighted, directed). Problem solving with graphs. DMC Chapter 11 (handout version) Lecture 12. Matching and Coloring. Addressing real world problems with tools from graph theory. DMC Chapter 12 (handout version) Lecture 13. Counting Basic tools. Build-up and bijection. Permutations and combinations. Binomial Theorem. DMC Chapter 13 (handout version) Lecture 14. Advanced counting Sequences with repetition; inclusion-exclusion; pigeon-hole principle and applications. DMC Chapter 14 (handout version) Lecture 15. Probability Discrete probability theory: computing probabilities; probability spaces. DMC Chapter 15 (handout version) Lecture 16. Conditional Probabiliy New information changes a probability. Law of total probability. DMC Chapter 16 (handout version) Lecture 17. Independent Events Multiplying probabilities: birthday problem; hashing; gambler's ruin. DMC Chapter 17 (handout version) Lecture 18. Random Variables Measurable quantities of an outcome. Bernoulli, Uniform, Binomial, Exponential. DMC Chapter 18 (handout version) Lecture 19. Expected Value Summarzing a random variable with its mean. Law of Total Expectation. DMC Chapter 19 (handout version) Lecture 20. Expected Value of a Sum Expectations of sums and products; iterated expectation; sums of indicators. DMC Chapter 20 (handout version) Lecture 21. Deviations from the Mean Expected value (mean) summarizes a measurement. How good is it: variance? DMC Chapter 21 (handout version)

Ⅱ. Theory of Computing
 Lecture 22. Infinity Cardinality and comparing sets. Countable and uncountable. DMC Chapter 22 (handout version) Lecture 23. Languages: What is Computation? Computing problems are sets of finite strings. What is the complexity of a problem? DMC Chapter 23 (handout version) Lecture 24. Deterministic Finite Automata (DFA) Computing without scratch paper. Solves regular languages. Can't solve equality. DMC Chapter 24 (handout version) Lecture 25. Context Free Grammers Generating the strings in a language (more powerful than DFA). What can it solve (compilers)? What can't it solve? DMC Chapter 25 (handout version) Lecture 26. Turing Machines Church-Turing Thesis. The! model of computation that captures the intuitive notion of an algorithms (unbounded RAM). Infinite loops. Deciders and recognizers. DMC Chapter 26 (handout version) Lecture 27. Unsolvable Problems Problems we cannot solve: Auto-Grade, Ultimate-Debugger, program verification, PCP. DMC Chapter 27 (handout version) Lecture 28. Efficiency Extended Church-Turing Thesis. The fast (P) and the slow (EXP) DMC Chapter 28 Lecture 29. Hard Problems The Fast (P) the Slow (EXP) and the verifiable (NP). Circuits and 3-SAT, a hardest verifiable problem. NP-completeness. DMC Chapter 29