CS/EE/MA 129a
Information and Complexity (Part I only)
Prof. Erik Winfree
Fall 2011. http://www.dna.caltech.edu/courses/cs129
Office Hours
Time (CS 129a): Tuesday and Thursday 1:00pm - 2:25pm
Location: Annenberg 213


Important historical papers: [ip restricted access]

Office Hours

Professor TAs (CS 129a only)
Erik Winfree
Hours: by arrangement
Office: 204 Moore
Extension: x6246
Brian Merlob and Suiyi (Doris) Xin
Ruddock dining hall : Wednesdays 8-11pm (Brian)
CS Lab, 1st floor Annenberg : Saturday 8-9pm (Brian)
CS Lab, 1st floor Annenberg : Sunday 8-9pm (Doris)
Email: <winfree@caltech.edu> Email: <cs129_ta@dna.caltech.edu>


Format: The class will be based on reading and discussion. Each week, several of pages of lecture notes will be assigned. Read them carefully and test your understanding by working out alternative proofs or invent and solve simple problems investigating the material. Monday's homework: Read the lecture notes, solve the assigned problem, provide a discussion point / clarification, and invent and solve your own problem. Typical Tuesday's class: Summary of section, explanation of discussion points by students, quiz problem & discussion. Typical Thursday's class: Continued discussion of discussion points, presentation of invented problems, quiz & discussion.

Grading: Homework (60%), class discussion (30%), in-class problems (10%). There will be no midterm or final. Attendance is mandatory. Homework questions will be open-ended; creative engagement with the subject matter is encouraged and expected. Clear presentation and rigorous proofs are important aspects of the homework exercises, and will be graded accordingly. Programming will be part of some homework.

Late Policy: Homework (a single PDF file) must be handed in by email (cs129_ta@dna.caltech.edu) before 11:59pm each Monday. Please use a subject line that contains your name, the class name "CS129", and the homework number (e.g. "HW1"); also please give your PDF a filename containing all the same information. You have 5 (total) "late days" which you may allocate as you wish to avoid the lateness penalty. For example, a homework turned in on Wednesday that was due Monday is 2 day late. When late homework is turned in, the time, date, and number of "late days" used, must be clearly stated in the email. Beyond institute-established cases of illness or emergency, no other exceptions will be granted. Use late days wisely, or not at all.

Collaboration and Open-Book Policy: Collaboration in the sense of discussions is allowed, but you should write the final solutions alone and understand them fully. Clear reasoning and presentation is as important as correctness. Do not read class notes or homework solutions from previous years at any time. Other books and notes can be consulted, but not copied from; however, they shouldn't be necessary for the homework problems. All programming must be entirely your own.


Lecture notes will be handed out in class. A preliminary schedule, subject to change, is given below. Each line corresponds roughly to one or two class meetings.