\documentclass[12pt,twoside]{article}
\addtolength{\topmargin}{-1in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

\input{macros-course}

%%\usepackage{hyperref}

\newcommand{\week}[2]{\subsection*{Week #1}#2}
\newcommand{\topics}{{\bf Topics: }}
\newcommand{\readings}{{\bf Reading: }}
\newcommand{\opread}{\emph{optional/supplementary: }}
\newcommand{\tutorial}{{\bf Tutorial: }}
\newcommand{\assignment}{{\bf Assignment: }}
\newcommand{\lecture}{{\bf For Lecture: }}
\newcommand{\finger}{{\bf Finger Exercises: }}
\newcommand{\revise}{\textbf{Revisions: }}

\begin{document}
\handout{curriculum}{Staff Curriculum}{Sept. 2, 2001}

\week{1: Wed 9/5--Fri 9/7}{Basic Logic \& Math}

\topics

Basics: \emph{Logical concepts \& notation} $\smand, \smor, \neg,
\forall, \implies, \exists$, truth tables.  \emph{Set notation}
$\union, \intersect, \emptyset, \subset$, complement, power set.
\emph{Functions}: domain, range, injection, surjection, bijection,
composition, pointwise ops.  \emph{Standard sets}: Booleans, Natural
numbers, Strings

Proofs methods: contradiction, cases, contrapositive, subproofs and
lemmas, quantifier rules.

\lecture
Course Overview:
What we want them to learn this term:
    1. Basic discrete math concepts (data types and structures, properties)
    2. Proofs 
    3. Math foundation for software engineering (6170)
    4. Analysis methods for algorithms (6046)
    5. Discrete probability (6046? 6033?)

Administrivia.

Friday lect 2: go over finger exercises; express ``injective''
``surjective'' ``exactly 2'' $A = B \oplus C$ in 1st-order logic.

\readings
Karger Lectures 1-2; 5.1 \opread Rosen 1.1-1.5, 3.1; Vellemen Ch.1-3

\revise insert Lect 5.1 into 1.3.4 as sos

\finger (for Friday Sept. 7)
Rosen, 1.1.8a,d,e,f; %truth table
1.3.10b,d; %quantifiers
1.5.4. %set ops
Vellemen, 2.1.4a,b,c; %quantifiers
2.3.7. %set ops, powerset

\tutorial
False proofs from Karger tut1 \& S99 handout 4

\assignment
PS1. probs from R \& V3.7.7?  logical notation, proof theory

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\week{2: Mon 9/10--Thur 9/13}{Induction} %2

\topics

Inductive proofs.  Strong induction.  Structural induction.  Least
Number Principle.

Present the basic idea of (ordinary) induction over the natural numbers.
Examples using the basic data types: Sums of series, strings of length

recursive examples: binary trees, boolean expressions, matched parens,
lists, string w/= 0's and 1's, recursive functions.  [f(n,m) = f(n-1, f(n,
m-1))] false induction principle [n+1 implies n]


\readings Karger Lecture 3, (Skim-or-skip 2.3,2.5,4.3,
5).  Karger Lecture 4 revise def 3.1-4 (change 3.4 into real lists)
interact w/thm 3.6, slightly def 3.3 sos 2.2

\revise \S 4.5: elaborate block tower false proof, delete false thm 4.5;
\S 6.)

\tutorial

\assignment double induction, well-ordering?

% Structural induction
%   Recursive definition of some basic data types.
%     E.g., nat using 0 and successor    
%     E.g., arbitrary strings built up from empty string using concat-with-atom
%     E.g., well-formed strings of left and right parens built up
%       from empty string, wrapping parens around, concat.
%   Inductive proofs about the domains based on this structure
%     Examples?
%       For paren strings, prove that for any prefix, number of
%         preceding l parens is geq number of preceding r parens
%       Define a function on general strings by recursion, prove it satisfies
%         some property.
%       For nat, 0, succ, just reduces to ordinary induction.
%       Invent some new kind of ``blob'' data type, prove something
%         about it.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\week{3: Wed 9/19--Thurs 9/20}{Relations, Equivalence}

\topics

Binary Relations: \emph{Properties:} reflexivity, symmetry,
antisymmetry, transitivity \emph{Representation:} lists, PREDICATES?,
matrices, digraphs, how to recognize properties \emph{Operations:}
inverse, composition (matrix composition and paths of length n),
closures (symmetric, reflexive, transitive closures, computing
transitive closure) \emph{Examples:} divisibility, paths of length n
and transitive closure (examples in vellemen pg 196 and rosen of
nonstop buses and state borders, where can you get to in n hops or how
many state borders do you cross from state A to B?)

K-ary relations?? No notes, sparse information in Rosen
6.2. Potentially a Database example.

Equivalence relations and partitions. Example: Modular artithmentic
and fast exponentiation application. Other Kinds of relations next
week: partial order, total order.

% Transitive closure. A theorem about it?  CORRESPONDENCE BETW DIGRAPHS AND
% BINARY RELATIONS \& binary and nonnegative integer matrices (boolean and
% min/max matrix product vs paths in graph)

\lecture Short week, only one lecture. Finger exercises due beginning
tutorial and are sufficient for tutorial background. Should do path
length / transitivity example in class to prepare for tutorial.

\readings Lecture Notes 5 (skim-or-skip 5.1), 6.1 \opread Vellemen 4.2
4.3, Rosen 6.1--6.4.

\revise Would be nice to add a motivating example for transitive
closure/path lengths from velleman or rosen. More ambitiously a
section on k-ary relations and relational databases.

\finger Rosen 6.1.3 (a,b,c) (properties), 6.3.7 (matrix and ops),
6.5.2 (abe) (equivalence). Need to set up some collection mechanism
for NAME+AGE+HEIGHT for next week demo?

\tutorial 1) False Proof on relation properties, 2) Equivalence
relation problem 3) Composition of relation matrices

