|
|
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:30-4:30pm, Mon |
|
TA |
Chih-Yuan Yang |
SE1 281 |
cyang35 |
AOA 142 |
3:30-4:30pm, Wed |
-
Michael
Sipser, Introduction
to the Theory of Computation, 2nd
(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 |
|
|
|
1-1 |
1/27 |
|
|
|
Discussion
1 |
1/28 |
DFA
(see CROPS) |
|
|
1-2 |
1/29 |
|
|
|
2-1 |
2/3 |
HW01 released |
|
|
Discussion
2 |
2/4 |
DFA
and NFA (see CROPS) |
|
|
2-2 |
2/5 |
|
|
|
3-1 |
2/10 |
|
|
|
Discussion
3 |
2/11 |
FA
and Regular Language |
|
|
3-2 |
2/12 |
|
|
|
4-1 |
|
No
Lecture (Presidents Day Holiday) |
HW01 due |
|
Discussion
4 |
2/18 |
Regular
Expression and Regular Language |
|
|
4-2 |
2/19 |
HW02-(a) released |
|
|
5-1 |
2/24 |
|
|
|
Discussion
5 |
2/25 |
Pumping
Lemma and Closure Properties |
|
|
5-2 |
2/26 |
HW02 released |
|
|
6-1 |
3/3 |
Review |
|
|
Discussion
6 |
3/4 |
Review |
|
|
6-2 |
3/5 |
Midterm 1 (during
the class) |
|
|
7-1 |
3/10 |
HW02 due |
|
|
Discussion
7 |
3/11 |
Context-free
languages and Ambiguity |
|
|
7-2 |
3/12 |
|
|
|
8-1 |
3/17 |
|
|
|
Discussion
8 |
3/18 |
PDA
and Chomsky Normal Form |
|
|
8-2 |
3/19 |
|
|
|
|
No
Lecture (Spring Recess) |
|
|
|
|
|
No
Lecture (Spring Recess) |
|
|
|
No
Lecture (Spring Recess) |
|
|
|
9-1 |
3/31 |
|
|
|
Discussion
9 |
4/1 |
Pumping
Lemma, Closure Properties, and Membership Test |
|
|
9-2 |
4/2 |
|
|
|
10-1 |
4/7 |
Review |
HW03 due |
|
Discussion
10 |
4/8 |
Review |
|
|
10-2 |
4/9 |
Midterm 2 |
|
|
11-1 |
4/14 |
Part(1):
Turing Machine, and |
HW04 due |
|
11-2 |
4/15 |
|
|
|
11-3 |
4/16 |
NP-completeness Strongly
recommended to read Section 7.3, 7.4, and 7.5 in Sipser’s
2nd edition book. |
|
|
- |
|
No
lecture |
|
|
Discussion
12-1 |
4/22 |
NP-completeness |
|
|
Discussion
12-2 |
4/23 |
NP-completeness |
|
|
13-1 |
4/28 |
|
|
|
Discussion
13 |
4/29 |
NP-completeness |
|
|
13-2 |
4/30 |
Decidability and Recognizability
(same as 4/28) |
|
|
14-1 |
5/5 |
Complexity,
Approximability… |
HW05 due |
|
Discussion
14 |
5/6 |
Review |
|
|
14-2 |
5/7 |
Review |
|
|
Final Exam |
11:30-2: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
high-level 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 web-search 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.