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

Course Webpage: http://www-cse.ucsd.edu/classes/wi08/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: Hopcroft, Motwani, Ullman, Introduction to Automata Theory, Languages and Computation (3rd edition).

Announcements: Course announcements will be made through this course web page. (Announcements are in reverse chronological order, most recent announcement on top.) You are responsible for checking the webpage regularly for announcements.

• In the last lecture, I announced that the final exam will be open books. You can bring the textbook to the exam, and there is no limit on the amount of notes you can bring, but they must be your own, and all collected together, e.g., in a binder, notebook, etc.
• Here are the solutions to HW3 in pdf format. The jflap file for problem 2 is also available.
• Homework 3 is available. Solutions should be e-mailed to the TA by Tuesday, March 11 before class. Problem 1 in the HW3 has been slightly revised on Friday March 7: at the end of the computation, the tape head of the TM should be positioned at the beginning of the output string (rather than the end as requested in the initial version of the homework), to adhere to jflap conventions, and make your code easier to debug.
• Here are the solutions to HW2 in pdf format. The jflap files for problem 1, problem 2 and problem 3 are also available.
• There will be a midterm review session on Wed. Feb. 13, 4-5pm in PETER 104. This will be mostly a Q&A session, so be prepared to ask questions.
• Here are the solutions to HW1 in pdf format. The jflap files for problem 1, problem 2 and problem 3 are also available.
• If you want to generate the pdf file of solutions to HW1 on your own computer, here is the LaTeX source file and png of figure 1 and figure 2. These files produce exactly the same solutions as posted above, you don't need to look at these files. We are providing these files just in case you are curious about what program is being used to write homework assignments and solutions.
• Homework 2 is available. Solutions should be e-mailed to the TA by Thursday, February 14 before class. Note: there was a typo (now fixed) in one of the examples in the homework posted on Tuesday: "a[a[1],f(f(0))]" should have been "a[a[1]][f(f(0))]".
• The midterm exam will be on Thursday February 14, during regular lecture hours. (Usual time and place.) One cheat sheet allowed. Absolutely NO valentines during the exam! If you want to exchange valentines with a class mate, do it before of after class.
• Homework 1 is due on Tuesday Jan. 29.
• TA office hours scheduled on Monday and Friday, see below for room/time
• Discussion sections (every Friday at 2pm and 3pm) have finally been scheduled in room HSS 2152.
• Homework 1 is available. Solutions should be e-mailed to the TA on Jan. 29 before class. (See homework for submission instructions.) If you have any question about the submission procedure, you should send your inquiries directly to the TA.
• No discussion sessions on Jan. 9 (first week of classes)
• Instructions to install JFLAP
• Final Exam on Wednesday March 20, 3:00pm-5:59pm.

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.

Reading assignments

Chapter 1: The material covered in this chapter (mostly, proof methods) 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.

Chapter 2: Deterministic finite state automata (DFA), non-deterministic finite state automata (NFA), equivalence of DFAs and NFAs, NFAs with epsilon transitions.

Chapters 3 and 4: regular expressions, closure properties of regular languages, pumping lemma and non-regular languages.

Chapters 5,6,7: context free languages, context free grammars, push down automata, equivalence of PDA and CFG, closure properties of context free languages, pumping lemma for non-context free languages.

Chapters 8,9: Turing machines, Church-Turing thesis, diagonalization, undecidability of the halting problem, other undecidable problems (Post correspondence problem, problems about CFG and TM, etc.), relation between recursively enumerable and decidable languages, Turing reductions, map reductions (these are just called reductions in the textbook in chapter 9.3).

Course requirements and policies

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

• Attending lectures
• Studying relevant chapters of the textbook, as covered in class
• 3 Homework assignments
• 1 (in class) midterm exam
• 1 (in class) final exam

Homework assignments will use JFLAP, a java package for experimenting with automata and formal languages. Instructions to use JFLAP will be posted soon on this webpage.

Midterm will be scheduled during regular lecture hours, (exact date to be announced soon), and everybody is expected to attend. There will be no make up midterm or final. Not showing up to either exam will count as 0 grade, unless your absence is due to ademonstrated personal health problem at the time. Each homework accounts for 10% of the course grade (for a total of 30%), the midterm will contribute another 30%, and the final exam will give the remaining 40%. Both the midterm and the final exam will be closed books, closed notes. You can take 1 double sided sheet of notes to each exam exam, but the notes must be your own.

Grades will be available through GradeSource. If you are enrolled in the class you will soon 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). In particular, you are encouraged to form study groups, but no form of collaboration is allowed in the solution of the homeworks, midterm and final exams. Also, you should not use any external resource (e.g., the Internet, Google, etc.) when working on the homeworks. (Of course, using such resources as a study tool is fine, but if anything you find using such resources end up being directly useful for the solution of a homework, you should clearly acknowledge the use of the resource on your solutions to avoid academic dishonesty charges.)

Regrade requests on any assignment or exam are only accepted within a week after the graded object 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.