Foundations of Computer Science (FOCS) Lecture Schedule and Handouts

The lectures and readings have been modified from the original plan to accomodate the shortened semester. In particular, what were originally Lectures 20 (Expected Value of a Sum) and 21 (Deviations from the Mean) have been combined into a single Lecture 20, and what were originally Lectures 22 (Infinity) and 23 (Languages: What is Computation?) have been combined into a single Lecture 21.

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 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 (double sided 8.5x11 crib sheet allowed) 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 and Deviations from the Mean
Expectations of sums and products; iterated expectation; sums of indicators. Expected value (mean) summarizes a measurement. How good is it: variance? 		DMC Chapters 20 and 21 (handout for Chapter 20, handout for Chapter 21) (compact for Chapter 20, compact for Chapter 21)   [see also Rosen: Ch 7.4]

Ⅱ. Theory of Computing

Lecture 21. Infinity and Languages: What is Computation?
Cardinality and comparing sets. Countable and uncountable. Computing problems are sets of finite strings. What is the complexity of a problem? 		DMC Chapters 22 and 23 (handout for Chapter 22, handout for Chapter 23 ) (compact for Chapter 22, compact for Chapter 23 )   [see also Sipser: Ch 1]
Lecture 22. 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 23. 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 24. 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 25. 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 26. Efficiency
The Fast (P) the Slow (EXP) and the verifiable (NP). Extended Church-Turing Thesis. 		DMC Chapter 28 (handout) (compact)   [see also Sipser: Ch 7]
FINAL. Cumulative exam (Two double sided 8.5x11 crib sheets allowed) Lectures        1-26
Assignments 1-10