CSE 105: Introduction to the Theory of Computation, Winter 2003

Section ID: 456200

This web page (http://www-cse.ucsd.edu/classes/wi03/cse105/) will be used to make important announcements related to the course. All class members are responsible for reading information on the web page, and checking it frequently for updates.

Course Description

This course introduces the basic, formal ideas underlying the notion of computation. Syllabus: finite automata, regular expressions, context-free grammars, pushdown automata, turing machines, decidability, undecidability, the halting problem, introduction to complexity theory.

Announcements

• In preparation to the final, we will hold some additional office hours as follows:

  Jia: Friday March 14, 11am. (Notice: Alejandro will not be able to hold office hour on Friday at 2pm as previously annouced in class)

  Alejandro: Monday March 17, 10am, (Confirmed)

  Daniele: Monday March 17, 12noon.

• Reminder: Final exam in Monday March 17 in Center 212 at 7pm.
• Solutions to Quiz 3 are ready
• In preparation to the last quiz, Jia will hold office hour on Monday March 10, 1-2pm, instead of Wed Mar 12. (Mar. 12 office hour is cancelled)
• Solutions to HW3 are ready
• Mar. 11, 5:00pm: Quiz 3
• Solutions to Quiz 2 are ready
• Revised solutions to HW2 are available below
• Notes about Feb. 15 discussion are available at http://www.cse.ucsd.edu/~jiamao/105
• Solutions to HW2 are being posted (see below).
• In preparation to the second quiz, Jia will hold office hour on Friday Feb 14, 1-2pm, instead of Wed Feb 19. (Feb. 19 office hour is cancelled)
• Alejandro will regularly hold office hour on Monday Feb 17.
• CAPE review is scheduled on Feb. 27th at 5pm. Come to class on time to provide feedback about the course.
• Look at Homework 2 below to start preparing for the second quiz, scheduled on Feb. 18th.
• You should be able to access your grades and class statistics from WebCT
• Solutions to Quiz 1 are available
• Error found in the solution to HW1, problem 1.4 L. Thanks to Janelle and Ramu for pointing this out. See below for correction.
• Jia's office hour for the week of Jan 27, is rescheduled from Wednesday to Monday Jan 27 at 3:30-4:30.

• Daniele will hold extra office hour on Monday Jan 27, at 12:30-1:30 in AP&M 5218, (in addition to the regular office hour on Tuesday Jan 28, 2-3pm in AP&M 4218 )

• Solutions to HW1 are ready. (See below)
• Reminder: Quiz 1 is scheduled on Jan 28th (regular class hours). It covers all of Chapter 1.
• Notes (ps, pdf) from Jan 10 discussion are available.
• Homework 1 is ready. This homework is indended as preparation to Quiz 1, but you should start working on it now!
• Quizzes are scheduled on Tuesday January 28th, February 18th and March 11th, all during regular class hours.

Course Schedule

Textbook

Introduction to the Theory of Computation by Mike Sipser, PWS Publishing Co., 1997.

See book website for Errata.

Staff

Homeworks

You can access your grades and course statistics through WebCT.

• Homework 1
• HW1 Solutions (ps,pdf). NOTICE: Solution to 1.4L contains a mistake. The correct solution is (ps,pdf)
• In addition to HW1, as preparation to the quiz, you can look at last quarter quiz 1 and solutions (ps, pdf). [Notice, some of the notation from last quarter textbook is slightly different, but the covered material is substantially the same]
• Quiz 1 solutions (ps,pdf)
• Homework 2
• HW2 solutions (ps,pdf). The first version of the solutions posted contained various errors (ps,pdf). Revised solutions for some of the problems is available here. (ps,pdf)
• As additional material to prepare for the second quiz, you can work on quiz 2 from Fall 2002 (ps,pdf).
• Quiz 2 solutions (ps,pdf)
• Homework 3
• As additional material to prepare for the second quiz, you can work on quiz 3 from Fall 2002 (pdf).
• HW3 solutions (ps,pdf)
• There will be no additional homework assignments to prepare for the final, but you are encouraged to work on any problems from chapters 1,2,3,4,5. Additionally, you may want to try the final exam from last quarter (pdf). Topics not covered in the course (e.g., Chomsky normal form), won't be in the final.
• Quiz 3 solutions (ps,pdf)

Reading assignments

Chapter 0: The material covered in this chapter is prerequisite to this course. This material will not be explicitly covered in class, but you are supposed to read the chapter to make sure you have the necessary background.

Below are some pointers to where in the textbook you can find the material covered in each lecture. The book also contains many excercises and problems at the end of each chapter. You are encouraged to try solve them (in addition to the regularly assigned homeworks of course). That's the best way to test your understanding and problem solving abilities.

• Jan 7: Chapter 1, Section 1.1 (except last paragraph): Definition of finite automaton, examples, etc.
• Jan 9: Chapter 1, Section 1.2 (except last paragraph): Nondeterministic finite automaton, equivalence of DFAs and NFAs
• Jan 14: Chapter 1, Finish sections 1.1, 1.2: Regular operations, closure properties of regular languages
• Jan 16: Chapter 1, Section 1.3: Regular expressions, equivalence between RE and DFA
• Jan 21: Chapter 1, Section 1.4: Non-regular languages, pumping lemma for regular languages
• Jan 23: More about regular languages, applications, etc.
• Jan 28: Quiz 1. Covers all of Chapter 1.
• Jan 30: Chapter 1, Section 1.4: Proof of the pumping lemma for regular languages
• Feb 4: Chapter 2, Section 2.2 (except equivalence with CFG): Context free languages and Push Down Automata
• Feb 6: Chapter 2, Section 2.1 (except Chomsky Normal Form): Context Free Grammars, parse trees, ambiguity.
• Feb 11: Chapter 2, Section 2.2 (all): Equivalence of CFL and PDA
• Feb 13: Chapter 2, Section 2.3: Pumping lemma for context free languages
• Feb 18: Quiz 2. Covers all of Chapter 2, except Chomsky normal form. There will be no problems specific to Chapter 1, but some of the problems about the material from Chapter 2 might require knowledge of regular languages as well.
• Feb 20: Chapter 2, Proof of the pumping lemma for context free languages. This completes Chapter 2.
• Feb 25: Chapter 3, Section 3.1: Definition of Turing Machine
• Feb 27: Chapter 3, Sections 3.2 and 3.3: Equivalence between different computational models
• Mar 4: Chapter 4: The halting problem and undecidability
• Mar 6: Chapter 5: Reducibility
• Mar 11: Quiz 3, Covers Chapters 3, 4 and 5.
• Mar 13: Selected topics from Chapter 6 and 7.

The final exam will cover all of Chapters 1,2,3,4,5, excluding the following topics: Chomsky normal form.

Course requirements and grading

Class members are expected to do all of the following in order to satisfactorily pass this class:

• Attending lectures
• Reading from the textbook
• All homework assignements. Homeworks will not be graded, but you are expected to individually solve all the problems, and checking if your solutions are correct
• 3 in class quizzes
• 1 final exam

Quizzes are scheduled during regular lecture hours, and everybody is expected to attend. There will be no make up quizzes. Not showing up to a quiz will count as 0 grade. Each quiz will account for 20% of the final grade, the final exam gives the remaining 40%. Both the quizes and the final exam will be closed books, closed notes. You can take 1 double sided sheet of notes to the exam, but the notes must be your own.

All students are expected to be familiar with and abide by the rules of UCSD Policy on Integrity of Scholarship as described in the UCSD General Catalog. In case of cheating, such policy will be enforced. This means an F grade in the course, and action by the Dean of your college (probation or suspension from UCSD). You are allowed (and encouraged) to collaborate with other students in doing the homeworks, as they will not receive a formal grade. No form of collaboration is allowed during the quizzes and final exam.