
Time 
Location 
Lecture 
2:00~3:15, MW 
Classroom 113 
Discussion 
8:00~8:50, T 
Classroom 113 

Name 
Office 
Email 
Office Hours 

Location 
Hours 

Instructor 
Sungjin Im 
SE1 294 
sim3 
SE1 294 
3:304:30pm, Mon 
TA 
ChihYuan Yang 
SE1 281 
cyang35 
AOA 142 
3:304:30pm, Wed 

Michael
Sipser, Introduction
to the Theory of Computation, 2^{nd}
(main reference).

John
E. Hopcroft, Rajeev Motwani,
and Jeffrey D. Ullman, Introduction to
Automata Theory, Languages, and Computation.
Lecture Number 
Date 
Topics 
Homework 

1/21 
No
discussion section 

0 
1/22 


11 
1/27 


Discussion
1 
1/28 
DFA
(see CROPS) 

12 
1/29 


21 
2/3 
HW01 released 

Discussion
2 
2/4 
DFA
and NFA (see CROPS) 

22 
2/5 


31 
2/10 


Discussion
3 
2/11 
FA
and Regular Language 

32 
2/12 


41 

No
Lecture (Presidents Day Holiday) 
HW01 due 
Discussion
4 
2/18 
Regular
Expression and Regular Language 

42 
2/19 
HW02(a) released 

51 
2/24 


Discussion
5 
2/25 
Pumping
Lemma and Closure Properties 

52 
2/26 
HW02 released 

61 
3/3 
Review 

Discussion
6 
3/4 
Review 

62 
3/5 
Midterm 1 (during
the class) 

71 
3/10 
HW02 due 

Discussion
7 
3/11 
Contextfree
languages and Ambiguity 

72 
3/12 


81 
3/17 


Discussion
8 
3/18 
PDA
and Chomsky Normal Form 

82 
3/19 



No
Lecture (Spring Recess) 




No
Lecture (Spring Recess) 


No
Lecture (Spring Recess) 


91 
3/31 


Discussion
9 
4/1 
Pumping
Lemma, Closure Properties, and Membership Test 

92 
4/2 


101 
4/7 
Review 
HW03 due 
Discussion
10 
4/8 
Review 

102 
4/9 
Midterm 2 

111 
4/14 
Part(1):
Turing Machine, and 
HW04 due 
112 
4/15 


113 
4/16 
NPcompleteness Strongly
recommended to read Section 7.3, 7.4, and 7.5 in Sipser’s
2^{nd} edition book. 

 

No
lecture 

Discussion
121 
4/22 
NPcompleteness 

Discussion
122 
4/23 
NPcompleteness 

131 
4/28 


Discussion
13 
4/29 
NPcompleteness 

132 
4/30 
Decidability and Recognizability
(same as 4/28) 

141 
5/5 
Complexity,
Approximability… 
HW05 due 
Discussion
14 
5/6 
Review 

142 
5/7 
Review 

Final Exam 
11:302:30pm, Sat, 5/10 
Class room 113 
HW06 due 

You
can form a group of size up to 3, and each group only needs to submit one copy
of solutions. However, there should be no student left alone unless the student
wants to do so. If students do not follow this rule, the instructor has the
right to change groups. You can change groups for each
homework.

Students
can discuss everything within a group. However, the discussion between two
different groups must be restricted to understanding problems, exchanging
highlevel ideas. In particular, showing the final solution is strictly
prohibited.

You
can submit either a hard copy or soft copy. If you want to submit a hard copy,
you must give it to the instructor or TA on the deadline during the class. Or
you can email your solutions to the instructor or TA by the deadline.
Handwriting, scanned images of hardcopies, and photos of hardcopies are all
accepted.

No
late homework will be accepted, but the lowest score will be dropped.

Give
credits properly! The worst cheating is to pretend that someone’s intellectual
work is his/her own. You are allowed to websearch solutions. As long as you
give proper credits and state the source, you will lose no point. However, I
strongly encourage you to come up with your own solutions. Homework will be
graded very generously. Homework is designed to help you understand the course
materials and prepare for the exams. If you lose any point from your homework,
you have to take a closer look at where you made mistakes. Exams will be graded
more strictly.

If
you cheat on an assignment, you will get no point for the assignment. If you
cheat again, you will fail the course.
The instructor thanks Mahesh Viswanathan for generously sharing his lecture notes with him and allowing him to use them. Mahesh also states that his lecture notes have been strongly influenced both in form and content by discussions with and slides, talks, lectures and notes of the following people: Gul Agha, Margaret Fleck, Sariel Har Peled, P. Madhusudan, Steven Pinker, Leonard Pitt, Manoj Prabhakaran, and Steven Rudich. The instructor thanks all of them.