CSE 105 - Theory of Computation, Fall 2017


Welcome to CSE 105! This course will help you answer fundamental questions about computing: In this course, we will explore what it means to be "computable". We begin with a very simple model of computation, and work our way to the most powerful, the Turing machine, named after Alan Turing, who formalized the notion of "algorithm" in this last model even before there were any physical computers. You'll also learn about the relationship of these models to some essential tools in a computer scientist's toolkit, such as regular expressions and context-free grammars. Finally, you'll develop your technical communication skills in writing formal arguments and proofs.

Instructors

Class times

Textbook

Michael Sipser, Introduction to the Theory of Computation, 3rd ed.
We will use the international edition, which is much more affordable. It is available on Amazon for about $15, or the bookstore for $17.50.
See also the errata for a list of known typos/errors in the book.

Grading

The final grade will be composed as follows: A passing grade in the final exam (at least 50%) is required to pass the class. Letter grades will be assigned as follows: The designation of +/- inside a grade range is based on the instructor discretion. It will depend on the grade distribution as well as your particiaption in class and discussion, coming to office hours, and improvement throughout the class.

Homework

Homework is 20% of the final grade. There will be 7 homeworks, your lowest grade will be dropped. Homework is due on Mondays 11pm, except for weeks with midterms. Submission is online via Gradescope (you should already be enrolled; if not, enroll using your @ucsd.edu email and the code MGEP28).
Instructions:

Participation

Participation is 10% of the total grade. For full participation grade, you need to collect 20 participation points. How to collect participation points:

i-Clicker

Please register your i-Clicker here.

Discussion forums

We use Piazza for discussion forums: any questions that you have on the material, and finding other students for group study and homework.

Podcast

You can access all previous classes through podcast.

Schedule

NOTE: Subject to change throughout the quarter
Date Subject Chapter Slides HW
10/02/2017 Logistics, introduction to automata Sipser 0, 1.1 slides
10/04/2017 Formal definition of Deterministic Finite Automata (DFA) Sipser 1.1 slides
10/09/2017 Regular languages, closure under: complementation, union Sipser 1.1,1.2 slides HW1 due
10/11/2017 Formal definition of Nondeterministic Finite Automata (NFA) Sipser 1.1,1.2 slides
10/16/2017 Equivalence of DFAs and NFAs Sipser 1.2,1.3 slides HW2 due
10/18/2017 Equivalence of DFAs and regular expressions Sipser 1.2,1.3 slides
10/23/2017 Limits of regular languages: the pumping lemma Sipser 1.4 slides HW3 due
10/25/2017 More examples of pumping lemma, intro to Context Free Grammar (CFG) Sipser 1.4, 2.1 slides
10/30/2017 Midterm 1 (in class)
11/01/2017 Context Free Grammar (CFG), Push Down Automata (PDA) Sipser 2.1 slides
11/06/2017 More on Push Down Automata (PDA) Sipser 2.1 slides HW4 due
11/08/2017 Introduction to Turing machines (TM) Sipser 3.1 slides
11/13/2017 Turing machines: more examples and equivalent models Sipser 3.1,3.2 slides HW5 due
11/15/2017 More on models, encodings of inputs and proving decidability Sipser 3.2,4.1 slides
11/20/2017 Proving decidability Sipser 4.1 slides HW6 due
11/22/2017 Proving undecidability by diagonalization Sipser 4.2 slides
11/27/2017 Midterm 2 (in class)
11/29/2017 Reductions and the halting problem Sipser 5.1 slides
12/04/2017 Introduction to complexity Sipser 7.1,7.2,7.3 slides HW7 due
12/06/2017 Summary slides
12/14/2017 Final exam