CS 70, Fall 2021

Welcome to CS 70!

Section: Tu/Th 5-6pm in Soda 405
Office Hours: Mon/Wed 5-6pm in Cory 400*

*office hours will be held remotely at oh.eecs70.org on 8/30 and 9/1


Discussion DateTopicsExtra Materials
8/31 (1a)Propositional logic
Inverse, converse, and contrapositive
Proving set equivalence
Functions: Image, Pre-image
Pigeonhole principle
How to succeed in CS 70 (one TA’s opinion)

Problem 3b notes
9/2 (1b)General proof practice
Primes, divisibility, remainders
Induction
Advanced induction strategy: Prove a stronger statement
Very short induction summary
9/7 (2a)Stable matching:
Propose-and-reject algorithm,
Optimal / Pessimal stable matchings
Discussion 2a notes
9/9 (2b)Graphs:
Eulerian tours and walks,
Bipartite graphs / coloring,
Induction on graphs
Discussion 2b notes
9/14 (3a)Graphs:
Planarity (Euclid’s formula, K5 and K33)
Trees, forests, and connected components
Hypercubes
Discussion 3a notes
9/16 (3b)Modular Arithmetic:
Definition, mod rules, tricks for simplifying formulas
Inverses and GCD
Euclid’s GCD algorithm
Discussion 3b notes
9/21 (4a)Extended Euclidean algorithm
Fermat’s Little Theorem (FLT)
Functions and bijections
Review on your own: Chinese remainder theorem (CRT)
Just for fun: How Ancient War Trickery Is Alive in Math Today
(CRT article from Quanta Magazine)

Discussion 4a notes

See you in class!