Autumn 2021

University of Washington

CSE 311 introduces theoretical computer science, the theory background necessary for other CSE courses, and how to construct rigorous, formal arguments. Topics include logic, set theory, modular arithmetic, induction, regular expression, and relations.

No data.

No data.

- Teach you the theory background needed for other CSE courses – only topics used in many areas of CSE
- Teach you how to make and communicate rigorous and formal arguments – want to know for certain that systems work
- Introduce you to theoretical CS – may be the only theory course you take

There is no required text for the course. For the first 6-7 weeks of the course, the following textbook can be useful: Rosen, Discrete Mathematics and Its Applications, McGraw-Hill. (Course materials will reference problem numbers from the 6th edition, but more recent versions include the same material.) It should be available through the bookstore and on short-term loan from the Engineering Library.

On occasion, there may be required readings during the course when there is insufficient time to fully cover the material during lecture. If this occurs, the readings will be posted on the web site and students will be notified of the reading via email or the message board.

Lecture slides available at Schedule

No videos available

Homework available at Assignments

Problems and solutions available at Schedule

Boolean AlgebraCanonical FormsCircuitsContext-Free Grammar (CFG)Directed GraphsEnglish ProofsEquivalencesEuclidian AlgorithmFSM MinimizationFinite State Machine (FSM)Greatest Common Divisor (GCD)InductionLimitations of DFAs, NFAs, and REsModular EquationsModular ExponentiationModular arithmeticMore Structural InductionNondeterministic Finite Automata (NFA)Predicate LogicPrimesProofs for Predicate LogicProofs for Propositional LogicPropositional calculus (Propositional logic)Recursively Defined FunctionsRecursively Defined SetsRegular expressionRelating DFAs, NFAs, and REsRelation (mathematics)Set (mathematics)Set theoryStrong InductionStructural InductionTranslation