CSE 105 - Theory of Computation, Fall 2019


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.


Homeworks:

Review quizzes:


Instructors

RoleNameEmailOffice hours
ProfessorShachar Lovettslovett@ucsd.eduWed 10am-noon, CSE 4234
TAKarthika Aravindksreejay@ucsd.eduMon 11:30 am - 1:30 pm, CSE B260A
TAMichael Borkowskimborkows@ucsd.eduSat 2 pm - 4 pm, CSE 4217
TADhiren Laddlad@ucsd.eduThur 2:00pm - 3:00pm, 7:30pm - 8:30pm CSE B240A
TASankeerth Raoskaringu@ucsd.eduTue 8am-10am, CSE 4217
TAManish Singhmksingh@ucsd.eduFri 1 pm - 3 pm, CSE B240A
TARitwik Vatsyayanrvatsyay@ucsd.eduMon 6:30pm-8:30pm, CSE B240A
TALisa Xuezixue@ucsd.eduTue 10am - 11am CSE B215, Wed 1pm - 2pm CSE B240A
TAAhmed Youssefa1yousse@ucsd.eduWed 8am - 9am CSE B250A, Wed 9am - 10am CSE B215A
TutorJoshua Comesjcomes@ucsd.eduWed 7pm-9pm, CSE B250A

Class times

TypeDayTimeLocation
LectureMW5-6:20pmPeterson (PETER) 110
Discussion A01W7-7:50pmCognitive Science Building (CSB) 002
Discussion A02W8-8:50pmCognitive Science Building (CSB) 002
Discussion A03F4-4:50pmCenter Hall (CENTR) 109
Discussion A04F5-5:50pmCenter Hall (CENTR) 109

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 about $19.
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 midnight. Submission is online via Gradescope (you should already be enrolled; if not, enroll using your @ucsd.edu email and the code M3DNJ3).
Instructions:

Participation

Participation is 10% of the total grade. For full participation grade, you need to collect 20 participation points. There are several ways in which you can get particiaption points:

i-Clicker

Please register your i-Clicker here. If you are asked to pay, please use this alternative form.

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/2019 Logistics, introduction to automata Sipser 0, 1.1 slides
10/07/2019 Formal definition of Deterministic Finite Automata (DFA) Sipser 1.1 slides
10/09/2019 Regular languages, closure under: complementation, union Sipser 1.1, 1.2 slides
10/14/2019 Formal definition of Nondeterministic Finite Automata (NFA) Sipser 1.1, 1.2 slides HW1 due
10/16/2019 Equivalence of DFAs and NFAs Sipser 1.2, 1.3 slides
10/21/2019 Equivalence of DFAs and regular expressions Sipser 1.2, 1.3 slides HW2 due
10/23/2019 Limits of regular languages: the pumping lemma Sipser 1.4 slides
10/28/2019 More examples of pumping lemma, intro to Context Free Grammar (CFG) Sipser 1.4, 2.1 slides HW3 due
10/30/2019 Midterm 1 (in class)
11/04/2019 Context Free Grammar (CFG), Push Down Automata (PDA) Sipser 2.1, 2.2 slides
11/06/2019 More on Push Down Automata (PDA) Sipser 2.2 slides
11/11/2019 Veterans day (no class) HW4 due
11/13/2019 Introduction to Turing machines (TM) Sipser 3.1 slides
11/18/2019 Turing machines: more examples and equivalent models Sipser 3.1, 3.2 slides HW5 due
11/20/2019 More on models, encodings of inputs and proving decidability Sipser 3.2, 4.1 slides
11/25/2019 Proving decidability Sipser 4.1 slides HW6 due
11/27/2019 Proving undecidability by diagonalization Sipser 4.2 slides
12/02/2019 Reductions and the halting problem Sipser 5.1 slides HW7 due
12/04/2019 Midterm 2 (in class)
12/12/2019 Final exam