\assignment Pset3, Practice problems, Determining properties after
composition of relations, equivalence of similar triangles and problem
on transitive closure.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\week{4: Mon 9/24--Fri 9/28}{Partial Orders, Digraphs, Graphs.}

\topics 

Partial Orders. (reflexive, transitive and antisymmetric),
poset. Kinds of relations: partial order, total order,
equivalence. \emph{DAGs:} dependency graph->partial order, no cycles,
hasse diagrams \emph{Topological Sorting:} construction, minimal
element, \emph{Parallel Task Scheduling:} chains, antichains and
Dilworth. Examples: dictionary/lexicographical sorting, class prereqs,
chains of students by height/age or countries by population/size.

Graphs. types, degree theorems, \emph{Graph Coloring:} conflicts
chromatic number, greedy algorithm for delta+1 colors, examples: final
exam (notes) or airline gates assignment (make up)
\emph{Connectivity:} connectedness as equivalence relation, connected
components, Cuts, several theorems (with inductive proofs).

Other graph topics, might spill into next week: Euler Tours and
Circuits, Hamiltonian path, Weighted graphs, Spanning Trees, Bipartite
graphs, Adjacency matrices (path lengths)

\lecture Class demo: 15 students decreasing age increasing
height. Question: what is the real dilworth theorem?  \textbf{NOTE:
QUIZ 1 on FRIDAY}

\readings Lecture notes 6.2, 

\revise add GRAPH ISOMORPHISM section back from leighton lectures

\finger Velleman 4.4.1 (partial/total order)

\tutorial From Karger tutorial 4 1) Scheduling class prereqs (chains,
antichains) 2) Simple graph false proofs (uses graph isomorphism) 3)
Graph coloring (graph is 2 colorable iff) \emph{removed dilworth
example assuming that will cover it in class}

\assignment 

Friday: QUIZ 1 covers weeks 1-3

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\week{5: Mon 10/1--Thur 10/4}{Graphs, Trees}
\topics 

Tree theory: 
  Three equivalent characterizations
  Recursive definition of trees.
  Proving properties of trees by structural induction.
  Counting stuff about trees

taxonomony: rooted, ordered, labelled
leaves, internal nodes, height
characterization: unique paths and connected, 
minimal connected (for finite case), etc.
branching model: weighings, searching, prefix codes.
spanning trees? game trees.

\reading Karger Lecture 7.4, 13.3.2-3, 14.3; Rosen

\tutorial

\assignment 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\week{6: Wed 10/10--Thur10/11}{Computational Processes}
\topics

The idea of a computational process (algorithm, abstract system
description) as a process that moves from state to state following
some rules, with possible nondeterminism.

State machine model for algorithm.

Toy examples:
  Die Hard, 2-dimensional version (good because they are
    nondeterministic)
  Something with parity of number of inversions?
  A queue, where things magically get added on at the end and
    removed from the beginning.

Simple iterative programs and how they denote state machines
  (informal).

Example algorithms, using the basic data types.
E.g.:
  For natural numbers:  Euclidean GCD
  For relations:  Transitive closure by successive doubling
  For trees:  Counting notes, returning the total
  For graphs: Depth-first search, enumerating the notes
Talk about them as iterative programs, state machines.
Might state some interesting properties, but don't try to prove them yet.

Simple recursive programs and how they denote state machines (needs
  stack, informal).

Might want to introduce stacks here as another data type.
Give its operations, basic properties, can prove something about them.
Do NOT define them axiomatically, but as set-theoretic objects
  (abstract finite sequences, accessible only by push, empty?, pop
  (formulated as a total operation, some default for the empty stack)).
Can prove something about stacks, but just say informally how a
  stack can be used within a state machine to do the bookkeeping for
  recursive calls.

Invariant assertion proofs.
Invariants, proof by induction.
The main Invariant Theorem (so we can avoid using induction each
 time.)

Examples
 Revisit some of the ones already done, state and prove their
   invariants formally.

Proofs about iterative algorithms (Rosen, new notes)
 Annotating a program with invariants.
 Loop invariants, Hoare triples. 

Examples

\readings Lecture Notes ?

Lecture 8:

Proofs about processes:  Termination, step bounds. 
Process behavior.

Termination proofs, based on some kind of well-founded order theorem.

A bounded version of this, counting steps.
[[[Step counting makes sense as a time measure if we're talking
 about a sequential process for which all steps are locally controlled.
 It is too special for a general setting that allows interaction,
 inputs, concurrency.]]]

Examples of termination and step bound proofs. 

Actions labelling transitions.
How external (input and output) give rise to mathematically
 describable visible external behavior.

Examples:  
 A send/receive queue, send adds to end, receive removes.

Object models

Examples:
 A simple object model, intended for sequential invocations.
 E.g., an object of type integer, with inputs that are invocations of
   increment/decrement/value?, outputs that are responses saying
   OK/current-val.
 Describe this as a state machine whose state maintains the value
   of the integer, plus some bookkeeping to keep track of current
   operation.
   (Assume invocation that arrives at incorrect time is ignored.)

Introduce anything with concurrent invocations, nondeterminism?

\readings Lecture Notes ?

\tutorial

\assignment Pset X due, Pset Y out

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\week{7}
\topics
\readings Lecture Notes ?
\tutorial
\assignment Pset X due, Pset Y out

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\week{8}
\topics
\readings Lecture Notes ?
\tutorial
\assignment Pset X due, Pset Y out

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\week{9}
\topics
\readings Lecture Notes ?
\tutorial
\assignment Pset X due, Pset Y out

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\week{10}
\topics
\readings Lecture Notes ?
\tutorial
\assignment Pset X due, Pset Y out

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\week{11}
\topics
\readings Lecture Notes ?
\tutorial
\assignment Pset X due, Pset Y out

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\week{12}
\topics
\readings Lecture Notes ?
\tutorial
\assignment Pset X due, Pset Y out

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\week{13}
\topics
\readings Lecture Notes ?
\tutorial
\assignment Pset X due, Pset Y out

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\week{14}
\topics
\readings Lecture Notes ?
\tutorial
\assignment Pset X due, Pset Y out

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\week{15}
\topics
\readings Lecture Notes ?
\tutorial
\assignment Pset X due

\end{document}
