CS 181 Languages and Automata

 
Quarter   Fall 2016
Instructor   Prof. Alexander Sherstov
TAs   Yunzhong He, Pei Wu
Lecture   MW 2–3:50pm (BOELTER 5249, instructor)
Discussion A   F 12noon–1:50pm (HAINES A18, Pei)
Discussion B   F 2–3:50pm (HUMANTS 169, Yunzhong)
Webpage http://www.cs.ucla.edu/~sherstov/teaching/2016-fall
Textbook M. Sipser, Introduction to the Theory of Computation, 3rd ed., 2012
Office Hours MW 1:30–2pm (BOELTER 3731J, instructor)
MW 11:00am–1:00pm (BOELTER 2432, Yunzhong)
TR 10:30–12:30 (BOELTER 2432, Pei)
F 10:50–11:50 (BOELTER 2432, Yunzhong & Pei)

 

Everything should be made as simple as possible, but not simpler.

Albert Einstein

Description

This course is an undergraduate introduction to the theory of computation. We will study a variety of abstract computational devices, from very simple and limited ones to highly sophisticated and powerful: deterministic and nondeterministic finite automata, regular expressions, pushdown automata, context-free grammars, and Turing machines. We will completely characterize the relative computational capabilities of these devices. Lastly, we will discover that there are important practical problems that cannot be solved by any computational device at all!

This is a rigorous course with an emphasis on mathematical proofs. Please do not enroll if you have not taken the prerequisites, which are CS 32 "Introduction to Computer Science II" and one of MATH 61 "Introduction to Discrete Structures," MATH 180 "Combinatorics."

Grading

Homework (10 x 2%). There will be ten weekly homework assignments, each worth 2% of your course grade. Homework will be graded based on effort rather than correctness, using the following grading scheme: 2% for a good-faith effort (more than half of the problems attempted), 1% for some effort (less than half of the problems attempted), and 0% for unintelligible, late, or unsubmitted homework. Homework assignments will be posted on the course webpage by 5pm on Mondays, including official holidays. Please submit your homework by 11:50am on Friday of the same week, using the corresponding TA drop box in 2432 Boelter Hall: box A1 for Pei's discussion section, and box A2 for Yunzhong's discussion section. Homework solutions will be worked out on the blackboard in discussion sections, and solutions to the more difficult problems will be uploaded in PDF format to CCLE. Please feel free to collaborate with other students on the homework or use any outside scholarly sources. However, you must write up your solutions on your own and indicate with whom you have collaborated. If you have worked on your own, you must state that as well.

Exams (4 x 20%). There will be three exams during the quarter (October 21, November 4, and November 18) and an additional final exam (December 5). The exams are closed-book and closed-notes. The first three exams will be administered in the discussion sections; please attend the discussion section in which you are enrolled. Exam solutions will be posted on the course webpage by the end of the day on the exam date. No alternate or make-up exams will be administered, except for disability/medical reasons documented and communicated to the instructor prior to the exam date. In particular, exam dates and times cannot be changed to accommodate scheduling conflicts with other classes.

Course Schedule

The following table gives the sequence of topics that we will cover, along with the number of hours of instruction devoted to each topic and the corresponding chapters of the Sipser textbook.

Topic Hours Chapter
Finite automata Sipser 1.1
Nondeterministic finite automata Sipser 1.2
Regular expressions Sipser 1.3
Pumping lemma Sipser 1.4
Context-free grammars Sipser 2.1
Pushdown automata Sipser 2.2
Pumping lemma for CFGs Sipser 2.3
Turing machines Sipser 3.1
Variants of Turing machines Sipser 3.2
Decidable languages Sipser 4.1
Undecidability Sipser 4.2, 5.3

 

Here is a more detailed view, with the primary topic indicated for each lecture date. The color coding shows the primary scope for each of the four exams.

Homework

The problem numbers below refer to the Sipser textbook.

Week Assignment
1 1.1, 1.6 (b, d, e, f, h, j, k, n)
2 Download
3 1.16, 1.32, 1.40, 1.41, 1.62, 1.66(a), 1.69
4 1.21, 1.28, 1.47, 1.49, 1.53
5 Download
6 2.1, 2.6(d), 2.19, 2.27, 2.28(c)
7 2.11, 2.20, 2.30(a,d), 2.45
8 1.54, 1.63(a), 1.64(a-c), 2.9, 2.24, 2.31
9 3.8(b), 3.10, 3.12, 3.13, 3.16(a-d)
10 3.20, 4.12, 4.14, 4.17, 4.27

Weekly Planner

Exams from Previous Years

Below, you will find every single exam that I have administered in my previous offerings of CS 181, complete with a solution to each problem. Work on the exams on your own under the time constraints before you study the solutions. Some problems on these exams are adapted from or inspired by the following textbooks on the theory of computing: Theory of Computing: A Gentle Introduction by E. Kinber and C. Smith, Elements of the Theory of Computation by H. Lewis and C. H. Papadimitriou, Introduction to Languages and the Theory of Computation by J. Martin, and Introduction to the Theory of Computation by M. Sipser. You can download all the exams at once as a ZIP archive for convenient offline access:

ALL EXAMS

Alternately, or you can browse the individual exams below, grouped by quarter.

 

Fall 2015

1 2 3 4

 

Spring 2015

1 2 3 4

 

Spring 2014 A

1 2 3 4

 

Spring 2014 B&C

1 2 3 4

 

Spring 2013

Midterm Final

Exam Solutions

The official solutions to this quarter's exams are posted here. A problem in mathematics often has several valid solutions, so don't worry if your approach is different from the posted solutions.

Exam 1
Exam 2
Exam 3
Final Exam

Policies

Attendance and class participation. Although not a formal component of the course grade, attendance is essential for success in this course. I emphatically welcome questions and any other input from you—your active participation in this course will enhance your learning experience and that of the other students.

Academic honesty. The students are expected to fully abide by UCLA's student conduct policies, including Section 102.01 on academic honesty. You will find a wealth of helpful materials here, including the Student Guide to Academic Integrity. Academic dishonesty will be promptly reported to the Dean of Students' Office for adjudication and disciplinary action. Remember, cheating may have significant and irrevocable consequences for your academic record and professional future. Please don't cheat.

Regrade requests. Regrade requests for homework and exams must be made within one week after the graded assignments have been handed out, regardless of your attendance on that day and regardless of any intervening holidays such as Memorial Day. Please put your request in writing, indicating the parts you want regraded and why, and hand in your request in person to a TA.

Late arrival to an exam. Students arriving 15 minutes late will not be admitted to the exam and will automatically receive a score of 0. This policy applies to all four exams.

Record keeping. Students are expected to monitor their posted homework/exam scores in Gradebook throughout the quarter and bring up any inaccuracies in a timely manner, no later than 7 days of the date the scores were posted. All scores will be considered final at 5pm on Friday of Finals Week, with no further changes or corrections possible.

Email policy. Neither the instructor nor the TAs are able to take questions about course material by email, due to the large number of enrolled students as well as the considerable chance of miscommunication. Please take advantage of the abundant office hours, class time, and discussion sections to make sure that all your questions are answered.