**THEORY OF COMPUTING**

**Com S 331**

**Syllabus**

Introduction and Objective |

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.

Prerequisites |

(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 Policy |

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

Homeworks 25% |
3 Midterms (25% each) |

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

Score |
Grade |

at least 90 |
A |

at least 85 but less than 90 |
A- |

at least 80 but less than 85 |
B+ |

at least 75 but less than 80 |
B |

at least 70 but less than 75 |
B- |

at least 65 but less than 70 |
C+ |

at least 60 but less than 65 |
C |

at least 55 but less than 60 |
C- |

at least 50 but less than 55 |
D+ |

at least 45 but less than 50 |
D |

at least 40 but less than 45 |
D- |

less than 40 |
F |

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

**Web Pages**

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.

**Academic Honesty**

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