Home

Welcome to Foundations of Computer Science at Olin College, Spring 2012.

Instructor: Allen Downey.

Meetings: Monday and Thursday from 9am to 10:40 in AC326. Here is the class mailing list.

Topics: Foundations of Computer Science (FOCS) covers topics in Programming Languages, Automata, Analysis of Algorithms, and Theory of Computation.

  • We start the semester with a survey of programming paradigms, including an introduction to functional programming in Scheme and logic programming in Prolog.

  • We study formal languages and the abstract machines that process them, including regular expressions, finite state machines, context-free grammars, and push-down automata.

  • Finally, we review algorithmic complexity and discuss Turing machines, the Halting Problem, and NP-completeness.

  • Topics we might cover include Gödel's Incompleteness Theorem and parsing using ANTLR.

The prerequisites are Software Design and Discrete Math.

Textbooks:

We use Sipser's Introduction to the Theory of Computation, 2nd Edition. It costs $130 new, which is ridiculous. On the first day of class, I will make some suggestions for dealing with that.

The optional text is Nagel and Newman, Gödel's Proof, which costs $7, and well worth it!

Course Work: Work in this class includes readings from the textbook and other sources, programming homeworks, pen-and-pencil homeworks, two midterm exams, a final exam, and written quizzes.

The total course load is intended to be 12 hours per week (including class time); the load should be spread evenly across the semester.

Final grades are determined by a weighted average of exam scores, quizzes, homeworks, and an additional factor that reflects my subjective impression of the quality of your work, your progress and effort, and your contribution to the educational goals of the class.

Quizzes: We will have about one quiz per week. The quizzes are intended to help both you and me figure out how things are going. They make up a small part of the final grade. Since there are many quizzes during the year, it is too complicated to try to schedule alternative dates. Instead, I will drop the lowest quiz score at the end of the semester.

Exams: Midterm exams are tentatively scheduled for February 27 and April 2. If there is a problem with either of those dates, please let me know as soon as possible. Both exams will be during a regular class meeting. The final exam will be during the final exam period.

If you miss a midterm for a good reason, your final grade will be based on the other exams. If you miss a midterm without a good reason, you will receive a failing grade. If you miss two midterms or the final for any reason, you cannot pass the class, but you may be able to get an Incomplete, at the discretion of the Dean of Students.

Homeworks: We will have (roughly) weekly homeworks that are meant to give you an opportunity to apply and practice the material we cover in class. Homeworks are graded on a coarse scale: check-plus has the numerical value 10/10; check has the value 8/10; check-minus has the value 6/10.

I believe that these homeworks are most effective if we have an opportunity to discuss them in class shortly after the due date. In order to make that possible, I will have to enforce the due dates with some strictness. Homework that is up to one day late can get a check or lower; homework that is more than one day late can get a check-minus or lower. But late is still much better than never!