CS 584: Theory of Computation and Computational Complexity - Spring 2005

Professor

Gopal Pandurangan (gopal@cs.purdue.edu)
Office: CS 128
Office hours: by appointment

Lectures

M,W,F; 1.30-2.20pm; SMTH 201

Teaching Assistant

Deepak Bobbarjung (drb@cs.purdue.edu)
Office: CSG64
Office hours: Mon, Wed 12.25pm - 1.25 pm

About this course

Welcome to the theory world!! This is a graduate-level course on theory of computation. The official (undergraduate) prerequisite is CS483 (Introduction to Theory of Computation). (Note: If you have not taken this prerequisite or its equivalent, you cannot take this course.)

Topics

  • Introduction: Problems and Algorithms
  • Turing Machines
  • Computability
  • Logic: Boolean, First-Order, Undecidability
  • Time and Space Complexity Classes; P and NP
  • Reductions and Completeness
  • Randomized Computation and Complexity
  • Approximation Algorithms and Approximability
  • Cryptography
  • More ...

    Textbook

    Computational Complexity by Papadimitriou.

    Grading

    There will be 4 or 5 homework assignments. (The assignments have to be done in Latex. If you are not familiar with Latex please learn as soon as possible. This is quite easy: there are tutorials on the Web and we will also provide you with a template file to get started.) Assignments will be non-collaborative i.e., you should work independently. You should refer only to the textbook, class notes, and any handouts given in class. Cheating on the non-collaborative policy of the assignments or on the exams will be taken seriously.
    There will also be a midterm and a final (with a Ph.D. qualifying exam supplement). The (tentative) split up is:
    assignments: 20%
    midterm:40%
    final: 40%

    Lecture Notes

    Lecture 1: 1.pdf
    Lecture 2: 2.pdf
    Lecture 3: 3.pdf
    Lecture 4: 4.pdf
    Lecture 5: 5.pdf
    Lecture 6: 6.pdf
    Lecture 7: 7.pdf
    Lecture 8: 8.pdf
    Lecture 9: 9.pdf
    Lecture 10: 10.pdf
    Lecture 11: 11.pdf
    Lecture 12: 12.pdf
    Lecture 13: 13.pdf
    Lecture 14: 14.pdf
    Lecture 15: 15.pdf
    Lecture 16: 16.pdf
    Lecture 17: 17.pdf
    Lecture 18: 18.pdf
    Lecture 19: 19.pdf
    Lecture 20: 20.pdf
    Lecture 21: 21.pdf
    Lecture 22: 22.pdf
    Lecture 23: 23.pdf
    Lecture 24: 24.pdf
    Lecture 25: 25.pdf
    Lecture 26: 26.pdf
    Lecture 27: 27.pdf
    Lecture 28: 28.pdf
    Lecture 29: 29.pdf
    Lecture 30: 30.pdf
    Lecture 31: 31.pdf
    Lecture 32: 32.pdf
    Lecture 33: 33.pdf
    Lecture 34: 34.pdf
    Lecture 35: 35.pdf
    Lecture 36: 36.pdf

    WebCT

    We will use WebCT to turn in assignments.

    Newsgroup

    We plan to use the purdue.class.cs584 newsgroup ( on the server news.purdue.edu) for announcements and other postings. You should subscribe to this newsgroup and check it regularly. Send all general questions (such as clarifications regarding assignments etc.) to this newsgroup.