CSC2401 Home Page (Fall 2007)
This page will provide WWW access to various documents concerning csc2401.
Some of these documents are electronic versions of
handouts given in class. Announcements will also be made on
this page.
Announcements for week of December 10.
Since I didn't have a chance to post an additional problem
it seems only fair to leave the assignment with just three questions.
Anastasios Zouzias noticed a glaring typo in the third
question. Namely the probability should be \geq 1 - 2^{-n}
and not 1-2^n.
As I indicated in class, I am willing to receive the third
problem set up to Decemeber 28 in order to accomodate anyone travelling
before the holidays. However, I suggest finishing the assignment
by the original December 21 due date and then you can really enjoy the
holidays. You can either submit an electronic
version to Periklis (papakons@cs) or make arrangements with Periklis
to submit a hard copy. Periklis will be here (around the department
over the holidays).
I will be away after December 17.
The department will close for the holiday on the 21st.
Once again, I wish you all an enjoyable holiday season.
Please send any comments or questions to the instructor:
This course is a standard graduate level introduction
to complexity.
The text is ``Computational Complexity: A Modern Approach'' by
Sanjeev Arora and Boaz Barak. The text is now in press and
should be released within the fall term. A version of
the text appears on the web site of Professor Arora
and we have been given explicit permission to use this version.
We will follow previous versions of this course although
now using the new text. However, in many regards the
the course will be quite similar to the versions taught in 2001,
2003 and 2005.
Syllabus
Syllabus
Problem Sets, Tests and Other Handouts will be posted here.
Problem set 1 in pdf format
Problem set 2 in pdf format
Problem set 3 in pdf format