All materials in this directory are Copyright © 1987-1995 by Matthew Belmonte. All rights reserved. Please ask for permission.
TEXTS:
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 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 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 Tuesday deadline while keeping up with the theoretical assignments.
Contrary to the glamourous image of computer science (and contrary to the photo in CTY's catalogue), 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.
You'll need a 3.5 inch, double or high density, double sided disk to store your project on. We strongly recommend that you purchase two of these disks and use one of them as a backup; it's possible to lose an entire day of work if your disk becomes damaged and you have no backup copy. (Yes, this has happened.) Disks are available at the bookstore.
CSaW is the text for the theoretical component of the course. It was written specifically for CTY students. One of the advantages of this is that the lectures 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 lecture. The flip-side is that the book sometimes re-hashes explanations and examples covered in lecture instead of presenting alternatives. In addition to the mathematics itself, the book 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.
Class meets for five hours during the day on weekdays, and also for two hours in the evening Sunday through Thursday. We'll also be scheduling optional study sessions in your dormitories at the week-end. In general, we'll begin each morning and afternoon 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.
Historically this course has been a lot of work, even for a CTY course. 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
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, 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.
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
Optional 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
Optional 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 lectures are presented varies somewhat.
You may also wish to view the official CTY Catalogue description of the course, or the TIP C++ version of the course.
