All materials in this directory are Copyright © 1987-1998 by Matthew Belmonte. All rights reserved. Please ask for permission.
TEXTS:
This course is meant to introduce you to computer science not only as the practice of computer programming, but also as a branch of mathematics. These are two sides of the same coin, although most introductory courses at the high school level focus on the former and neglect the latter. The fact is that the mathematical bases of computer science were objects of study long before anyone ever designed an electronic computer. The course thus consists of two interrelated components: automata theory and formal systems, and programming.
CST is the text for the programming component. It contains two types of problems: `pauses for reflection', and `exercises'. You are to work independently through this book; we'll do very little lecturing on programming. Try to complete the following readings and problems by the end of study hall on Tuesday of the second week:
| READINGS | PROBLEMS | CONCEPTS |
|---|---|---|
| 1.1 | What is computer science? | |
| 1.2 | What is an algorithm? | |
| 2.1 | syntax and semantics | |
| 2.2 | flow of control | |
| 2.3 | pauses 5-11 | string and numeric literals |
| 2.4 | pauses 12-15 | sequences of function calls |
| 2.5 | pauses 16-24 | parameters |
| 2.6 | pauses 25-31 | multiple parameters |
| 2.7 | style | |
| 3.1 | pauses 2, 3, 4 | input |
| 3.2 | pauses 5-9 | numeric types and arithmetic operators |
| 3.3 | more on types and operators | |
| 3.4 | data abstraction | |
| 3.7 | exercises 2, 4 | |
| 4.1 | assignment | |
| 4.2 | conditionals | |
| 4.3 | relational operators | |
| 4.4 | pauses 1-10 | scope of conditionals |
| 4.5 | pauses 11-16, 19, 20, 22 | return values |
| 4.6 | string functions | |
| 4.8 | exercises 3, 4, 9, 11 | |
| 5.1 | more on data abstraction | |
| 5.2 | pauses 7-11 | iteration |
| 5.3 | pauses 13, 14, 16, 17, 18, 19 | loop development |
| 5.4 | pauses 26, 27, 32 | nested loops |
| 5.5 | scope | |
| 5.6 | alternative statement | |
| 5.8 | exercises 4, 9, 13, 16 | |
| 6.4 | reference parameters | |
| 8.1 | defining vectors | |
| 8.2 | pauses 1-5 | using vectors |
| 9.1 | strings as sequences of characters | |
| 10.1 | recursion | |
| 10.2 | pauses 1-5 | recursion applied |
| 10.3 | relationship of recursion to iteration | |
| 10.4 | more on scope | |
| 10.5 | pauses 6-9 | static allocation |
| 10.7 | exercises 2-5 | |
| 7.3 | enumerated and aggregate types | |
| 12.1 | pauses 1-4 | pointers |
| 12.2 | dynamic allocation | |
| 12.3 | pauses 9-15 | linked lists |
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 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.
Your solutions 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. The `pause' sections should be completed as soon 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 questions on programming. Some of the problems ask you to modify programs that are presented in the book. Don't spend time recopying sections of code from these programs; write just enough to let us know what changes are being made. Try to pace yourself so that you can finish the assignments from CST by the Tuesday deadline while keeping up with the theoretical assignments, but don't worry if you can't make the deadline. As with most of the requirements of this course, it's a guideline only, not an absolute requirement.
Your programs will be written using nothing more high-tech than a pencil and paper; they will not be developed on the computers. Please trust that there is a reason for this. In many years of teaching, I've found that immediate access to a computer is often more of a distraction than an aid to a beginning student. The ability to run a program while it's being written encourages shortcuts. Conversely, writing a program on paper forces you to consider the logic behind each statement that you construct. In the long term, constructing programs methodically and logically, on paper, will make you a better programmer. You will have a chance to use the computers for your term project, but this won't come until the second week of the course. Please be patient.
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.
Because this is an introduction, we have a lot of ground to cover. Many of the topics that we address may at first seem not to be relevant or not to fit together. Please bear with this and give it a chance. As the author of our programming textbook puts it, computer science is a large tapestry and newcomers may at first be overwhelmed with detail. By the end of the course, we feel, you'll be able to step back from this tapestry and to view the scene as a whole with the interactions of all its parts.
So, what specifically are all these mathematical topics that form the theoretical foundations of computer science? We'll start off by studying formal logic, which gives you a method to form statements about the processing of information within computer programs, and to prove theorems about the behaviours of those programs. There are two main ways to ascertain whether or not a program is correct: one is to write it correctly in the first place using logical thinking, and the other is to write it haphazardly and then to test it on some example inputs. Writing programs using logic takes longer in the beginning, but it saves you a lot of time in testing and debugging (not to mention saving you from embarrassment in cases in which your programs might not work as advertised).
We'll also study some methods of representing and describing computer algorithms and their inputs and outputs. One of these methods, the lambda-calculus (no relation to "calculus" as in "calculus and analytic geometry"), specifies computer programs as mappings between mathematical sets. We'll use the lambda-calculus to study the relationship between recursion and looping, two methods of reducing complex problems to simple steps.
Programs can also be viewed as processors of sequences of symbols. We'll study the regular expressions, a system of notation for describing these sequences, and also finite automata, mathematical constructs that process these sequences. Finally, we'll look at some more general models of computation, and at some very interesting classes of problems whose solutions cannot be computed by any computer program.
For a term project, you'll be writing an interpreter for a small programming language. (This may sound daunting, but the details will be explained and you'll have the tools with which to approach this problem.) The first part of this project is a concrete implementation of some concepts from the theory of finite automata. The subsequent parts apply what you'll learn about methods of specifying the structure of sequences of symbols---for a computer program itself is really nothing more than a sequence of symbols.
In general, I'll be starting each morning and afternoon class with a lecture on one of the theoretical topics. 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.
The lecture will occupy a third to a half of the period, and the rest of the time will be used for self-paced study. You are to use the study time to work on reading and problems in CST, doing the theoretical exercises that we assign, and working on your term project. 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.
This self-paced format is the same as that employed in TIP's precalculus mathematics courses: we'll be available to answer questions and to tutor you individually on specific problems and topics. We'll try to check up on all of you and to make sure that you're getting the individual help that you need. During busy times, though, we may not be able to get to everyone as promptly as we'd like. Please don't be shy about approaching us, rather than waiting for us to come to you.
Because there's a self-paced component to this course, I'm giving a lot of assignments. The goal is to include so much work that hardly anyone will be able to complete all of it during the three-week term of the course. This way, everyone in the class will always have something to which to progress, regardless of their background or the rate at which they work. 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. Evaluations are written with the expectation that nobody will finish all the work, and you can get a good evaluation without finishing. What we do expect is that you make an effort to address at least a few problems from most of the topics that we cover. Try for a wide breadth, not a narrow depth. 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.
WEEK 1, DAY 1
Morning-- What is an algorithm? Syntax versus semantics. A simple production
system. A formal algorithm for binary addition. Relationship between programs
and formal proofs. Program verification as distinct from testing.
Afternoon-- Basic set theory: union, intersection, complement, difference,
Cartesian product, power set. Relations and functions: one-to-one versus
many-one; total versus partial. Parameter passing and flow of control in a
computer program. Relationship between type specifiers in a program and sets
in a mathematical description. An introduction to the lambda-calculus.
Assignment: sets handout.
WEEK 1, DAY 2
Morning-- The propositional calculus, a tool for proving programs correct:
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.
WEEK 1, DAY 3
Morning-- Symbols, 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. Programs as processors of
formal languages. Assignment: CSaW page 89: all.
Afternoon-- Deterministic finite automata: simple programs for processing
strings of symbols. 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.
WEEK 1, DAY 4
Morning-- The predicate calculus: extending the propositional calculus to make
assertions about different variables. Predicates, quantifiers, inference
rules, and proofs. Assignment: CSaW pages 67-68: all.
Afternoon-- Programs that mimic other programs: simultaneous simulation of
deterministic finite automata. Closure properties of deterministic finite
automata. Assignment: DFA Languages handout.
*** CST ASSIGNMENT THROUGH SECTION 5.2 DUE
WEEK 1, DAY 5
Loops and invariants in C++: solving complex problems by reducing them to
iterations of simple cases. 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. Introduction to the term project and
guidelines for implementation using C++. Assignment:
lexical scanner.
WEEK 2, DAY 1
Morning-- Programming in a nondeterministic environment: nondeterministic
finite automata, with and without 
-moves.
Assignment: CSaW page 110: 8,9.
Afternoon-- The Subset Construction, with and without -CLOSURE.
Assignment: NFA handout; CSaW page 110: 10.
WEEK 2, DAY 2
Morning-- 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. C++ as a compiled language.
Afternoon-- Equivalence of recursion and iteration. Implementation of a
generalised looping function in the lambda-calculus.
*** CST ENTIRE ASSIGNMENT DUE
WEEK 2, DAY 3
Morning-- Recursive-descent parsing: an example using C++.
Assignment: parser
Afternoon-- Equivalence of program states, and an application to minimisation
of finite automata. Assignment:
CSaW page 110: 11.
WEEK 2, DAY 4
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. Regular expressions as
a notation for the sets computed by the lexical scanner.
Afternoon-- Semantics of programming languages: imperative and functional
languages, eager and lazy evaluation, strong typing, strictness. Description
of C++ in terms of these formal properties. Use of lazy evaluation in infinite
data structures and in cases of undefined parameters.
WEEK 2, DAY 5
Morning-- Evaluation of parse trees: an example.
Assignment: evaluator.
Afternoon-- Sizes of infinite sets of data: not all infinities are equal.
Countability proofs for the integers and the rationals. Uncountability of the
reals by Cantor diagonalisation.
WEEK 3, DAY 1
Morning-- The Peano Axioms for the natural numbers. Addition and
multiplication. Proofs.
Afternoon-- Structured sets: partial orderings and well-foundedness.
Assignment: CSaW pages 72, 76: all.
WEEK 3, DAY 2
Morning-- The Turing Machine: a simple model of a general computing system.
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.
WEEK 3, DAY 3
Morning-- Random Access Machines and their equivalance to Turing Machines. The
Church-Turing Thesis on general computability.
Afternoon-- Introduction to the theory of computability: sets that cannot be
computed and problems that cannot be solved by computing devices. Recursive,
recursively enumerable, and complementary recursively enumerable sets. The
Halting Problem and undecidability.
WEEK 3, DAY 4
Morning-- The Incompleteness Theorem (demonstrated using enumeration machines,
details glossed over).
Afternoon-- Sorting and algorithmic complexity. (CST 11.1-11.6 optional.)
WEEK 3, DAY 5
Time to finish term projects, and optional lectures on current topics in
computer science.
The order in which lectures are presented varies somewhat.
| FRONT | BACK |
|---|---|
 |  |
