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: Recommended:

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.