Foundations of Computer Science

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

Class meetings: Monday and Thursday, 10:00-11:50am

For more information, contact allen.downey@olin.edu