Foundations of Computer Science

Take home final

The take home final is Due on December 15 (note extension). The fixed version is here. Please continue to write me if something looks amiss (also, be sure to hit the reload button on your browser).

Lecture: Tuesdays, 6:40-9:30 PM, in HILL-254

Office Hours:
   Joe Kilian (Lecturer): Wednesdays, 1-3, HILL 411
   Fengming Wang (TA): Mondays, 3:30-5:30, HILL 486
   (fengming@cs.rutgers.edu)

People have expressed a desire to have Monday office hours. In the coming weeks, Fengming will switch primarily to Mondays, 3:30-5:30; however, on some weeks this will not be possible. On some weeks, Joe will reschedule his office hours to Mondays.

Likely substitutions for Joe:
My apologies for the earlier message saying Monday, October 30 - for family reasons I can't be in at Rutgers that day. (for what it's worth, I did have people come to my usual office hours)

This course is still under construction!

This is the second time I will be teaching this course. Some changes have been made from last year, most notably a deemphasis in logic in favor of other topics in complexity theory.

Class Wiki

I have set up a class site on sakai.rutgers.edu. You should be set up for it. Thus far, it has been inactive, but people can use it to discuss the course.

Textbook

Our main textbook with be Sipser's, Introduction to the Theory of Computation. However, I will try to go beyond this textbook. We will experiment with having scribe notes to cover this additional material.

Grading

Grading will be based on 4 problem sets (10% each), a take-home midterm exam (25%) and a take home final (35%).

Lecture and Exam Schedule

Here is the current lecture/homework/exam schedule. It is not set in stone.

Problem Sets and Exams

Problem Set 1, due September 19.  [Solutions]

Problem Set 2, due October 3.  [Solutions]

Problem Set 3, due October 31.  [Solutions]

Problem Set 4, due November 17.  [Solutions]

The take home midterm was due on October 17. Here are the solutions

Lecture Notes

Lecture 1   [outline]

Lecture 2   [outline]

Lecture 3   [outline]

Lecture 4 first part and the last part   [outline]

Lecture 5   [outline]

Lecture 6: no scribe notes [outline]

Lecture 7 (last half)   [outline]

Lecture 8   [outline]

Lecture 9   [outline]

Lecture 10   [outline]

Lecture 11

Lecture 12   [outline]

A great set of quantum computing notes are here.

We strongly recommend doing the lecture notes in latex. Some useful latex links are here, here and here.

Fengming Wang's latex source for Lecture~1 notes are here. He used two style files: style.tex and cs509.sty.

Condon-Lipton paper on Probabilistic Finite Automata is here.

Academic Integrity

Rutger's academic integrity policy may be found here. This actually is set in stone.

For homework, you may collaborate with others, but you must

You may not search out solutions from previous years or from other courses.

For take-home exams you may not collaborate with others. You may not search out solutions from previous years or from other courses.

Deviations from the above policy constitute cheating, and will be forwarded to the appropriate discplinary committee.