Date: Wed, 20 Nov 1996 21:47:09 GMT
Server: NCSA/1.5
Content-type: text/html
Computer Science 410 --- Spring 1996
Computer Science 535 - Fall 1996
Computer Science Department, Boston University
Current information
Homework: (and its solution, after the submission
date), in the directory ~cs535/gacs/handout.
Useful pointers
Instructor:Peter Gacs,
Email: gacs@cs.bu.edu,
Phone: 353-2015,
Office: MCS 277
Office hours: Tue 3:30-5:00, Wed 1:30-3:00
Time: Tue, Thu 2:00-3:30,
Place: MCS B29
Texts
Required:
- Lovasz: Computation Complexity (translation by Gacs).
file gacs/comp-th-notes.ps on ftp.cs.bu.edu (about 180 pages).
Print on publp, (two-sided), bind at the BU Copy Center.
Recommended:
-
Leonid A. Levin: Fundamentals of Computing
- Lewis-Papadimitriou: Elements of the Theory of Computation,
Prentice-Hall 1981
- Hopcroft-Ullmann: Introduction to Automata Theory, Languages and
Computation Addison-Wesley 1979.
- Papadimitriou: Computational Complexity, AW 1994, ISBN 0-201-53082-1
Description
Topics covered:
Machine models. Undecidability. Complexity notions. Some
important algorithms. Compression and speed-up theorems.
Nondeterminism. NP problems. Randomized algorithms. Prime number
tests. Description complexity, randomness, information.
Pseudorandom generators. Quadratic residuosity, and public-key
cryptography. Parallel algorithms. Exponential lower bounds,
alternating machines and games. Decision trees. Communication
complexity.
Homework
Homework:
Given every Tuesday. Must be returned next Tuesday. 50% credit if
late by one class period, no credit thereafter.
Each student can get at most one exception for not submitting homework on
time.
Exams
One midterm (one class period length) and one final exam.
Only a single double-sided sheet of handwritten notes
("crib-sheet") is allowed.
The final exam covers the whole material.
Grading
In the final grade, your homeworks count 30% and your exams 30% and 40%.
An Incomplete grade will only be given in exceptional circumstances.
Cooperation
It is OK to discuss the homework with your classmates, but you must write
it up yourself and understand it.
I will ask questions if the solution is suspicious.