Foundations of Computer Science (FOCS) Lecture Schedule and Handouts
The linked handouts were provided as supplementary material for our course text, Discrete Mathematics and Computation (DMC) by Magdon-Ismail. They are included here for self-study, and DO NOT SUBSTITUTE FOR ATTENDING LECTURES AND READING! Optional references are included to another popular text, Discrete Mathematics and Its Applications, by Rosen.
The copyright for the slides remain with the original copyright holders (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) (compact) |
Lecture 2. |
Discrete Objects and Proof
Sets, sequences, graphs. Building an intuition for proof. | DMC Chapter 1,2 (handout) (compact) [see also Rosen: Ch 2.1-2.4] |
Lecture 3. |
Making Precise Statements
Logicical propositions. Negation and quantification. Truth tables. | DMC Chapter 3 (handout) (compact) [see also Rosen: Ch 1.1-1.6] |
Lecture 4. |
Proof Methods.
Proof patterns: if-then; if-and-only-if; for all; there exists. | DMC Chapter 4 (handout) (compact) [see also Rosen: Ch 1.7-1.8] |
Lecture 5. |
Induction
Basics of Induction | DMC Chapter 5 (handout) (compact) [see also Rosen: Ch 5.1] |
Lecture 6. |
Strong Induction
Harder inductions: stronger claims, leaping induction, strong induction. | DMC Chapter 6 (handout) (compact) [see also Rosen: Ch 5.2] |
Lecture 7. |
Recursion
Recursive functions, recurrences, recursive sets, sequences, structures (trees). | DMC Chapter 7 (handout) (compact) [see also Rosen: Ch 5.3-5.5] |
Lecture 8. |
Proofs with Recursive Objects
Structural induction: induction on recursively defined objects. | DMC Chapter 8 (handout) (compact) [see also Rosen: Ch 5.3-5.5] |
Lecture 9. |
Sums and Asymptotics (Order Notation)
Tools for computing sums (runtime of algorithms). How to compare runtime function. | DMC Chapter 9 (handout) (compact) [see also Rosen: Ch 2.4, 3] |
Lecture 10. |
Number Theory
Primes, division and modular arithmetic and cryptography (RSA). | DMC Chapter 10 (handout) (compact) [see also Rosen: Ch 4] |
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) (compact) [see also Rosen: Ch 10,11] |
MIDTERM. | Cumulative exam |
Lectures 1-11
Assignments 1-5 |
Lecture 12. |
Matching and Coloring.
Addressing real world problems with tools from graph theory. | DMC Chapter 12 (handout) (compact) [see also Rosen: Ch 10,11] |
Lecture 13. |
Counting
Basic tools. Build-up and bijection. Permutations and combinations. Binomial Theorem. | DMC Chapter 13 (handout) (compact) [see also Rosen: Ch 6.1-6.4] |
Lecture 14. |
Advanced counting
Sequences with repetition; inclusion-exclusion; pigeon-hole principle and applications. | DMC Chapter 14 (handout) (compact) [see also Rosen: Ch 6.5-6.6, 8.5] |
Lecture 15. |
Probability
Discrete probability theory: computing probabilities; probability spaces. | DMC Chapter 15 (handout) (compact) [see also Rosen: Ch 7.1-7.2] |
Lecture 16. |
Conditional Probabiliy
New information changes a probability. Law of total probability. | DMC Chapter 16 (handout) (compact) [see also Rosen: Ch 7.1-7.3] |
Lecture 17. |
Independent Events
Multiplying probabilities: birthday problem; hashing; gambler's ruin. | DMC Chapter 17 (handout) (compact) [see also Rosen: Ch 7.1-7.3] |
Lecture 18. |
Random Variables
Measurable quantities of an outcome. Bernoulli, Uniform, Binomial, Exponential. | DMC Chapter 18 (handout) (compact) [see also Rosen: Ch 7.1-7.3] |
Lecture 19. |
Expected Value
Summarzing a random variable with its mean. Law of Total Expectation. | DMC Chapter 19 (handout) (compact) [see also Rosen: Ch 7.4] |
Lecture 20. |
Expected Value of a Sum
Expectations of sums and products; iterated expectation; sums of indicators. | DMC Chapter 20 (handout) (compact) [see also Rosen: Ch 7.4] |
Lecture 21. |
Deviations from the Mean
Expected value (mean) summarizes a measurement. How good is it: variance? | DMC Chapter 21 (handout) (compact) [see also Rosen: Ch 7.4] |
Ⅱ. Theory of Computing
Lecture 22. |
Infinity
Cardinality and comparing sets. Countable and uncountable. | DMC Chapter 22 (handout) (compact) [see also Sipser: Ch 1] |
Lecture 23. |
Languages: What is Computation?
Computing problems are sets of finite strings. What is the complexity of a problem? | DMC Chapter 23 (handout) (compact) [see also Sipser: Ch 1] |
Lecture 24. |
Deterministic Finite Automata (DFA)
Computing without scratch paper. Solves regular languages. Can't solve equality. | DMC Chapter 24 (handout) (compact) [see also Sipser: Ch 1] |
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) (compact) [see also Sipser: Ch 2] |
Lecture 26. |
Turing Machines
Church-Turing Thesis. The! model of computation that captures the intuitive notion of an algorithm (unbounded RAM). Infinite loops. Deciders and recognizers. | DMC Chapter 26 (handout) (compact) [see also Sipser: Ch 3] |
Lecture 27. |
Unsolvable Problems
Problems we cannot solve: Auto-Grade, Ultimate-Debugger, program verification, PCP. | DMC Chapter 27 (handout) (compact) [see also Sipser: Ch 4,5] |
Lecture 28. |
Efficiency
The Fast (P) the Slow (EXP) and the verifiable (NP). Circuits and 3-SAT, a hardest verifiable problem. NP-completeness. | DMC Chapter 28 (handout) (compact) [see also Sipser: Ch 7] |
FINAL. | Cumulative exam |
Lectures 1-28
Assignments 1-13 |