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.

Slides (handout) (compact)

Lecture 2.(DMC Chapter 1, 2) Discrete Objects and Proof▾

Sets, sequences, graphs. Building an intuition for proof.

Slides (handout) (compact)

Lecture 3.(DMC Chapter 3) Making Precise Statements▾

Logical propositions. Negation and quantification. Truth tables.

Slides (handout) (compact)

Lecture 4.(DMC Chapter 4) Proof Methods▾

Proof patterns: if-then; if-and-only-if; for all; there exists.

Slides (handout) (compact)

Lecture 5.(DMC Chapter 5) Induction▾

Basics of Induction.

Slides (handout) (compact)

Lecture 6.(DMC Chapter 6) Strong Induction▾

Harder inductions: stronger claims, leaping induction, strong induction.

Slides (handout) (compact)

Lecture 7.(DMC Chapter 7) Recursion▾

Recursive functions, recurrences, recursive sets, sequences, structures (trees).

Slides (handout) (compact)

Lecture 8.(DMC Chapter 8) Proofs with Recursive Objects▾

Structural induction: induction on recursively defined objects.

Slides (handout) (compact)

Lecture 9.(DMC Chapter 9) Sums and Asymptotics (Order Notation)▾

Tools for computing sums (runtime of algorithms). How to compare runtime functions.

Slides (handout) (compact)

Lecture 10.(DMC Chapter 10) Number Theory▾

Primes, division and modular arithmetic and cryptography (RSA).

Slides (handout) (compact)

Lecture 11.(DMC Chapter 11) Graphs▾

Notation and basics. The handshaking lemma; different types of graphs (planar, multigraphs, weighted, directed). Problem solving with graphs.

Slides (handout) (compact)

Lecture 12.(DMC Chapter 12) Matching and Coloring▾

Addressing real world problems with tools from graph theory.

Slides (handout) (compact)

Lecture 13.(DMC Chapter 13) Counting▾

Basic tools. Build-up and bijection. Permutations and combinations. Binomial Theorem.

Slides (handout) (compact)

Lecture 14.(DMC Chapter 14) Advanced Counting▾

Sequences with repetition; inclusion-exclusion; pigeon-hole principle and applications.

Slides (handout) (compact)

Lecture 15.(DMC Chapter 15) Probability▾

Discrete probability theory: computing probabilities; probability spaces.

Slides (handout) (compact)

Lecture 16.(DMC Chapter 16) Conditional Probability▾

New information changes a probability. Law of total probability.

Slides (handout) (compact)

Lecture 17.(DMC Chapter 17) Independent Events▾

Multiplying probabilities: birthday problem; hashing; gambler's ruin.

Slides (handout) (compact)

Lecture 18.(DMC Chapter 18) Random Variables▾

Measurable quantities of an outcome. Bernoulli, Uniform, Binomial, Exponential.

Slides (handout) (compact)

Lecture 19.(DMC Chapter 19) Expected Value▾

Summarizing a random variable with its mean. Law of Total Expectation.

Slides (handout) (compact)

Lecture 20.(DMC Chapter 20) Expected Value of a Sum▾

Expectations of sums and products; iterated expectation; sums of indicators.

Slides (handout) (compact)

Lecture 21.(DMC Chapter 21) Deviations from the Mean▾

Expected value (mean) summarizes a measurement. How good is it: variance?

Slides (handout) (compact)

II. Theory of Computing

Lecture 22.(DMC Chapter 22) Infinity▾

Cardinality and comparing sets. Countable and uncountable.

Slides (handout) (compact)

Lecture 23.(DMC Chapter 23) Languages: What is Computation?▾

Computing problems are sets of finite strings. What is the complexity of a problem?

Slides (handout) (compact)

Lecture 24.(DMC Chapter 24) Deterministic Finite Automata (DFA)▾

Computing without scratch paper. Solves regular languages. Can't solve equality.

Slides (handout) (compact)

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?

Slides (handout) (compact)

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.

Slides (handout) (compact)

Lecture 27.(DMC Chapter 27) Unsolvable Problems▾

Problems we cannot solve: Auto-Grade, Ultimate-Debugger, program verification, PCP.

Slides (handout) (compact)

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.

Slides (handout) (compact)