Models of Computation

CSCI 2400 - Spring 2010



Announcements

Welcome to Models of Computation!


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 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.

Read this paragraph carefully!! No homework extensions will be granted under any circumstances, unless approved by the Dean of Students. Homeworks are generally due on Thursday, by 4pm (sharp), in the box outside the Instructor's office at Lally 317. You can check your grades online at RPI LMS. Once the grades have been posted, you can pick up the assignment from the TA, during his office hours or from a box 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 at RPI LMS.

  • NOT AVAILABLE YET Homework 1, due by 4pm on XX/XX. Grader: TA XXX. Grades posted on XX/XX, pick up your homework from Lally XX.

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:
  • Final: