Theoretical Foundations of Computer Science

All materials in this directory are Copyright © 1987-1999 by Matthew Belmonte. All rights reserved. Please ask for permission.

CONTACT: cs-staff@mattababy.org

TEXT: Ferguson, Martin, & Kaufman, The Schemer's Guide, 2/e. Schemers Incorporated, 1995. (See errata.)

LOCATION: Saturdays 10am-noon and 1pm-3pm, MIT room 26-328. Optional study session 3pm-5pm in W20 fifth floor.

This course is meant to introduce you to computer science not as the mundane activity of computer programming, but as a branch of mathematics. If you have studied `computer science' in high school, you're about to experience something rather different. If you've never studied high school computer science, maybe you're better off.

The course consists of two interrelated components: automata theory and formal systems, and programming. tSG is the text for the programming component. It contains two types of problems: `exercises', and `problem sets'. You are to work independently through this book; we'll do very little lecturing on programming. You are to complete the following readings and problems by Saturday 10 April:

READINGS	PROBLEMS
1.1, 1.2	all exercises, and all of problem set 1
1.3     	all exercises, and all of problem set 2
2.1,2.2,2.3,2.4	all exercises, and all of problem sets 3 and 4
3.1     	all exercises, and problem set 5: 1-10, 15, 16
4.1, 4.2	all exercises, and problem set 8: 1, 2
4.3     	all exercises

If you have a computer at home, you may wish to download MIT Scheme so that you can try running some of the programs that you write. (We will also provide access to computers here at MIT to use in your programming project.)

Your solutions to all the problems, and also the exercises for section 4.3, are to be submitted to us for evaluation. Hand them in singly or a few at a time; you should allow enough time for us to correct them and discuss any errors or ambiguities with you before you've moved on to the next sections. For exercises from sections other than 4.3, we'll supply you with answers so that you can correct them on your own. The exercises should be completed as you encounter them in the text; don't wait until you reach the end of the section. Try to think through them on your own, but if you find yourself up against a wall, do ask us; we expect some questions on programming. Pace yourself so that you can finish the assignments from tSG by the deadline while keeping up with the theoretical assignments.

Contrary to the glamourous image of computer science, good mathematicians do most of their work using nothing more high-tech than a pencil and paper. In fact it'll be quite some time before you reach the stage at which typing at a computer will be a beneficial use of your time. Be patient.

tSG uses colour coding to distinguish expressions that are slated for evaluation from expressions that will not be evaluated. If you find this distinction useful, you may wish to purchase a red pencil for use in your assignments.

In general, we'll begin each class period with a lecture and leave the rest for study time, during which we'll be available for individual instruction. You are to use the study time to work on reading and problems in tSG, doing the theoretical exercises that we assign, and working on your final project. IF YOU DON'T UNDERSTAND SOMETHING DURING A LECTURE, STOP ME AND ASK A QUESTION! In the long run, it'll take less time for all of us. I'm far from infallible in my explanations, and if you aren't understanding something, chances are that there are other people who aren't understanding. FOR EACH SET OF THEORY EXERCISES, YOU SHOULD TRY A FEW OF THE EXERCISES ON THE SAME DAY AS THE RELEVANT LECTURE, WHILE THE INFORMATION IS STILL FRESH IN YOUR MIND.

