Class 1.
Introduction. The problem of Chinese male to female child ratio. 
Geometric series.

Class 2.
Mathematical Induction. Proof techniques. 
Examples of proofs using induction.

Class 3.
Two forms of Strong Induction. Examples of strong induction : proving
that you can pay any amount above 11 with 4 cent and 5 cent coins; prove
that all numbers can be written  as a  product of primes. 
Divisibility. Proofs by contradiction. There are  infinitely
many primes. The number 2^(1/2) is not rational.

Class 4.
Proofs by showing the contrapositive. If n=ab then either a<=n^(1/2)
or b<=n^(1/2). Non constructive proofs of existence: there are 
irrational numbers x,y such that x^y is rational. Sets and notations
and basic  opertions.  De Morgan rules. Proving two sets are equal. 
 A = {all numbers that are divisible by 6} is equal to
 B={all numbers divisible by 2 and 3 
at the same time}. Least common multiple and showing something
by a counterexample. Functions. 1-1 and onto definitions. Examples.

Class 5.
Functions. Onto functions. The basic counting technique. Proving
that |A|=|B|. The number of all functions. The number of all
1-1 functions. The number of all onto functions (only special
cases for now).

Class 6.
Inverse of a function. Finding the inverse.
Proving the number of elements of a powerset by induction.  
Relations. Properties of relations: reflexive, 
symmetric, transitive, antisymmetric. Examples : "at least as tall as",
"likes". 

Class 7.
Relation operations.
Equivalence Relations. Proving that the congruence modulo m
is an equivalence relation. We then proved that in an equivalence
relation (a,b) is in R iff [a]=[b] iff [a] intersection [b] is non-empty.
The set of equivalence classes defines a partition of
the space of the relation. Simple examples of equivalence
relations and the partitions defined. 

Class 8.
Permutations. The factorial function. Cycle decomposition
of permutations. Finding the order of a permutation.
Least common multiple of cycle orders.


Class 9.
The binomial coefficients. Counting the number of subsets
with k elements proof based on the relationship of k-tuples
and subsets of size k. 
Basic properties of Binomial coefficients:
How many bitstrings of length n have exactly k 1's. 
Why the usual multiplication rule fails. 
Similarly for 0's. Similarly for n-k 1's.
(n choose k) = (n choose n-k).
(n choose k)= (n-1 choose k) + (n-1 choose k-1). Proof by  partitioning
all subsets of a n-element set according to an element "a"
from the set. 
The sum of all (n choose k) for k=0..n equals 2^n.


Class 10.
Pascal triangle. The Fibonacci sequence in the Pascal triangle.
Relation of the Pascal Triangle to 
expressions of the form (1+x)^n. The Binomial Theorem. Proof
of the Binomial Theorem by induction. The proof demonstrates
some fundamental sum manipulation techniques; e.g. variable
renamings and regrouping the terms of summations.

Class 11.
 Counting the number of positive integer
solutions (including zero) of the equation x_1 + ... + x_r = m.
transformations of counting arguments: from solutions of the above
equations to tuples, then to boxes and balls, then
to bars and circles, then to bitstrings, and finally to subsets
(that we know how to count!). 
Choosing k objects out of n the four different cases, 
order/no order, repetition/ no repetition. Examples

Class 12.
The Inclusion/Exlusion Principle.
Formal statement of the Inclusion/ Exclusion Principle.
Proof of the Inclusion/Exclusion Principle by counting;
using an application of the Binomial Theorem for a series of 
sign-alternating binomial coffecients. Applications
of the Inclusion Exclusion principle.
Game: ``guess how many numbers are left.''

Midterm Review and Midterm.

Class 1.
Propositional Logic, Predicate Logic. Quantifiers.
Negation of quantified formulas.


Class 2. 
Approximations. Two general rules for the approximation
of  a summation and  a product. Examples of approximations:
the summation of all numbers 1,...,n. The factorial approximation.
Improving the tightness of the approximation. A lower bound for
the n-th harmonic number.

Class 3.
Midterm Solutions.

Class 4. 
Graphs. Definitions. 
Handshake Lemma. Adjacency Matrix.
Graph Isomoprhism.
Counting  the number of graphs over n vertices.
Lower bound on the number of isomorphic graphs of n vertices.

Class 5.
Euler Graphs. Motivation. Definition. Euler Cycle.
A graph has an Euler cycle iff it is connected and any vertex
has even degree. Proof of theorem by contradiction. 

Class 6.
Connectedness in graphs. 2-connected graphs. Characterization
of 2-connected graphs: every two vertices belong in a cycle.

Class 7.
cancelled.

Class 8.
Existential proofs by counting. 
Four dovetailing
shuffles are not enough to randomly permute
a deck of cards. On the existence
of "huge" boolean  functions.

Class 9.
Basic discrete probability. Random variables. Expectation.
 Some examples of finite probability
spaces. Playing the roulette at the casino. Expected winnings.
What is a fair probabilistic game?
Analysis of the following game: one player writes distinct numbers
in 10 cards of any desired size. deck is shuffled and player 2 flips cards
one by one so that he stops flipping at the largest  card written. We analyzed
a strategy that gives winning probability to player 2 of at least 25%

Class 10
More examples of random variables. Computing the expected value
using indicator random variables. The expected number of heads
when flipping n coins. The expected number of surviving rabbits
when n hunters shoot n rabbits at random. 
The probability of intersections  of events. Independent events.
Conditional Probability. The Monty Hall paradox (three doors).

Class 11
Combinatorial games more formally. Graphs of game configurations.
Labelling vertices as P-positions and N-positions. Every combinatorial
game has a winning strategy. Finding a winning strategy.
Subtraction games; drawing the configuration graph. Using
 S={1,2,3} as the subtraction set or  more generally other sets
e.g., S={1,3,4}.  General discussion on computing winning strategies
and Chess playing.

Class 12-13: Review exercises.