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

Section ID: 493523

This web page (http://www-cse.ucsd.edu/classes/wi04/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

• Quizzes are scheduled on Tuesday January 27th, Thursday February 12th, and Tuesday March 2nd, all during regular class hours.
• There will be no discussion on MLK (January 19) and President day (Feb 16).
• Discussion on January 26 will be a review session for quiz 1
• Jan 20: added some more problems to HW1. We also added pointers to where to find the solutions to most of the problems, as well as a pointer to previous year Quiz 1.
• Solutions to Quiz 1 (ps,pdf) are avaliable. Graded quizzes will be returned in class on Thursday January 29th. To get an idea of your projected grade, see grading scheme at the bottom of this page.
• Discussion on February 9 will be a review session for quiz 2. (Notice: quiz may cover also pumping lemma for non-context free languages to be covered in class on February 10.)
• Solutions to Quiz 2 (ps,pdf) are avaliable. Graded quizzes will be returned in class on Tuesday February 17th.
• Solutions to Quiz 3 (ps,pdf) are available.
• Final exam is on Monday March 15 at 11:30a-2-29p iu Center 214
• Review session scheduled on Friday March 12, at 3:00p-4:00p in AP&M 4301

Homeworks

Here are the problems posed in class and a selection of problems from the textbook. Although your grade will be based exclusively on your performance on the quizzes and final exams, all students are expected to work on the problems listed here. For the problems assigned in class, you are expected to come up with a solution before the next lecture, when the solution to the problem will be usually discussed, or used as a starting point to discuss a new topic.

• Jan 6: Consider the following languages. Are they regular? Can you give a DFA for any of them?
  • The set of all binary strings that end in 101011011
  • The sef of all binary strings such that the 10th symbol from the last is a 0.
  • The set of all binary strings that represent a multiple of 5 (written in binary notation)
  • The set of all binary strings that represent a power of 3.
• Jan 8: In class we proved that the set of regular languages is closed under the reverse operation
  • Are regular languages closed under the complement operation? I.e., if language A is regular, can you conclude that the complement of A is also regular?
  • Can you find some other operation that preserves regularity? I.e., set difference? Intersection? etc.
• Here is a selection of problems from the textbook to prepare for the first quiz on Jan 27. The quiz covers all of Chapter 1. You should start working on each problem as soon as the relevant part of Chapter 1 has been covered in class. Of course, this selection of problems is a minimal requirement, and all students are encouraged to work on all problems from Chapter 1.
• Jan 13: No new problems, but if you didn't work on the previously assigned problems, it is time to do it NOW! In particular, the following problems have a really simple solution using the results proved in today's lecture:
  • Show that regular languages are closed under intersection, i.e., the intersection of regular languages is regular
  • Show that regular languages are closed under set difference
• Jan 15: Give regular expressions for the following languages:
  • The set of all binary strings that do not contain 000 or 111
  • The set of binary strings that represent a multiple of 5
• Jan 20: Prove that the language of all binary strings w in {0,1}* such that w contains the same number of 0s as 1s is not regular. Can you prove the same for the language of all binary strings that represent a power of 3?
• Jan 29: Can you give a push down automaton for any of the following languages:
  • Lsum = {1^a 0 1^b 0 1^c : a + b = c}
  • Lexists = {1^(a_1) 0 1^(a_2) 0 ... 0 1^(a_k): k>=0, and a_i = i for some i}
  • Lforall = {1^(a_1) 0 1^(a_2) 0 ... 0 1^(a_k): k>=0, and a_i = i for all i}
• Feb 3: Prove that the grammar S -> epsilon | S(S) generates the set of all and only well parenthesized expressions

  Give context free grammar for the language Lexists defined above.

• Here is a selection of problems from the textbook to prepare for the second quiz on Feb 12. The quiz covers all of Chapter 2, (excluding Chomsky normal form). You should start working on each problem as soon as the relevant part of Chapter 2 has been covered in class. Of course, this selection of problems is a minimal requirement, and all students are encouraged to work on all problems from Chapter 2.
• Here is a selection of problems from the textbook to prepare for the third quiz on March 2nd. The exam covers chapters 3, 4, 5.1, 5.2. Notice, 5.2 is just a big example, so, even if not covered explicitly in class, you should be able to read it and understand it.
• The final will cover all of Chapters 1,2,3,4,5, with the exception of Chomski Normal Form, which was not covered in class.
• Sample final (ps,pdf) from last year.

Course Schedule

Textbook

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

See book website for Errata.

Staff

(*) If you want your messages to be read, you should send them from your ucsd email account in plain text format. Emails sent from external accounts (e.g., hotmail), with no return address, blank body and the message text included as an html attachment, may be automatically deteled by my email spam filter programs and are likely to never reach my email inbox.

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 expected 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 list is tentative, and will be updated lecture by lecture as the course goes on. The book also contains many excercises and problems at the end of each chapter. You are encouraged to try solve them. That's the best way to test your understanding and problem solving abilities.

• Jan 6: Chapter 1, Section 1.1: Definition of finite automaton, examples, etc.
• Jan 8: Chapter 1, Section 1.2: Nondeterministic finite automaton, equivalence of DFAs and NFAs
• Jan 14: Chapter 1, Section 1.2, 1.3: Closure properties of regular languages, Regular expressions
• Jan 16: Chapter 1, Section 1.3: Equivalence between RE and DFA
• Jan 20: Chapter 1, Section 1.4: Non-regular languages, pumping lemma for regular languages
• Jan 22: Chapter 1, Summary, Applications of DFAs, REs, etc.
• Jan 27: Quiz 1. Covers all of Chapter 1
• Jan 29: Chapter 2, Section 2.2: Push Down Automata (except equivalence with CFG)
• Feb 3: Chapter 2, Section 2.1: Context Free Grammars (except Chomsky normal form)
• Feb 5: Chapter 2, Section 2.2: Equivalence between CFG and PDA
• Feb 10: Chapter 2, Section 2.3: Non context free languages
• Feb 12: Quiz 2. Covers all of Chapter 2
• Feb 17: Chapter 3, Section 3.1: Turing Machines
• Feb 19: Chapter 3, Section 3.2, 3.3: Equivalence between models
• Feb 24: Chapter 4, Section 4.1, 4.2: Decidability and the Halting problem
• Feb 26: Chapter 5, Sections 5.1: Turing reductions
• March 2: Quiz 3. Covers all of chapters 3, 4 and 5.1
• March 4: Chapter 5, Section 5.3: Map reductions
• March 9: Chapter 6: Advanced topics
• March 11: Conclusion

Course requirements and grading

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

• Attending lectures
• Reading the textbook as assigned
• All homework assigned in class. (Homeworks will not be collected and graded, but you are expected to work on them.)
• 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.

Grades will NOT be assigned on a curve. You will receive a grade based on your own performance. If everybody does well, everybody will get an A! (Unfortunately, this has never happened so far.) Final grades will be based roughly on the following scale: 50-54 (D), 54-58 (C-), 58-62 (C), 62-66 (C+), 66-70 (B-), 70-75 (B), 75-80 (B+), 80-85 (A-), 85-90 (A), 90-100 (A+)

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. No form of collaboration is allowed during the quizzes and final exam.