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

Section ID: 580100

Course Webpage: http://www-cse.ucsd.edu/classes/wi07/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, Turing reducibility, introduction to complexity theory.

Instructor: Daniele Micciancio
TA: Steve Checkoway

Textbook: Mike Sipser's Introduction to the Theory of Computation (2nd edition).

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

• No class on January 15 (MLK day)
• Solutions to quiz 1 are available here (ps,pdf).
• No class on February 19 (President day)
• Quiz 2 on February 21 will cover Ch. 2 (context free languages).
• Office hour on February 23 is cancelled.
• Solutions to quiz 2 are available here (ps,pdf).
• CAPE instructor/course evaluation and TA evaluation will take place on Wed. March 7 at the beginning of class.
• Solutions to quiz 3 are available here (ps,pdf).
• Final Exam on Wednesday March 21, 11:30am-2:00pm. (Usual room CENTR 216)
  

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 most days in class I will give some problems for you to work on. You should try to solve the problems before the following lecture. For your reference, I will list the problems here on the webpage.

• Jan 8: Consider the Deterministic Finite Automaton described in the following diagram. Can you give an English description of the set of binary strings accepted by the automaton?

  

• Jan 10: Consider the following languages (all over the binary alphabet {0,1}):
  • L1={w: w is (the binary representation of) a multiple of 2}
  • L2={w: w is a multiple of 3}
  • L3={w: w is a multiple of 5}
  • L4={w: w is a power of 2}
  • L5={w: w is a power of 3}
  • L6={w: the 10th from last symbol in w is a 0}
  • L7={w: the 2nd symbol in w is a 1}
  In class, we gave DFAs for L1, L4 and L7. Can you give DFAs for any other language in the list?
• Jan 17: In class we showed that the class of regular languages is closed under the reverse operation. Answer the following questions:
  • Is the class of non-regular languages also closed under reverse?
  • Is the class of regular languages closed under complement?
  • Is it closed under intersection?
  • Is the class of non-regular languages closed under intersection?
• Jan 19: Show that for any DFA M=(Q,Sigma,delta,s,F), changing the set of accepting states F into its complement F'=Q-F, results in a DFA M' for the complement of the original language: L(M') = Sigma* - L(M). Show also that the same transformation applied to a NFA is not always correct, i.e., find a NFA N=(Q,Sigma,delta,s,F) such that the language of N'=(Q,Sigma,delta,s,Q-F) is not the complement of L(N).
• 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 you 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 21. The quiz covers all of Chapter 2, except Chomsky Normal Form. Chapter 3 (Turing machines) will not be covered in Quiz 2. This selection of problems is a minimal requirement, and you are encouraged to work on all problems from Chapter 2.
• Consider the following grammar simplification problem: given a grammar G and a rule X->alpha in it, determine if X->alpha can be removed from the grammar without affecting the generated language. Is this problem decidable?
• We have seen that the emptyness problem for context free grammars E_CFG is decidable. Show that the acceptance problem A_CFG is also decidable.
• Find two context free languages $A$ and $B$ such that their intersection is not context free, and prove your answer correct.
• Quiz 3 prep. homework. Here is a selection of problems from the textbook to prepare for the second quiz on March 12. The quiz covers all of Chapter 3,4 & 5.1.

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 8-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 22-24: Chapter 1, Section 1.4: Non-regular languages, pumping lemma for regular languages
• Jan 26: Quiz 1. Covers all of Chapter 1.
• Jan 29: Chapter 2, Section 2.2: Push Down Automata.
• Jan 31-Feb 2: Chapter 2, Section 2.1: Context Free Grammars
• Feb 5-7: Chapter 2, Section 2.2: Equivalence of PDA and CFG
• Feb 9-12: Chapter 2, Section 2.3: Non-context-free languages
• Feb 14: Section 3.1: Definition and examples of Turing Machine
• Feb 16: Sections 3.2, 3.3: Equivalence between different computational models
• Feb 21: Quiz 2. Covers all of Chapter 2, except Chomsky Normal Form.
• Feb 23: Section 4.1: Decidable problems
• Feb 26-28: Section 4.2: Halting problem and undecidability
• Mar 2-9: Chapter 5: Reductions and undecidable problems
• Mar 12: Quiz 3. Covers Chapters 3, 4 and 5.
• Mar 14-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 each quiz and final exam, but the notes must be your own.

Grades will be available through GradeSource. If you are enrolled in the class you should have received 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.