Syllabus |
Foundations of Computer Science (FOCS) cover topics in Programming Languages, Automata, Analysis of Algorithms, and Theory of Computation.
We will start the semester with a survey of programming paradigms, including an introduction to functional programming in Scheme and logic programming in Prolog.
We will 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 will review algorithmic complexity and discuss Turing machines, the Halting Problem, and NP-completeness.
The prerequisite is Software Design or equivalent experience.
Work in this class will include 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.
If you miss a midterm for an extremely legitimate reason, your final grade will be based on the other exams. If you miss a midterm without a legitimate 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.
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!
The easiest way to reach me is by email; I read my mail fairly often, even in the evening and on weekends. I try to answer email promptly, but occasionally fall behind and drop the ball. If an email goes unanswered, please give me another chance. You are also welcome to call me at x2558 any time, or at home during normal waking hours.
If I am in my office and my door is open, you are welcome to come in and talk to me. If I can't meet with you, I will let you know, and schedule a meeting for later. When I know my schedule for the semester, I will make it available.
You are encouraged to communicate with the other members of the class using whatever means you choose, including the class mailing list. You can join the mailing list (and change your membership configuration) at http://lists.olin.edu/mailman/listinfo/focs. It is appropriate to use this mailing list to discuss anything pertaining to the class, or to the topic of the class, broadly defined.
Some of the coursework you will do this semester is intended to help you develop understanding of the material, and some is intended to allow me to evaluate your understanding. While you are developing your understanding, you are encouraged to work with other students, but when you are being evaluated you will have to work alone unless you have explicit instructions otherwise.
As always, your actions in this class are bound by the Honor Code; in particular, the principle of integrity states, “Each member of the college community will accept responsibility for and represent accurately and completely oneself, one's work, and one's actions.” When you submit course work for evaluation, you are representing that the work is entirely yours, unless you state otherwise. Representing someone else's work as your own is a very serious violation of the Honor Code.
The following are the topics we will be covering, roughly in the order we will be covering them:
This document was translated from LATEX by HEVEA.