CSC280
Computer Models and Limitations
Instructor: Mehdi Manshadi
This
page is under construction. Contents are subject to change.
Location:
CSB 601
Time: MW 3:254:40
Instructor's office hours:
Please make an appointment by email.
TA:
Curtis Menton
TA's office hours:
TR 23pm (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. AddisonWesley,
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:305pm and the follwoing Tuesdays 56:30pm, both in CSB 632 (e.g. Workshop1 will be held on Friday 1/15 and Tuesday 1/19, Workshop2 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 1520
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
openbook 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 
ContextFree 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 
NPCompleteness 



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 oneway 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 