Models of Computation

CSCI 2400 - Spring 2012



Announcements

Homework 2 has been posted. It is due on Thursday, February 16, by 6pm.

Class on Monday, February 13, will be taught by Prof. Krishnamoorthy. Prof. Drineas' office hours on Monday, February 13, are cancelled; if you need to contact him, please send him an email.

Homework 1 is due on Thursday, February 9, by 6pm.

The first midterm will be on Monday, February 27, in class.


General Course Information PLEASE NOTE: The instructor will hold office hours in his office at Lally 317. The TAs will hold office hours at Amos Eaton 217.

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

Learning outcomes: At the end of the course, the student (i) is able to distinguish between various computational models, (ii) is able to determine whether a problem (language) is solvable (acceptable) within a computational model or not, (iii) is able to apply theoretical tools (such as the pumping lemma, diagonalization arguments, etc.) in order to prove impossibility results, (iv) is able to think critically on the difficulties of key questions in theoretical computer science, and (v) can recall key facts regarding finite automata, pushdown automata, and Turing machines.


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 Student Experience office (4th floor of Academy Hall, x8022, se at rpi dot edu). 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 RPI LMS. Once the grades have been posted, you can pick up the assignment from folders outside the instructor's office at Lally 317. 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.
  • Homework 1, due by 6pm on 2/9. Grader: TA White. Grades posted on XX/XX, pick up your homework from Lally 317.
  • Homework 2, due by 6pm on 2/16. Grader: TA Busch. Grades posted on XX/XX, pick up your homework from Lally 317.

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, Monday, February 27, 2012.