Mihai replaced Bill Steiger.

[Home] [Lectures] [Assignments]

**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 (more backtracking).
- (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 materials allowed.
- (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 something.
- (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**(mip@alum.mit.edu) 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 on Fridays.
- (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.