Foundations of Computer Science (FOCS) Lecture Schedule and Handouts

Professor DiTursi's lecture slides are posted after the lectures, at http://www.cs.rpi.edu/~ditursi/FOCS/slides/.

The linked handouts below 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!

The copyright for the slides remain with the original copyright holder, 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)
Lecture 3. Making Precise Statements
Logicical propositions. Negation and quantification. Truth tables. 		DMC Chapter 3 (handout) (compact)
Lecture 4. Proof Methods.
Proof patterns: if-then; if-and-only-if; for all; there exists. 		DMC Chapter 4 (handout) (compact)
Lecture 5. Induction
Basics of Induction 		DMC Chapter 5 (handout) (compact)
Lecture 6. Strong Induction
Harder inductions: stronger claims, leaping induction, strong induction. 		DMC Chapter 6 (handout) (compact)
Lecture 7. Recursion
Recursive functions, recurrences, recursive sets, sequences, structures (trees). 		DMC Chapter 7 (handout) (compact)
Lecture 8. Proofs with Recursive Objects
Structural induction: induction on recursively defined objects. 		DMC Chapter 8 (handout) (compact)
Lecture 9. Sums and Asymptotics (Order Notation)
Tools for computing sums (runtime of algorithms). How to compare runtime function. 		DMC Chapter 9 (handout) (compact)
Lecture 10. Number Theory
Primes, division and modular arithmetic and cryptography (RSA). 		DMC Chapter 10 (handout) (compact)
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)
Lecture 12. Matching and Coloring.
Addressing real world problems with tools from graph theory. 		DMC Chapter 12 (handout) (compact)
Lecture 13. Counting
Basic tools. Build-up and bijection. Permutations and combinations. Binomial Theorem. 		DMC Chapter 13 (handout) (compact)
Lecture 14. Advanced counting
Sequences with repetition; inclusion-exclusion; pigeon-hole principle and applications. 		DMC Chapter 14 (handout) (compact)
Lecture 15. Probability
Discrete probability theory: computing probabilities; probability spaces. 		DMC Chapter 15 (handout) (compact)
Lecture 16. Conditional Probabiliy
New information changes a probability. Law of total probability. 		DMC Chapter 16 (handout) (compact)
Lecture 17. Independent Events
Multiplying probabilities: birthday problem; hashing; gambler's ruin. 		DMC Chapter 17 (handout) (compact)
Lecture 18. Random Variables
Measurable quantities of an outcome. Bernoulli, Uniform, Binomial, Exponential. 		DMC Chapter 18 (handout) (compact)
Lecture 19. Expected Value
Summarizing a random variable with its mean. Law of Total Expectation. 		DMC Chapter 19 (handout) (compact)
Lecture 20. Expected Value of a Sum
Expectations of sums and products; iterated expectation; sums of indicators. 		DMC Chapter 20 (handout) (compact)
Lecture 21. Deviations from the Mean
Expected value (mean) summarizes a measurement. How good is it: variance? 		DMC Chapter 21 (handout) (compact)

Ⅱ. Theory of Computing

Lecture 22. Infinity
Cardinality and comparing sets. Countable and uncountable. 		DMC Chapter 22 (handout) (compact)
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)
Lecture 24. Deterministic Finite Automata (DFA)
Computing without scratch paper. Solves regular languages. Can't solve equality. 		DMC Chapter 24 (handout) (compact)
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)
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)
Lecture 27. Unsolvable Problems
Problems we cannot solve: Auto-Grade, Ultimate-Debugger, program verification, PCP. 		DMC Chapter 27 (handout) (compact)
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)