Theory of Computation (600.471)

Lecture Time	TuTh 12:00-1:15pm
Venue	202 Shaffer Hall, JHU Homewood
Instructor	Vinod Variyam
Office	200c Shaffer Hall
Email	vinod@cse.unl.edu
Office Hours	By appointment


CA	Parsia Hakimian
Office	Masters Lab, Shaffer 4th Floor
Email	parsiya@gmail.com
Office Hours	Mon 11-1pm, By appointment

Course Summary and Prerequisites

This course introduces students to the theoretical foundations of computer science. Topics covered will be models of computation from automata to Turing machines, computability, and basics of computational complexity theory. This will be a mathematically oriented course. We will use a "pencil-and-paper" approach and will avoid implementations/programmings. It is expected that the students know basic discrete mathematics and are familiar with writing mathematical proofs. A note on the related course 600:271 - you will not get credit for both 600.271 and 600.471, unless one is for an undergrad degree and the other is for a graduate degree.

Text Book and Topics

The course will be mainly based on the book Introduction to the Theory of Computation (2nd Edition) by Michael Sipser which should be available to purchase at the JHU Bookstore. (There is a 3rd edition, but it will be sufficient to have a copy of the 2nd edition.) The text book is divided in three parts : (1) Automata and Languages (2) Computability Theory (3) Complexity Theory. We intend to cover most of the major topics from parts (1) & (2), and selected topics from part (3).

Homeworks, Exams, and Grading

Grading will mainly be based on Homeworks and Exams. There will be many homework assignments each carrying equal weight. There will be 3 midterm exams (quizzes), each carrying equal weight. There will be an optional Final exam which will be cumulative. The following weighting will be used to calculate your grade.

Homeworks 45%

Exams 55%

Final examination is optional. If you are satisfied with your grade by the end of the semester, you need not take the finals. But if you choose to take the finals, then the finals will carry 40% weight and each midterm will carry 20% weight, of all the exams. Following is a tentative schedule of the exams.

All exams are open text/note book.

Schedule of Exams (tentative)

Exam 1	Thu Sep 20
Exam 2	Thu Oct 25
Exam 3	Tue Dec 4
Finals	Mon Dec 17, 2-5pm

Clarity and legibility of presentation of your submissions are as important as your answers to problems. For homeworks, you are very strongly advised to typeset your solution using some document processing system. If the grader cannot easily read your writings, you may not be awarded full points even if you claim your answers are correct.

Collaboration Policy

Collaboration with your fellow students are only allowed at an intuitive level. That is, the strategy and general approach of solutions may be developed jointly with other fellow students, but all details of the solutions must be constructed and written only by you. If you collaborate, then you must include an explicit acknowledgment in your solution of the persons with whom you collaborated. Unacceptable collaboration will be considered a violation of the Student Code of Conduct, and will result in a failing grade for the course.

More details about homework requirements/policy (such as late submissions and other requirements) can be found at TA's page.

Academic Integrity

Students enrolled in any computer science course are bound by the department's and the university's Academic Integrity Code. It is expected that the every student reads and understand it. Any violation of the policy will be dealt with severely.