|
|
Time |
Location |
|
Lecture |
4:30~5:45pm, Tue, Thu |
Classroom 113 |
|
Discussion |
7:30~8:20am, Thu |
SSM 104 |
|
|
Name |
Office |
Email |
Office Hours |
|
|
Location |
Hours |
||||
|
Instructor |
Sungjin Im |
SE2 214 |
sim3 |
SE2 214 |
6:00-7:00pm, Thu |
|
TA |
Maryam Shadloo |
SE2 213 |
mshadloo |
AOA 142 |
8:30-9:30am, Thu |
-
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 / Announcement |
|
1-1 |
1/20 |
|
|
|
Disc1 |
1/22 |
|
|
|
1-2 |
1/22 |
|
|
|
2-1 |
1/27 |
HW01 released (deadline 4:30pm, 2/3) |
|
|
Disc2 |
1/29 |
DFA
and NFA |
|
|
2-2 |
1/29 |
NFA
(cont’) |
|
|
3-1 |
2/3 |
HW02 released (deadline 4:30pm, 2/10) |
|
|
Disc3 |
2/5 |
NFA
and equivalence of DFA and NFA |
|
|
3-2 |
2/5 |
|
|
|
4-1 |
2/10 |
HW03 released (deadline 4:30pm, 2/17) |
|
|
Disc4 |
2/12 |
Regular
Expression and Regular Language |
|
|
4-2 |
2/12 |
HW04 to be released (deadline 4:30pm, 2/26) |
|
|
Disc5 |
2/17 |
Non-regular
languages and Pumping Lemma |
Note: This disc will be in classroom 113 at
4:30pm, Tue |
|
5-1 |
2/19 |
Note: This lecture will
be in SSM 104 at 7:30am,
Thu |
|
|
5-2 |
2/19 |
HW05 to be released (deadline 4:30pm, 3/3) |
|
|
6-1 |
2/24 |
Review |
|
|
Disc6 |
2/26 |
No
discussion section |
|
|
6-2 |
2/26 |
Midterm
1 (during the class) |
|
|
7-1 |
3/3 |
|
|
|
Disc7 |
3/5 |
|
|
|
7-2 |
3/5 |
HW06 to be released |
|
|
Disc8 |
3/10 |
Note: This disc will be in classroom 113 at 4:30pm,
Tue |
|
|
8-1 |
3/12 |
Note: This lecture will
be in SSM 104 at 7:30am,
Thu |
|
|
8-2 |
3/12 |
HW07 to be released, due 3/19 |
|
|
Disc9 |
3/17 |
Grammar
Simplification and Pumping Lemma |
Note: This disc will be in classroom 113 at
4:30pm, Tue |
|
9-1 |
3/19 |
Note: This lecture will
be in SSM 104 at 7:30am,
Thu |
|
|
9-2 |
3/19 |
HW08 to be released, due 3/31 |
|
|
|
|
No
Lecture (Spring Recess) |
|
|
|
|
No
Lecture (Spring Recess) |
|
|
|
|
No
Lecture (Spring Recess) |
|
|
11-1 |
3/31 |
Review |
|
|
Disc11 |
4/2 |
|
|
|
11-2 |
4/2 |
Midterm
2 (during the class) |
|
|
12-1 |
4/7 |
See also an example of TM on crops (in
resources/supplementary) |
|
|
Disc12 |
4/9 |
|
|
|
12-2 |
4/9 |
Variants of TMs and Church-Turing Thesis See also TM_multitape.pdf and TM_nondeterministic.pdf on
crops (in resources/supplementary) |
HW09 to be released |
|
13-1 |
4/14 |
||
|
Disc13 |
4/16 |
|
|
|
13-2 |
4/16 |
Decidability and
Recognizability (same as 13-1) |
HW10 to be released |
|
14-1 |
4/21 |
||
|
Disc14 |
4/23 |
|
|
|
14-2 |
4/23 |
HW11 to be released |
|
|
15-1 |
4/28 |
NP-completeness |
|
|
Disc15 |
4/30 |
|
|
|
15-2 |
4/30 |
NP-completeness |
HW12 to be released |
|
16-1 |
5/6 |
Complexity,
Approximability… |
|
|
Disc16 |
5/7 |
|
|
|
16-2 |
5/7 |
Final
thoughts and review |
|
|
Final Exam |
8-11am, Tue, 5/12 |
Class room 113 |
|
-
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
chose to work alone. 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, and exchanging
high-level ideas. In particular, showing the final solution is strictly
prohibited.
-
You
can submit either a hard copy or soft copy. Soft copy must be submitted to
UCMCROPS; if the server is down, please email your solution to the instructor
or TA. If you want to submit a hard copy, you must give it to the instructor or
TA on the deadline before the class begins. Handwriting, scanned images of
hardcopies, and photos of hardcopies are all accepted. However, students are
recommended to submit a hard copy as well as a soft copy; hard copy makes
grading easier, and soft copy is good for the record.
-
No
late homework will be accepted, but the two lowest scores 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 are strongly recommended 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.