CS381: Introduction to Theory of Computing

Fall 2007

[Location] [Announcements] [Course Staff] [Office Hours] [Textbook] [Grading] [Exams] [Concepts] [Homework]

Announcements

[December 11, Tuesday] Solutions to old final exams are now available online. Before reading them, please read the disclaimer, which appears on the first page of the document. They are available at Old Finals Solutions.
[December 11, Tuesday] Final exam from last year (Fall 2006) is available now. See the Exams sections.
[December 06, Thursday] Prof. Hopcroft's office hour for Friday, December 07 (1:30--2:30) has been cancelled. Please email Prof. Hopcroft or Yogi if you need to schedule an appointment.
[December 05, Wednesday] Griffin's office hour today is cancelled.
[November 30, Friday] There are no office hours today. Prof. Hopcroft will resume office hours next week as sched.
[November 21, Wednesday] There are no office hours this week after Prof. Hopcroft's office hour on Wednesday 11--12.
Homework 12 is online. It is due November 16.
Professor Hopcroft's Office Hours are cancelled today - 11/5/07 - due to illness.
Homework 11 is online. See the homeworks section below. It is due on November 09, Friday.
Solutions to prelim 2 are online (via CMS).
There is a review session for Prelim 2 on Wednesday 10/31, 6:30--8:00pm. Room number: to be announced (somewhere on the second floor of Upson).
Solutions to all homeworks are now available via CMS.
Here are some extra office hours for prelim 2 during the week of 10/29--11/02.
- Tuesday: 12:00--1:00 (Aaron)
- Thursday: 4:30--5:30 (Griffin)
[October 26 (Friday)] Homework 10 is available now. Note that it is due on Monday (November 05), not on Friday (November 02).
[October 26 (Friday)] Professor Hopcroft is out of town next week (week of 10/29--11/02). His office hours are cancelled for the next week hence. There will be more office hours by TAs, which will be announced shortly.
[Wednesday, October 10] Ray's office hour for Thursday, October 11 are cancelled.
[Thursday, October 04] Solutions to prelim 1 are now available via CMS.
Homework 7 is online now. Due on Friday, October 12.
[Thursday, October 04] Yogi's office hour today is from 1:25 to 2:25 (not 2--3).
Extra office hours for Homework 5 which is due Monday.
- Saturday 5:30--6:30. 328 Upson. Yogi Sharma.
- Sunday 6:00--7:00. 328 Upson. Yogi Sharma.
[Friday, September 28, 2007] Homework 6 is online, so is the bounus problem for prelim 1. See the homeworks section below.
[Tuesday, September 25, 2007] There is a slight mistake in Homework 3, Problem 3 solution. The first line in the solution should read: 1*(01*0)*1*. (The last 1* was missing from the solutions.)
[Tuesday, September 25, 2007] Solutions to homework 4 ~~(except for problem 4)~~ are online (via CMS). In problem 1 solution, third to last line should read: "A single 2 seperates substrings of 0's and 1's."
[Monday, September 24, 2007] There is a review session for prelim 1 today (September 24) from 7 to 9. ~~Check back later today for venue of the review session.~~ The review session is in UP 111.
[Monday, September 24, 2007] We have scheduled a few extra office hours for prelim 1. Please have a look in the office hours section below.
[Saturday, September 22, 2007] Homework 5 is now available online (see the homework section). Note that because of prelim next week it is due on Monday October 01, 2007, not on Friday.
[Thursday, September 20, 2007] Solutions to homework 3 are now available on CMS.
Homework 4 is available now. See the Homeworks section.
Last years' exams (prelims and finals) are now available. See the exams sections below.
The list of topics covered in lectures can be found in the concepts document. It is in the concepts section (see below).
[September 12, Wednesday] Yogi's office hour for today has moved to 2:30--3:30.
[September 11, Tuesday] Homework 2 is graded, please have a look at your grades in CMS to ensure everything is all right. Solutions to Homework 2 problems are also available on CMS; go to homework 2, and solutions are under "Files" section.
Homework 3 is available now (See homeworks section for .ps version). Due on September 14 (Friday).
[September 06, Thursday] Yogi Sharma's office hour on Thursday is from 2:00 to 3:00 (not 1:30 to 2:30 as was on the website earlier).
Ray Wang will not hold his office hour on Thursday, September 06 (11--12). Instead, his office hour is on Wednesday, September 05, 11:30--12:30.
[September 03 (Monday)] Solutions to Homework 1 are now available via CMS.
[September 03 (Monday)] Prof. Hopcroft will not hold office hours on September 05 (Wednesday), September 06 (Thursday), and September 07 (Friday).
Homework 2 is now available. (See homeworks section.) Due on Friday, Septemeber 07, 2007.
[August 31 (Friday)] Prof. Hopcroft's Friday office hour has moved (from 11:00--12:00) to 1:30--2:30. Today (onwards), his office hour time on Fridays is 1:30.
[August 29 (Wednesday)] Extra office hour (by Yogi Sharma): Thursday August 30 from 6:00 pm to 7:00 pm. 4106 Upson Hall.
Homework 1 is posted (see homeworks section).
Welcome to 381.

