\documentclass[12pt,twoside]{article}

\addtolength{\topmargin}{-1in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

\raggedbottom

\input{macros-course}

\long\def\ignore#1{}

\newcounter{lecnum}
%       USAGE:  `` \begin{lecture}{topic}{handouts} ''
\newenvironment{lecture}[2]{\stepcounter{lecnum}
        \parbox[t]{1in}{\raggedright
        Lecture \thelecnum :\\
                \hspace*{.1in} 
                \parbox[t]{.9in}{\footnotesize \raggedright 
                        #1} \\
        \vskip .1in  #2  \vskip .1in} }{}
\newenvironment{tutorial}[1]{
        \parbox[t]{1in}{\vspace{.1in} Tutorial #1}}{}
\newenvironment{recitation}[1]{
        \parbox[t]{1in}{\vspace{.1in} Recitation #1}}{}
\newenvironment{noclass}[1]{
        \parbox[t]{1in}{\vspace{.1in}\raggedright \bf #1}}{}

\newcommand{\mo}[1]{\llap{#1 \hspace{7pt}}\vspace*{-14pt}}
\newcommand{\week}{\begin{tabular}{|p{1in}|p{1in}|p{1in}|p{1in}|p{1in}|}\hline}
\newcommand{\eweek}{\\ \hline\end{tabular}}
\newcommand{\heightstrut}{\rule[-1in]{0in}{.75in}}

%       USAGE:  ``\weekoff{monthname}{..5 dates..}{title}''
\newcommand{\weekoff}[7]{\begin{tabular}{|p{1in}p{1in}p{1in}p{1in}p{1in}|}
        \hline
        #2 \hspace*{-.8in} #1 & 
        #3 \heightstrut & 
        #4      \parbox[t]{4in}{\vspace{.1in} \Large #7}
        & #5 & #6
        \rule[-1in]{0in}{1in} \\
        \hline
        \end{tabular}}


%       ABBREVIATIONS:
%\newcommand{\lec}[1]{\begin{lecture}{#1} \end{lecture}}
\newcommand{\tut}[1]{\begin{tutorial}{#1} \end{tutorial}}
\newcommand{\rec}[1]{\begin{recitation}{#1} \end{recitation}}
\newcommand{\dayoff}[1]{\begin{noclass}{#1} \end{noclass}}

%       OLD VERSIONS:
\newcommand{\lec}[2]{\begin{lecture}{#1}{#2} \end{lecture}}
% \newcommand{\recitation[1]}{\parbox[t]{1in}{\vspace{.1in} \sf Recitation.}}
% \newcommand{\week}{\begin{tabular}{|p{1in}|p{1in}|p{1in}|p{1in}|p{1in}|}\hline}

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

\begin{document}
\handout{course-calendar}{Course Calendar}{September 7, 2000}

\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\week

Monday & Tuesday & Wednesday & Thursday & Friday

\eweek

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      WEEK 1
\week

\mo{Sept}

4  \dayoff{Labor Day} &

5  \dayoff{Registration Day} &

6  &

7  \lec{Course overview.  Basic data types.  Basic proof methods. }{\textbf{PS1 out.}} & % Nancy

%  Overview:  
%    Administrivia.  
%    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?)
%  
%  Basic data types (informally):  definitions, operations, very basic
%  properties
%    Booleans
%      0, 1, and, or, not; simple Boolean algebra rules
%    Natural numbers, integers
%      0, +, -, times, integer div, mod, exp
%    Strings 
%      empty string, concat
%    Sets
%      emptyset, universal set, union, intersection, complement,
%      subset, proper subset
%    Functions 
%      domain, range
%      Composition
%      Pointwise ops (e.g., add, for functions whose range is integers)
%
%  Basic proof methods:  
%    Logical notation 
%    Propositional reasoning (truth tables)
%    Predicate calculus reasoning (incl. quantifiers)   
%    Basic proof methods (no induction yet)
%      Contrapositive
%      Cases
%      Contradiction
%
%  Examples of proofs using the basic data types
%    In structured form, making the proof rules explicit

8  \tut{1} 
\eweek

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      WEEK 2
\week
\mo{Sept}

11 &

12 \lec{Predicates and quantifiers. Induction.}{\textbf{PS1 due. \\ PS2 out.}} & % Nancy

%  Present the basic idea of (ordinary) induction over the natural numbers.
%
%  Examples using the basic data types.
%    Sums of series
%    Can make any amount of change
%    Number of subsets of a set of size n?
%    Number of strings of length n, of Booleans?
%  Try to use all the data types we've defined.

13 &

14 \lec{Inductive proofs. \\Strong Induction.}{} & % Nancy

%  More basic inductive proofs.
%    Induction with several base cases.
%
%  Strong induction
%    Mention equivalence of induction and strong induction, don't do
%      proof.
%  Well-ordering, also equivalent
%
%  Examples using the basic data types.
%    
%  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.

15 \tut{2}

%  Review the basic data types, do lots of proofs about them.

\eweek

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      WEEK 3
\week
\mo{Sept}

18 &

19 \lec{Structural induction. \\Set theory.}
{\textbf{PS2 due. \\ PS3 out.}} & % Shlomi

%  Binary relations
%  
%  Examples, involving real life, the basic data types, and computer science.
%    File is-in directory
%    Nat, less than
%    Network machines, directly-connected-to, directly-or-indirectly-connected-to
%    Entity-relationship diagrams

%  Properties: reflexivity, symmetry, antisymmetry, transitivity
%  Kinds of relations:  partial order, total order, equivalence
%  relation
%
%  Some basic properties and proofs.
%
%  Transitive closure.
%    A theorem about it?  Connected iff connected by path of length n?  
%
%  k-ary relations
%
%  Examples:
%    Relational db example

20 & 

% [[[I've not included any particular material on number theory, prime
% factorizations, modular arithmetic...just whatever seems to be
% needed for whatever proofs or algorithms we decide to use as examples.]]]

21  \lec{Relations.}{} & % Shlomi

22  \tut{3} 

% Fancy induction, relations

\eweek

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      WEEK 4
\week
\mo{Sept}

25  & 

26  \lec{Digraphs, graphs, and trees.  }{\textbf{PS3 due. \\ PS4 out.}} &
% Shlomi

%  Definitions.
%    As special kinds of relations.
%
%  Digraph theory
%    ???
%
%  Graph theory
%    Cute stuff: circuits, coloring
%
%  Tree theory: 
%    Three equivalent characterizations
%    Recursive definition of trees.
%    Proving properties of trees by structural induction.
%    Counting stuff about trees

27  &

28  \lec{Digraphs, graphs, and trees. }{\textbf{}} &
% Nancy

29 \tut{4}

\eweek

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      WEEK 5
\week 
\mo{Oct}

2 \dayoff{} &

3 \lec{Computational processes. Proofs about processes: Invariants.}{\textbf{PS4 due. \\ PS5 out.}} & % Nancy

%  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.
%
%
% 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

4 &

5 \lec{Proofs about processes:  Termination, step bounds. 
Process behavior.  }{} & % Nancy

% 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?]]]


6 \tut{5} \dayoff{Add date}

% Invariant assertion proofs.

\eweek

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      WEEK 6
\week
\mo{Oct}

9 \dayoff{Columbus Day holiday} &

10 \dayoff{Columbus Day holiday} &

11 &

12 \lec{Process structure.  Abstraction.  Composition.}{\textbf{PS5 due.}} &
% Nancy

% Levels of abstraction
%   Implementation of one process by another
%   Application to object subtyping 
%   
% Examples:
%
% Composition
%   Pasting and projection theorems
%
% Examples:
%   Combining node and channel?
%   Application invoking object
%
% Transition to next unit (maybe at beginning of Lecture 10):
%
% Proofs about recursive algorithms
%   Using structural induction to prove correctness?
%   Using recurrences for proving complexity bounds.

13   \tut{6} 
\eweek

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      WEEK 7
\week
\mo{Oct}

16 &

17 \lec{Series.  Summations.  Products. }{\textbf{PS6 out.}} & % Shlomi

18 \dayoff{QUIZ 1: Lectures 1-10} & 

19 \lec{Estimation.  Asymptotics.  Stirling's formula.  Recurrences.}{} &
% Shlomi

20 \tut{7}

\eweek

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      WEEK 8
\week
\mo{Oct}

23  &

24 \lec{Recurrences.   }{\textbf{PS6 due. \\ PS7 out.}} & % Nancy

25 &

26 \lec{Cardinality.  Bijections.  Pigeonhole Principle.  }{} &  % Nancy

27 \tut{8} 

\eweek

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      WEEK 9
\week
\mo{Oct-Nov}

30 &

31 \lec{Basic counting.  Sum and product rules.  Inclusion/
  exclusion. }{\textbf{PS7 due. PS8 out.}} & % Shlomi

1 &

2 \lec{Permutations. Combinations.  Binomial coefficients.    }{} & % Shlomi

3 \tut{9}

\eweek

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      WEEK 10
\week
\mo{Nov}

6 &

7 \lec{Permutations and combinations with repetition.
  }{\textbf{PS8  due.}} &   % Shlomi

8 &

9 \lec{Countable and uncountable sets.}{} & % Shlomi

10 \dayoff{Veteran's Day holiday}

\eweek

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      WEEK 11
\week
\mo{Nov}

13 &

14 \lec{Introduction to probability.  Sample points and spaces.  
  }{\textbf{PS9 out}} & % Nancy

15 \dayoff{QUIZ 2:  Lectures 11-18}& 

16 \lec{Probability laws.  Conditional probability.  }{} & % Nancy

17 \tut{10} 

\eweek

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      WEEK 12
\week
\mo{Nov}
20  &

21 \lec{Independence.  Failure analysis.  }{\textbf{PS9 due. \\ PS10 out.}} & % Nancy

22 \dayoff{Drop date} & 

23 \dayoff{Thanksgiving holiday} &

24 \dayoff{Thanksgiving holiday}
\eweek

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      WEEK 13
\week
\mo{Nov-Dec}

27 &

28 \lec{Random variables.  Binomial distribution. }
{\textbf{PS10 due. \\ PS11 out.}} & % Shlomi

29 & 

30 \lec{Expectation.}{} & % Shlomi

1 \tut{11}

\eweek

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      WEEK 14

\week
\mo{Dec}

4 & 

5 \lec{Computing expectations.  Wald's theorem}{} & % Shlomi

6 &

7 \lec{ Variance. Bounding tails of distributions.}{\textbf{PS11
due.}} & % Shlomi

% Markov's thm,
% Chebyshev's thm 
% Chernoff's Bound

8 \tut{12}  

\eweek

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      WEEK 15

\week
\mo{Dec}

11 &

12 \lec{Random Walks.}{} & % Nancy

% Gambler's Ruin

13 &

14 &

 \dayoff{FINAL, Date and time TBA} 
%[[[Put the info here when we find it out. ]]]
\eweek

\iffalse
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

        \vfill

        \begin{center}
        (Lecture topics are subject to change.)
        \end{center}
\fi

\end{document}










