
CSE4111
CSE 4111/5111:
Computability and Complexity
Winter 2011
TEXTS:
Course Description
Course Syllabus
Steve Cook:
Computability and
Recursive and Recursively Enumerable Sets
Russell Impagliazzo
Notes
Jeff Edmonds' "How to Think about Algorithms"
Amazon
Cambridge House Press
Desk Copies
reviews
Michael Sipser, Introduction to the Theory of Computation,
(second edition) PWS Publishing Company, 2006.
Lewis and Papadimitriou, Elements of the Theory of
Computation (second edition) 1998.
Hopcroft, J.E. and Ullman, J.D., Introduction
to Automata, Languages and Programming, Addison Wesley, 1979.
Gems of Theoretical Computer Science (Many thanks to U. Schoning and R. Pruim)
Other References
GRADING: (Mark Alg)
Assignments (between 10% and 45%)
- Due beginning of (odd) Thurs
- May do in pairs (may change partner)
- Covering material covered by Tue before
A test every 2 weeks
(between 10% and 45%)
- (even) Thurs
- 3:00-4:00 Lets have it in our room.
(We do have SC 219 booked)
- 5:30-6:30 Stong Collage SC 220
- Covering assignment material
- Test may be out of different amounts. Total is simply the sum.
Exam
(between 0% and 70%)
Class Participation
(10%)
-
Instructions
-
Photos
Final Mark =
Σi=1..5
[
0.02 Ai + 0.07 Max(Ai,E)
+
0.02 Ti + 0.07 Max(Ti,E)
]
+ 0.10 CP
.
.
.
.
.
.
.
.