Course Staff

Course staff mailing list: cs381-l@lists dot cs dot cornell dot edu
NOTE: Students cannot subscribe to the mailing list; you can email questions to the course staff via the list.
Instructor: Prof. John Hopcroft
TAs
- Andrew Chan
- Griffin Dorman
- Haibo Lu
- Yogi Sharma
- Aaron Sidford
- Ray Wang

Note: Please use the course email list (cs381-l@lists address) to contact the course staff. That way, any memeber of the course staff can see your email, and appropriate person can reply.

Office Hours

Locations of office hours (except for Prof. Hopcroft's office hours) is 328 Upson Hall.

Monday
- 11:00--12:00, Prof. John Hopcroft (Upson 5144)
Tuesday
- 11:00--12:00, Prof. John Hopcroft (Upson 5144)
- 4:30--5:30, Haibo Lu
Wednesday
- 11:00--12:00, Prof. John Hopcroft (Upson 5144)
- 1:30--2:30, Griffin Dorman
- 3:00--4:00, Yogi Sharma
- 4:00--5:00, Andrew Chan
Thursday
- 11:00--12:00, Ray Wang
- 12:00--1:00, Aaron Sidford
- 2:00--3:00, Yogi Sharma
- 3:00--4:00, Prof. John Hopcroft (Upson 5144)
Friday
- 1:30--2:30, Prof. John Hopcroft (Upson 5144)

Extra office hours for prelim 1

Monday September 24, 2007.
- 1:15--2:15. Griffin Dorman
Tuesday, September 25, 2007.

9:30--10:30. Ray Wang
5:30--6:30. Andrew Chan
5:30--6:30. Haibo Lu.

Textbook

Introduction to Automata Theory, Languages, and Computation / John E. Hopcroft, Rajeev Motwani, Jeffery D. Ullman (2nd or 3rd Edition).

Grading

Attendance is mandatory. Schedule job interviews on Tuesdays or Thursdays.
Grades will be based on the following
- Homework: 50%
- Quizzes: 10%
- Prelims: 2 x 10%
- Final: 20%
Grading scheme
- 90--100: A
- 80--90: B
- 70--80: C

Policies

Regrade policy

All regrade request for a homework/exam/quiz must be submitted within one week of the day homework/exam/quiz is handed back in class.
- If you believe we have made an error in grading any of your work, complete the course regrade form, giving a clear explanation as to what you believe is wrong and turn the homework in again with the regrade form attached to the front.
- All students should check CMS at least weekly to make sure we have recorded your work correctly. We want to make sure that you get all the credit you deserve. We work on the honor system. If we have misplaced a paper of yours, simply tell us and we will honor your statement.

Exams

Prelim 1 (HO B14): Wednesday September 26, 2007
Prelim 2 (HO B14): Friday November 2, 2007
Final (HO B14): Thursday December 13, 2007 (7:00 pm to 9:30 pm)

Old exams

Fall 2002: Prelim1 (solutions), Prelim2 (solutions), Final (solutions)
Fall 2003: Prelim1 (solutions), Prelim2 (solutions) Final (solutions)
Fall 2004: Prelim1 (solutions), Prelim2 (solutions), Final (solutions)
Fall 2005: Prelim1 (solutions), Prelim2 (solutions), Final (solutions)
Fall 2006: Prelim1 (solutions), Prelim2 (solutions), Final (solutions)
Solutions to Finals 2002, 2003--2006.

Concepts document

Here is the list of topics covered in lectures.

Homework is due every Friday. No late homework will be accepted without a medical reason (we operate on the honor system). We encourage your helping others. There is no "competition" for a grade; grades are on absolute basis. We will grade on correctness and clarity.

Two principles:

write up in your own words
you must understand everything you turn in

Graded homeworks will be taken to the lecture, if you are unable to pick up the homework on the day it is distributed in lecture, you can pick yours from UP 360. You must show your Cornell ID to pick up your assignments.

Homework 1 (.doc). Due Friday August 31, 2007 (in class).
Homework 2 (.ps, .pdf)
Homework 3 (.ps, .pdf)
Homework 4 (.ps, .pdf)
Homework 5 (.ps, .pdf)
Bonus problem for Prelim 1 (.doc) (.ps, .pdf)
Homework 6 (.doc) (.ps, .pdf)
Homework 7 (.ps, .pdf)
Homework 8 (.ps, .pdf). Due Friday, October 19, 2007 (in class).
Homework 9 (.doc)
Homework 10 (.ps, .pdf). Due Monday, November 02, 2007 (in class).
Homework 11 (.doc)
Homework 12 (.doc)
Homework 13 (.doc). The problems are: (1) 9.1.3, (2) 9.2.1, (3) 9.2.2, (4) 9.2.5, and (5) 9.2.6, all from the textbook. Due November 26, 2007 (Monday).
Homework 14 (.doc, .txt) Due November 30, 2007 (Friday).