# ECS 120: Theory of Computation

Undergraduate Course, *UC Davis*, 2019

## Logistics

*TA:***Aakash Prabhu***Office Hours:***Monday: 10 AM - 12 PM***Location:***53 Kemper**

*Discussion Section:***A01, Tuesday 6:10 - 7:00 PM***217 Art Building*

## Week 1 (01/08/2019)

- Review of Discrete Math and other things you should have already seen in
`ECS 20`

. - Discussion Notes
- Discussion Problems

### Useful Links

- Read this excellent
*Medium*article on the introduction to graph theory! - Here is a partially complete study guide that I wrote for
`ECS20`

. It contains proof techniques that will be useful in this class!

## Week 2 (01/15/2019)

- Deterministic Finite Automata (DFAs), Regular Expressions (Regex), and Context Free Grammars/Languages (CFGs)
- Go over a few problems from the written portion of HW 1.
- Discussion Notes
- Discussion Problems

## Week 3 (01/22/2019)

- Non-Deterministic Finite Automata (NFAs), Closure Properties of DFAs, and the Product Construction.
- Discussion Notes
- Discussion Problems

## Week 4 (01/29/2019)

- Closure Properties of NFAs. Union, Concatenation, and Star Constructions of NFAs. Constructing DFAs from RRGs and vice-versa.
- No Notes and Problems for this weekâ€¦sorry :(

## Week 5 (02/05/2019)

- Equivalence of Regexs and NFAs. The Pumping Lemma.
- Discussion Problems

## Week 6 (02/12/2019)

- Review topics for Midterm
- Turing Machines.

## Week 7 (02/19/2019)

- Variants of Turing Machines, Church-Turing Thesis (Review)
- Asymptotic Analysis, The Complexity Class
**P**. - Discussion Problems

## Week 8 (02/26/2019)

- Proving problems belong to
**P**,**NP**, The**P = NP**question - The class
**EXP** - Discussion Problems

## Week 9 (03/05/2019)

- NP-Complete problems
- Reducibility among NP-Complete problems.
- Discussion Problems

## Week 10 (03/12/2019)

- Undecidability of the Halting Problem
- Reducibility among undecidable problems
- Good bye and thanks for a great quarter!