CSC280
Computer Models and Limitations
Instructor: Mehdi Manshadi
This
page is under construction. Contents are subject to change.
Location:
CSB 601
Time: MW 3:25-4:40
Instructor's office hours:
Please make an appointment by email.
TA:
Curtis Menton
TA's office hours:
TR 2-3pm (CSB 617)
Workshop Leaders:
Adina Rubinoff (Tuesdays), Scott Ames (Fridays)
Michael J. Sipser,
Introduction to the Theory of Computation
(2nd edition), Thomson (Course Technology), 2006.
or
alternatively,
John E. Hopcroft
and
Jeffrey D. Ullman, Introduction
to Automata Theory, Languages, and Computation. Addison-Wesley,
1979.
-Both
are on reserve in the library. There will be handouts for the topics
not
covered in the book.
Workshop 5%
Homework 15%
Quiz 10%
Short Exams 10%
Midterm 20%
Final: 40%
There will be 15
workshops. Each workshop will be held twice: Fridays 3:30-5pm and the follwoing Tuesdays 5-6:30pm, both in CSB 632 (e.g. Workshop-1 will be held on Friday 1/15 and Tuesday 1/19, Workshop-2 will be held on Friday 1/22 and Tuesday 1/26, etc.). Attending one session of each workshop is required and counts for 5% of your final grade.
There will be 15
problem sets, posted on the course web site on Wednesdays right
before class. The assignments are due 1 week
later in
class (except the one assigned before spring break, which will be due
the
Monday after break). No late submissions
will be accepted. In order to allow for any sick days, religious
holidays,
unavoidable trips, etc. the lowest 3
problem set grades will be dropped.
There will be 15-20
quizzes with no advance warning (exception: there will be a
quiz on the first day of class!), given at the beginning, in the
middle, or at
the end of the class. The quizzes may be based on the two previous
lectures,
the reading assigned for the day, the lecture just given, or the
assignment due
that day. You will get 25% of the score
just for taking
the quiz. As with homework, the lowest 3
quiz grades will be dropped.
There will be two short exams, at the
end of
the first and third quarters of the semester, covering part 1 (Automata) and part 3 (Complexity) of the
course respectively
(See course syllabus below). They each contribute 5% to your final
grade.
There will be a midterm on Wednesday
3/17,
covering the first two parts of the course (Automata
and Computability). The midterm counts
for 20% of your final grade.
The final exam will be on May 3rd at 8:30AM.
It is cumulative, and counts for 40% of your final grade. The final
will be an
open-book exam.
Collaboration
on homework is allowed as long as
no written solutions are taken out of the discussion, and each student
writes
up their own independent solution.
Date |
Topic |
Reading
assignment |
Slides |
HW |
|
W 1/13 |
Introduction |
This handout SP Ch. 0/HU Ch. 1 |
||
|
M 1/18 |
Martin Luther King Day, No class. |
|||
|
Part
1. Automata |
||||
|
W 1/20 |
Strings, Languages, and Regular Expressions |
|
||
|
M 1/25 |
Finite Automata |
|
|
|
|
W 1/27 |
Regular Grammars, Equivalence of the models |
|
|
HW3 |
|
M 2/1 |
Properties of Regular Languages |
|
|
|
|
W 2/3 |
Context-Free Grammars |
|
|
HW4 |
|
M 2/8 |
Push Down Automata |
|
|
|
|
W 2/10 |
Pumping Lemma |
|
|
HW5 |
|
M 2/15 |
Review, Q&A, Short Exam 1 |
|
|
|
|
Part
2. Computability |
||||
|
W 2/17 |
Turing Machines |
|
|
HW6 |
|
M 2/22 |
Alternative definitions |
|
|
|
|
W 2/24 |
Decidability |
|
|
HW7 |
|
M 3/1 |
Reduction |
|
|
|
|
W 3/3 |
Post Correspondence Problem |
|
|
HW8 |
|
M 3/8 |
Spring break |
|||
|
W 3/10 |
||||
|
Part
3. Complexity |
||||
|
M 3/15 |
Review, Q&A |
|
|
|
|
W 3/17 |
Midterm |
|
|
HW9 |
|
M 3/22 |
Time complexity & the class P |
|
|
|
|
W 3/24 |
Class NP: P vs. NP |
|
|
HW10 |
|
M 3/29 |
NP-Completeness |
|
|
|
|
W 3/31 |
Space Complexity |
|
|
HW11 |
|
M 4/5 |
The class L and NL |
|
|
|
|
W 4/7 |
Review, Q&A, Short Exam 2 |
|
|
HW12 |
|
Part
4. Advanced topics |
||||
|
M 4/12 |
Kolmogorov Complxity |
|
|
|
|
W 4/14 |
Cryptography and one-way functions |
|
|
HW13 |
|
M 4/19 |
Randomized computation and the class BPP |
|
|
|
|
W 4/21 |
Take it easy: Approximation |
|
|
HW14 |
|
M 4/26 |
Take
it easy [cont.]: Average Case Complexity |
|
|
|
|
W 4/28 |
Something
fun: Quantum computing and the class BQP |
|
|
HW15 |