Models of Computation

CSCI 2400 - Spring 2008



Announcements

Final letter grades for the course have now been posted.


General Course Information TAs as well as the instructor will hold office hours in their offices.

Textbook: "Introduction to the Theory of Computation", by Michael Sipser (PWS Publishing Company). The book is available at the RPI bookstore. Please note that the slides are the primary source of study material for this course; we will not cover the whole book, and we will cover some topics that are not covered in the book.

Grading: Homeworks 30%, Midterm 30%, Final 40%. There will be eight to ten homeworks. Both the midterm and the final will be in class; the final will be in the last day of classes. Students whose course average is above 90% will get an A in this course, students whose course average is between 80% and 90% will get a B in this course, students whose course average is between 70% and 80% will get a C in this course, and students whose course average is between 60% and 70% will get a D in this course. The instructor adjusts (lowers) these bounds depending on the final curve of the grades in the course.

Description: The course will have 3 parts. The first part will cover regular languages, non-deterministic finite automata and the pumping lemma for regular languages. There will be a midterm after this part, testing your understading of the material. The second part will cover pushdown automata, context free languages and grammars, the pumping lemma for context free languages, and Turing machines. The last part will cover decidability and an introduction to complexity theory. The final exam (a longer midterm) will only cover the last two parts of the course.


Lectures

Part 1 Part 2 Part 3

Homeworks

Homeworks should be written by individuals alone. If anyone is caught cheating, then severe measures will be taken, depending on the gravity of the offense. Such measures include significant lowering of the final grade and reporting the event to the appropriate authorities in the campus.

No homework extensions will be granted under any circumstances, unless approved by the Dean of Students. Homeworks are generally due on Thursday, by 6pm (sharp), in the box outside the Instructor's office at Lally 317. You can check your grades online at WebCT. Once the grades have been posted, you can pick up the assignment from the TA, during his office hours or outside his office. Any request to re-evaluate a grade must be made within one week of the return date of the homework in question; return dates will be posted.

Solutions for the homeworks will be posted on WebCT.
  • Homework 1, due by 6pm on 1/31. Grader: TA Lewis. You may pick up your assignment from a box outside AE 219.
  • Homework 2, due by 6pm on 2/7. Grader: TA Boutsidis. You may pick up your assignment from a box outside AE 112.
  • Homework 3, due by 6pm on 2/14. Grader: TA Lewis. You may pick up your assignment from a box outside AE 219.
  • Homework 4, due by 6pm on 3/6. Grader: TA Boutsidis. You may pick up your assignment from a box outside AE 112.
  • Homework 5, due by 6pm on 3/27. Grader: TA Lewis. You may pick up your assignment from a box outside AE 219.
  • Homework 6, due by 6pm on 4/3. Grader: TA Boutsidis. You may pick up your assignment from a box outside AE 112.
  • Homework 7, due by 6pm on 4/10. Grader: TA Lewis. You may pick up your assignment from a box outside AE 219.
  • Homework 8, due by 6pm on 4/17. Grader: TA Boutsidis. You may pick up your assignment from a box outside AE 112.

Exams

There will be one short midterm after the first part of the course, and a longer midterm (final) at the end. Exams are closed book, but you may bring one double-sided A4 page with notes in the exam. Any request to re-evaluate a grade must be made within one week of the return date of the exam in question.
  • Midterm, in class, 2/21. Graded midterms are outside TA Lewis' office at AE 219.
  • Final, in class, 4/28.