CS172 Computability and Complexity (Spring'09)
Mihai replaced Bill
- Lecture: Monday & Wednesday 10:40-12:00 in Soda 320
- Sections: Friday 12-1 and 1-2, in Evans 85.
- Mihai's office hours: Mihai is often available in Soda 643 on
Monday & Wednesday afternoons. To make sure a specific time
works, send email.
- Omid's office hours: Mondays, 2-3PM in Soda 751.
- Prerequisites: It is assumed you are familiar with the
material in an upper division algorithms course (CS 170 or
equivalent) and a basic Discrete Mathematics course (such as Math 55
or CS 70).
- Expected work: Regular (weekly) problem sets, one midterm, final exam.
- (Apr 22) Sample final. The real final
will have 4 questions, covering the following topics:
decidability/undecidability, membership in P (dynamic programming),
backtracking, membership in NP, NP-hardness, membership in PSPACE
- (Apt 6) The final exam will be in class on Monday, April 27.
- (Apr 6) Homework 8 posted. From now on, homeworks are due on Mondays.
- (Mar 30) Homework 7 posted. Due April 2.
- (Mar 11) Remember that the midterm is next Monday. Here is a sample midterm. Please bring paper to
write on. You may also bring one sheet of paper (double-sided,
letter size) containing any notes you care to use. No other
- (Mar 9) If you have questions about Turing machines, take a look
at this video.
- (Mar 5) Homework 6 posted. Due March 12.
- (Mar 4) In homework 5/problem 1, there were misunderstandings
about what "reading from standard input" meant. The homework PDF now
includes an example. In C, you may just use "gets(needle);" to read
- (Mar 2) Homework 5 and "attachments" are up. Due March 5.
- (Mar 2) The midterm date has been fixed to Monday, March 16
- (Feb 25) Send Mihai email (firstname.lastname@example.org) indicating
whether you want to receive announcements by email. Announcements will
always be posted here, and only emailed to people who opt in.
- (Feb 23) Mihai is taking over the course from Bill Steiger.
- (Feb 21) Some Homework 2 solutions are posted.
- (Feb 19) Homework 4 is available, and due in a week.
- (Feb 12) Homework 3 is available, and due in a week.
- (Feb 10) Solutions for Homework 1 are posted. A handout on minimal
DFA's is available.
- (Feb 5) Homework 2 is available; due in a week.
- (Feb 2) Correction: HW1 said it was due on Feb 4. The actual
date is Thursday, Feb 5.
- (Jan 29) Homework 1 is available; due in a week.
- (Jan 28) Discussion sections will be in 85 Evans, 12-1 and 1-2
- (Jan 22) There will be no section meeting the first week.
Homeworks will begin during the next week, posted on Thursday and due
one week later.
- (Jan 21) Homework 1 will be posted on the "homeworks" page
before Jan 23. It will be due a week later.