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 |