198:538: Complexity of Computation

Meeting times and locations: Mondays and Wednesdays, 2:50--4:10, in Hill 120
Index number for registration: 54420

Professor Eric Allender

Phone: (732) 445-3629
FAX: (732) 445-0537

Email: allender@cs.rutgers.edu

Office: Hill 442
Click here for current Office Hours.

Teaching Assistant: Sambuddha Roy
Phone: (732) 445-4467

Email: samroy at paul.rutgers.edu

Office: Hill 418
Office Hours: Wednesdays 5:00-7:00

Click here for information about homework.
This year, the texts for the course will be

We will augment with notes and papers, as needed. In addition, students may find some of the following books to be useful as references. However I do not anticipate making specific reference to these materials.

Rough Outline

The actual list of topics may vary slightly from the list that follows below, depending on the interests of the class. Prerequisites: 198:452, 198:509, and 198:513, OR familiarity with the basic notions of data structures and algorithms, and common models of computation (e.g., Turing machines, finite automata, etc.)

Expected Work: Homework assignments

NOTES for the 1998 offering of the class are available by clicking here.

Some notes for the 2000 offering of the class are available by clicking here.