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

Section ID: 549454

Course Webpage: http://www-cse.ucsd.edu/classes/wi06/cse105/

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.

Instructor: Daniele Micciancio

TAs: Brian McFee and Neil Alldrin

Textbook: Introduction to the Theory of Computation by Mike Sipser, PWS Publishing Co., 1997. (See book website for Errata.)
[A second edition of the book came out recently. The two editions are almost identical, and you can use either edition of the book.]

Announcements: Course announcements will be made through this course web page. You are responsible for checking the webpage regularly for announcements.

• Solutions to Quiz 1 are available. (See Reading assignments below)
• Solutions to Quiz 2 are available.
• Solutions to Quiz 3 are available.

Course Schedule

Staff

(*) Important: all course related emails sent to the intructor should include the string CSE105 in the subject line (anywhere, possibly within a more descriptive message). If you do not include CSE105 in the subject, your email risks to be discarded by the spam filtering program. Also, your email messages should be in plain text format and include valid sender and return addresses. Emails with no return address, blank body and the message text included as an html attachment, ms word files, etc. risk also be automatically deleted by the email spam filter programs and are likely to never reach the instructor.

Homeworks

This course does not have formally graded homework assignments, but each day in class I will give some problems you should try to solve before the following lecture. For your reference, I will list the problems here on the webpage.

• Jan 10: In the first lecture we defined DFAs and the languages associated with them. A language is call "regular" if it is the language of some DFA. Consider the following languages. Are they regular? Can you give a DFA for any of them? (All languages should be considered as binary, i.e., the alphabet is {0,1}.)
  • L1: The sef of all binary strings such that the 10th symbol from the last is a 0.
  • L2: The set of all binary strings that represent a multiple of 5 (written in binary notation)
  • L3: The set of all binary strings that represent a power of 3.
• Jan 12: In class we have studied a general method to convert NFAs into equivalent DFA. We also gave NFAs for the language L1, and the simpler languages L4: "The set of all binary strings such that the 3rd symbol from the last is a 0."
  • Transform the NFA for L4 into an equivalent DFA using the procedure studied in class
  • Can you apply the same transformation to the NFA for L1? How many states would you get? Is there a smaller DFA for the same language? What is the smallest number of states for any DFA accepting L1?
  • So far we have proved that L1 and L2 are regular. What about L3? Can you find a DFA or NFA for L3?
• Jan 17: In class we proved that the class of regular languages is closed under union, complement, intersection, reverse. What about the following operations:
  • Star: L* = { w(1)...w(n) : n>= 0 and w(i) is in L for all i } [Answer: YES. You can find the proof in the book]
  • Concatenation: L.L' = {ww' : w is in L and w' is in L' } [Answer: YES. You can find the proof in the book]
  • Perfect shuffle: L | L' = {a[1]b[1]...a[n]b[n] : a[1..n]...a(n) is in L, b[1...n] is in L' }
  • Even(L) = {a[2]a[4]...a[2.trunc(n/2)] : a[1...n] is in L }
  • Odd(L) = {a[1]a[3]...a[2.trunc((n-1)/2) + 1] : a[1...n] is in L}
• Jan 19: We start getting a good understanding of regular languages. We showed that they can be alternatively described by DFAs, NFAs or regular expressions (REX). The question is: is every language regular? Or some languages do not admit a description by a DFA, NFA or REX? Define a language D over the alphabet {0,1} as follows. (The definition of the language is a bit involved, and it requires a few steps.)
  1. Observe that any regular expression over the alphabet {0,1} can be described by a string over the alphabet {0,1,(,),+,o,*}, where +,o,* are the union, concatenation and star operation.
  2. Define the binary encoding enc(R) of a regular expression R as the binary string obtained by representing each symbol in {0,1,(,),+,o,*} as a triplet of bits, e.g., 0 is represented by 000, 1 by 111, + by 010, and 0+1 by 000010111.
  3. Let D be the language {enc(R) : enc(R) is not in L(R) }

  Is D regular? Or nor? Can you prove your answer? (By either giving a regular expression such that L(R) = D, or by giving a mathematical proof that L(R) is different from D for every regular expression R.)

• Quiz 1 prep. homework. Here is a selection of problems from the textbook to prepare for the first quiz on Jan 26. The quiz covers all of Chapter 1. This selection of problems is a minimal requirement, and all students are encouraged to work on all problems from Chapter 1.
• Quiz 2 prep. homework. Here is a selection of problems from the textbook to prepare for the second quiz on Feb 14. 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. This selection of problems is a minimal requirement, and all students are encouraged to work on all problems from Chapter 2.
• Quiz 3 prep. homework. Here is a selection of problems from the textbook to prepare for the third quiz on March 14. The quiz covers all of Chapters 3,4,5. You should start working on each problem as soon as the relevant material has been covered in class. This selection of problems is a minimal requirement, and all students are encouraged to work on all problems from Chapters 3,4,5.

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 to solve them. That's the best way to test your understanding and problem solving abilities, and prepare for midterm and final exams..

• Jan 10: Chapter 1, Section 1.1: Definition of finite automaton, examples, etc.
• Jan 12: Chapter 1, Section 1.2: Nondeterministic finite automaton, equivalence of DFAs and NFAs
• Jan 17: Chapter 1, Section 1.2, 1.3: Closure properties of regular languages, Regular expressions
• Jan 19: Chapter 1, Section 1.3: Equivalence between RE and DFA
• Jan 24: Chapter 1, Section 1.4: Non-regular languages, pumping lemma for regular languages
• Jan 26: Quiz 1. Covers all of Chapter 1. Solutions to Quiz 1 (pdf, ps)
• Jan 31: Chapter 2, Section 2.2: Push Down Automata.
• Feb 2: Chapter 2, Section 2.1: Context Free Grammars
• Feb 7: Chapter 2, Section 2.2: Equivalence of PDA and CFG
• Feb 9: Chapter 2, Section 2.3: Non-context-free languages
• Feb 14: Quiz 2. Covers all of Chapter 2, except Chomsky Normal Form. Solutions to Quiz 2 (pdf,ps)
• Feb 16: Section 3.1: Definition and examples of Turing Machine
• Feb 21: Sections 3.2, 3.3: Equivalence between different computational models
• Feb 23: Section 4.1: Decidable problems
• Feb 28: Section 4.2: Halting problem and undecidability
• Mar 2-9: Chapter 5: Reductions and undecidable problems
• Mar 14: Quiz 3. Solutions (pdf.ps) (pdf,ps)
• Mar 16: Chapter 7: Introduction to computational complexity

Course requirements and policies

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, unless your absence is due to a demonstrated personal health problem at the time, in which case the weight of the quiz will be shifted to the final. Each quiz accounts for 20% of the final course grade, the final exam gives the remaining 40%. Both the quizzes 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 be available through GradeSource. You will receive an email from gradesource with instructions and a secret number to access your grades.

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! 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+)

Academic honesty: 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.

Regrade requests on any quiz are only accepted within a week after the graded quiz has been returned. Do not modify your solutions after they are returned to you. If you alter the your solutions, you loose any right to request a regrade of that exam. Modifying the exam and then bringing it back to ask for a regrade will be treated as a violation of academic honesty rules, and so prosecuted.