Syllabus

THEORY OF COMPUTING

Com S 331

Syllabus

This is a course on the theoretical foundations of computer science. We will study the fundamental models of computing and understand their theoretical limitations. Which problems can be solved by a computer? Are there problems that cannot be solved by any computer? To answer these questions, we need to learn to reason mathematically.

The course will go over three models of computation; the finite automaton, the pushdown automaton and the Turing Machine. We will study the class of problems that can be solved in each of these models.

(i) Math 166, (ii) English 104, (iii) Com S 330 or Cpr E 310.

All undergraduates will need to have these three pre-requisites before they can take Com S 331. In addition, Computer Science undergraduates will need to have at least a C- in these courses. Graduate students may have some or all of these courses waived at the discretion of the instructor, if they can show proof of having taken the equivalent courses elsewhere.

Grading will be based on weekly homeworks and three one-hour exams. There will be no final exam.

Your final grade will be decided by an absolute grading scale as following:

Assignments

Homeworks will be due every Friday except the first Friday, and the other two Fridays on which exams will be held. So there will be twelve assignments in total. All assignments will be posted on the web page on Friday, starting January 17, and will be due on the following Friday, starting January 24.

The homework must be submitted at the beginning of the lecture on the due date. Any homework turned in after this time will be considered late. Please do not submit homework once class has started since this is disruptive! Late homework will be accepted upto one class period after the due date for a penalty of 25%. Homework will not be accepted beyond that time.

Exams

There will be three one-hour exams. Roughly speaking, the first exam will focus on Finite Automata and Regular Languages, the second exam will focus on Pushdown Automata and Context-free Languages, and the third exam will cover Turing Machines and Computability. Since the material is cumulative, you may be tested on topics covered in earlier exams as well. For example, in the third exam, you may be asked to compare Finite Automata, Pushdown Automata and Turing Machines.

The first exam will be on Monday, February 24, the second on Monday, April 7, and the third on Thursday, May 8. The first two will be held during the regular class time while the third will be held during the scheduled final exam time. Further information on the exams, including dates and topics, will be posted on the Exams page.

Office Hours

Office hours are provided to answer any questions that you have regarding lecture material, exams or homework. Please take advantage of this opportunity.

If you have questions with short answers or you cannot attend any of the office hours, alternatively, you can e-mail us at cs331staff@iastate.edu.

The class web page is located at the following URL : http://www.cs.iastate.edu/~cs331/. You should check the web page constantly for announcements regarding homeworks, exams and other information about this course.

In this course, you are encouraged to discuss assignments with other students since this helps in understanding. (Do not assume this is true in all your courses!) However, the solutions you turn in must be written individually, based on your own understanding. Plagiarism will be dealt with harshly. You should consult the University Policy for details regarding academic misconduct and its consequences.

Iowa State University - Computer Science Department - Top of this page