CS530 Theory of Computation Spring 2018

Remote students: please check this web page before each class and print the handouts.

Reading this page:

Please let us know if you have any trouble downloading, displaying, or printing anything on the course web site!

News

The final exam will be held as scheduled, on Tuesday May 1st, 8-10 AM. The topics for the final exam are based on the notes for the chapters 3-7 (relevant notes will be given to students with the exam), and on homeworks 3,4,5. Regular and Context Free languages may appear on the final, but only in the context of Turing Machines and/or (Un)Decidability.

The fifth homework was assigned April 12. It is due on April 26. You can download it in PDF here. Note: the latest day when this homework is accepted is the day before the final exam.

The fourth homework was assigned March 27. It is due on April 12. You can download it in PDF here.

The chapter notes on Time Complexity are available in PDF here.

The notes on NP-Completeness are available in PDF here.

Archive

The academic honesty handout and the pledge you are asked to sign and return are here.

The first-chapter notes (version 1.1) are available in PDF here.

The syllabus is available in PDF version 1.1. The information regarding TAs was updated.

The first homework was assigned Jan. 23. It is due on Feb. 6. You can download it in PDF here (version 1.1).

The second homework was assigned Feb. 8. It is due on Feb. 22. You can download it in PDF here.

The registrar has scheduled the final exam for Tuesday May 1st, 8-10 A.M.

The second-chapter notes are available in PDF here (version 1.1).


The midterm will be held as scheduled, on March 6th during regular class hours. The topics for the midterm are Regular and Context-Free Languages, as covered in the lectures and following the notes here (that will be given to students with the exam), and as tested in the first two homeworks.

The third-chapter notes are available in PDF here.

The third homework was assigned March 1. It is due on March 22, after the midterm. You can download it in PDF version 1.1. Here is the TM for problem 1 , scanned from the textbook.

The fourth-chapter notes are available in PDF here.

The fifth-chapter notes are available in PDF here.

Contact the instructor at calinescu iit edu.

Document last modified on April 12, 2018.