Many of your assignments will come back marked `Redo'. When you receive this annotation, look at the comments we've made on your attempted solution, and understand your mistake. If our written comments fail to make your mistake clear to you, ask us about it. When you understand the error and how to fix it, submit a revised version to us, clipped or stapled to the original.

This course is a lot of work, especially since it's occurring in parallel with your high school classes. You are not expected to complete all the assignments during the term of this course. You may find some people who move faster than you do, and some who move more slowly. This is okay. Your goal should be simply to learn as much from the course as you can. Some exercises are more difficult than others; think about the more difficult problems, but don't spend so much time on them that you fall behind on other assignments. There is such a thing as an optimal level of stress, and while we aim to stress you enough to learn a lot, we don't want to load you down with so much that you begin to feel inadequate to the task. If you begin to feel this way, please speak with us and with your parents.

We hope that this document answers most of your general questions about the course. We welcome your further queries.

Approximate Schedule of Topics

Saturday 27 February
Registration day.

Saturday 6 March
Morning-- Introduction. Binary numeration. A formal algorithm for binary addition. Syntax versus semantics. View of problems as questions of language membership. A simple production system. Invariant relations and their use in formal proofs.
Afternoon-- Basic set theory: union, intersection, complement, difference, Cartesian product, power set. Relations and functions: one-to-one versus many-one; total versus partial. Sets as types. An introduction to the lambda-calculus. Assignment: sets handout.

Saturday 13 March
Morning-- Syntax and semantics of the propositional calculus: conjunction and negation, decomposition trees and a context-free grammar, inference rules and proofs. Assignment: CSaW page 40: 0-9; page 46: 0,2,5.
Afternoon-- Disjunction and implication, and associated inference rules and proofs. Assignment: CSaW page 46: 1,3,4,6-11.

Saturday 20 March
Morning-- Alphabets, languages, and regular expressions. Regular expressions defined in terms of set operations: union, concatenation, Kleene closure, and positive closure. Construction of regular expressions from English-language descriptions of strings, and vice versa. Assignment: CSaW page 89: all.
Afternoon-- Formal mathematical definition of deterministic finite automata. State diagrams and transition tables. Automata viewed as decision algorithms for language membership. Construction of automata from English-language descriptions and from regular expressions. Assignment: CSaW pages 98-99: all.

Saturday 27 March
*** tSG PROBLEM SETS 1, 2, and 3 DUE
Morning-- Simultaneous simulation of deterministic finite automata. Closure properties of deterministic finite automata. Assignment: DFA Languages handout.
Afternoon-- Nondeterministic finite automata, with and without -moves. Assignment: CSaW page 110: 8,9.

Saturday 3 April
Morning-- Equivalence of recursion and iteration. Implementation of a generalised looping function in the lambda-calculus. Program correctness for iterative algorithms. Development of a loop from an invariant. The invariant as a compromise between precondition and postcondition. Guards and bound functions.
Afternoon-- Lexical scanners as concrete implementation of a finite automaton. An example of lexical scanning. Assignment: lexical scanner.

Saturday 10 April
*** tSG ENTIRE ASSIGNMENT DUE
Morning-- Compilers as mappings between languages. Recursive-descent parsing. Assignment: parser
Afternoon-- The predicate calculus: predicates, quantifiers, inference rules, and proofs. Assignment: CSaW pages 67-68: all.

Saturday 17 April
Morning-- Evaluation of parse trees: an example. Assignment: evaluator.
Afternoon-- Mathematical induction.

Saturday 24 April
Morning-- The Peano Axioms for the natural numbers. Addition and multiplication. Proofs.
Afternoon-- Infinite sets and a generalised notion of cardinality. Countability proofs for the integers and the rationals. Uncountability of the reals by Cantor diagonalisation.

Saturday 1 May
Morning-- Turing Machines. Construction of a Turing Machine that accepts a non-regular language.
Afternoon-- Extensions to Turing Machines: multiple tracks, multiple tapes, two-way infinite tapes, multi-dimensional tapes, nondeterminism. Computational equivalence of all these extensions to the basic Turing Machine.

Saturday 8 May
Morning-- Random Access Machines and their equivalance to Turing Machines. The Church-Turing Thesis on general computability.
Afternoon-- Recursive, recursively enumerable, and complementary recursively enumerable sets. The Halting Problem and undecidability. An overview of the Incompleteness Theorem.

The order in which lectures are presented may vary somewhat.

You may also wish to view the TIP C++ version of the course.