All materials in this directory are Copyright © 1987-1999 by Matthew Belmonte. All rights reserved. Please ask for permission.
A computer program is an example of what mathematicians call a `formal system' -- a set of rules for manipulating sequences of symbols according to their syntactic form. Lectures and group activities will address several formal systems and mathematical models of computers. These theoretical topics will be applied in self-paced work in computer programming using the Scheme language. Focusing on the logic behind program development, students initially will develop solutions using only pencil and paper. Building on preliminary work in the programming text, students will have the opportunity to implement an extensive programming project consisting of an interpreter for a small programming language. During the latter half of the course, electronic computers will be used intensively for debugging this project.
TEXTS:
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 the end of study hall on Tuesday of the second week:
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
Your solutions to all the problem sets, 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 Tuesday deadline while keeping up with the theoretical assignments.
Although popular culture inevitably associates computer science with today's high-speed electronic computers, computer science as a mathematical discipline existed long before the invention of the transistor. And it's still the case that most advances in algorithmic design are accomplished 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.
CSaW is the text for the theoretical component of the course. It was written specifically for talented high school students. One of the advantages of this targeted design is that the class discussions follow the text very closely, so you have something besides your own notes to which to refer on occasions when you haven't fully understood a topic. The flip side is that the book sometimes re-hashes explanations and examples covered in class instead of presenting alternatives &emdash; if you need supplementary examples, please don't be afraid to ask for them. In addition to the mathematics itself, CSaW discusses the history and philosophy of computer science. These discussions won't be included in this course, but you're welcome to read them if these topics interest you and if you have time.
In general, we'll begin each morning and afternoon class period with a lecture and group activity 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 term 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 in the same situation. For each set of theory exercises, you should try a few of the exercises on the same day that the topic is discussed in class, while the information is still fresh in your mind. Don't expect to finish all the problems in a particular theoretical assignment before moving on to the next.
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 involves a very large amount of work, even for TIP students. Most of you won't be able to complete all the assignments during the three-week term. 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, or with your RA.
We hope that this document answers most of your general questions about the course. We welcome your further queries.
DAY 1
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
notation of the lambda-calculus. Assignment: sets handout.
DAY 2
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.
DAY 3
Morning-- Alphabets, languages, and regular expressions. Regular expressions
defined in terms of set operations: union, concatenation, Kleene 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.
DAY 4
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.
*** tSG PROBLEM SETS 1, 2, and 3 DUE
DAY 5
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.
DAY 6
Review, tutorials, and self-paced study.
DAY 7
Optional self-paced study.
DAY 8
Morning-- The Subset Construction, with and without -CLOSURE.
Assignment: NFA handout; CSaW page 110: 10.
Afternoon-- Compilers as mappings between languages. Scanning and parsing.
Code generation as a process of tree decoration. Intermediate code. A brief
overview of optimisation strategies: peephole optimisation, constant folding,
common subexpression elimination, code motion, reduction in strength, dataflow
analysis, vectorisation, and others. Front ends and back ends. Interpreters
versus compilers.
DAY 9
Morning-- Recursive-descent parsing: an example.
Assignment: parser
Afternoon-- Minimisation of finite automata.
Assignment: CSaW page 110: 11.
*** tSG ENTIRE ASSIGNMENT DUE
DAY 10
Morning-- Formal construction of finite automata from regular expressions and
of regular expressions from finite automata (Hopcroft's R(i,j,k)
construction); equivalence of these two formalisms.
Afternoon-- Semantics of programming languages: imperative and functional
languages, eager and lazy evaluation, strong typing, strictness. Use of lazy
evaluation in infinite data structures and in cases of undefined parameters.
DAY 11
Morning-- The predicate calculus: predicates, quantifiers, inference rules, and
proofs. Assignment: CSaW pages 67-68: all.
Afternoon-- Mathematical induction.
DAY 12
Morning-- Evaluation of parse trees: an example.
Assignment: evaluator.
Afternoon-- Infinite sets and a generalised notion of cardinality.
Countability proofs for the integers and the rationals. Uncountability of the
reals by Cantor diagonalisation.
DAY 13
Review, tutorials, and self-paced study.
DAY 14
Optional self-paced study.
DAY 15
Morning-- The Peano Axioms for the natural numbers. Addition and
multiplication. Proofs.
Afternoon-- Partial orderings and well-foundedness.
Assignment: CSaW pages 72, 76: all.
DAY 16
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.
DAY 17
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.
DAY 18
Morning-- The Incompleteness Theorem (demonstrated using enumeration machines,
details glossed over).
Afternoon-- Sorting and algorithmic complexity.
DAY 19
Optional lectures on current topics in computer science, or self-paced study.
The order in which discussions occur may vary somewhat from term to term.
You may also wish to view the C++ version of the course.
