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)

  • 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)

Week 3 (01/22/2019)

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)

Week 6 (02/12/2019)

  • Review topics for Midterm
  • Turing Machines.

Week 7 (02/19/2019)

Week 8 (02/26/2019)

Week 9 (03/05/2019)

Week 10 (03/12/2019)

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