Foundations of Computer Science (FOCS) Lecture Schedule and Handouts
The linked handouts below were provided as supplementary material for our course text, Discrete Mathematics and Computing (DMC) by Magdon-Ismail. They are included here for self-study, and DO NOT SUBSTITUTE FOR ATTENDING LECTURES AND READING THE ASSIGNED CHAPTERS.
The copyright for the slides remains with the original copyright holder, the author of DMC.
Click a lecture to expand its summary, reading, and links.
I. Discrete Mathematics and Probability
Lecture 1.(DMC Chapter 1, 2) Introduction and Motivation▾
Warmup on discrete objects and motivating examples from epidemic spread, speed dating, friendship networks, and computing.
Lecture 2.(DMC Chapter 1, 2) Discrete Objects and Proof▾
Sets, sequences, graphs. Building an intuition for proof.
Lecture 3.(DMC Chapter 3) Making Precise Statements▾
Logical propositions. Negation and quantification. Truth tables.
Lecture 4.(DMC Chapter 4) Proof Methods▾
Proof patterns: if-then; if-and-only-if; for all; there exists.
Lecture 6.(DMC Chapter 6) Strong Induction▾
Harder inductions: stronger claims, leaping induction, strong induction.
Lecture 7.(DMC Chapter 7) Recursion▾
Recursive functions, recurrences, recursive sets, sequences, structures (trees).
Lecture 8.(DMC Chapter 8) Proofs with Recursive Objects▾
Structural induction: induction on recursively defined objects.
Lecture 9.(DMC Chapter 9) Sums and Asymptotics (Order Notation)▾
Tools for computing sums (runtime of algorithms). How to compare runtime functions.
Lecture 10.(DMC Chapter 10) Number Theory▾
Primes, division and modular arithmetic and cryptography (RSA).
Lecture 11.(DMC Chapter 11) Graphs▾
Notation and basics. The handshaking lemma; different types of graphs (planar, multigraphs, weighted, directed). Problem solving with graphs.
Lecture 12.(DMC Chapter 12) Matching and Coloring▾
Addressing real world problems with tools from graph theory.
Lecture 13.(DMC Chapter 13) Counting▾
Basic tools. Build-up and bijection. Permutations and combinations. Binomial Theorem.
Lecture 14.(DMC Chapter 14) Advanced Counting▾
Sequences with repetition; inclusion-exclusion; pigeon-hole principle and applications.
Lecture 15.(DMC Chapter 15) Probability▾
Discrete probability theory: computing probabilities; probability spaces.
Lecture 16.(DMC Chapter 16) Conditional Probability▾
New information changes a probability. Law of total probability.
Lecture 17.(DMC Chapter 17) Independent Events▾
Multiplying probabilities: birthday problem; hashing; gambler's ruin.
Lecture 18.(DMC Chapter 18) Random Variables▾
Measurable quantities of an outcome. Bernoulli, Uniform, Binomial, Exponential.
Lecture 19.(DMC Chapter 19) Expected Value▾
Summarizing a random variable with its mean. Law of Total Expectation.
Lecture 20.(DMC Chapter 20) Expected Value of a Sum▾
Expectations of sums and products; iterated expectation; sums of indicators.
Lecture 21.(DMC Chapter 21) Deviations from the Mean▾
Expected value (mean) summarizes a measurement. How good is it: variance?
II. Theory of Computing
Lecture 22.(DMC Chapter 22) Infinity▾
Cardinality and comparing sets. Countable and uncountable.
Lecture 23.(DMC Chapter 23) Languages: What is Computation?▾
Computing problems are sets of finite strings. What is the complexity of a problem?
Lecture 24.(DMC Chapter 24) Deterministic Finite Automata (DFA)▾
Computing without scratch paper. Solves regular languages. Can't solve equality.
Lecture 25.(DMC Chapter 25) Context Free Grammars▾
Generating the strings in a language (more powerful than DFA). What can it solve (compilers)? What can't it solve?
Lecture 26.(DMC Chapter 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.
Lecture 27.(DMC Chapter 27) Unsolvable Problems▾
Problems we cannot solve: Auto-Grade, Ultimate-Debugger, program verification, PCP.
Lecture 28.(DMC Chapter 28) Efficiency▾
The Fast (P) the Slow (EXP) and the verifiable (NP). Circuits and 3-SAT, a hardest verifiable problem. NP-completeness.