Correctness Proofs and Time Bounds for Algorithms Sections 2.1, 2.2
Procedure 
:integer
Procedure linearsearch(x:integer;
:distinct integers)
Procedure binarysearch
:integer;
: increasing
integers)
For each of these procedures: invariant assertion, proof of
termination, time bound.
Recursive Definitions and Recursive Algorithms Sections 3.3, 3.4
Examples: 
, Fibonacci sequence 
, 
Recursive version of binary search
Divisibility, greatest common divisor, euclidean
algorithm(pp. 126-128, 204-206)
time bound for euclidean algorithm
Counting Sections 4.1, 4.3
Sum rule
Product rule
: number of k-permutations of an n-set; 
(also denoted 
): number of k-element subsets
of an n-set
if k > n
Pascal's triangle
Binomial Theorem: 
Consequences of binomial theorem: 
; 
Pigeonhole Principle Section 4.2
If k+1 or more objects are placed in k boxes then some box receives
at least two objects.
If N objects are placed in k boxes then some box receives at least
objects.
Application: Among any n+1 positive integers not exceeding 2n
there must be an integer that divides one of the other integers.
Application (not covered in lecture): Every sequence of n distinct
numbers contains either an increasing subsequence of length n+1 or a
decreasing subsequence of length n+1.
Probability Sections 4.4, 4.5
Experiment, sample space S, event E
Assuming all points in the sample space are equally likely, the
probability of event E is 
.
Examples: balls in urns, poker hands, dice, birthdays.
Generalization: 
,
,
, 
.
Conditional probability: 
events E and F are independent if 
;
equivalently 
, 
Bernoulli trial, binomial distribution: if a coin has probability p
of heads and probability q of tails , then the probability of
exactly k heads in n independent tosses is 
.
A random variable X is a function from the sample space of an
experiment to the set of real numbers.
The expectation of random variable X is 
Theorem: The expectation of a sum of random variables is the sum of
their expectations.
Application: the expectation of a binomial random variable is np,
where n is the number of coin tosses and p is the probability of
heads.
Recurrence Relations Sections 5.1, 5.2; Appendix 3
Example: towers of Hanoi:
Example: dots and dashes:
Example: rooted, ordered binary trees: 
,
First solution method: tabulating, guessing and verifying
Generating function of sequence 
: 
Example: 
for all n;
Example: 
; 
Deriving generating function from recurrence relation: multiply term
for 
by 
, then sum over n
; 
;
; 
Passing from the generating function to the sequence:
partial fractions expansion: example: 
example: 
where 
and 
are
the roots of 
; 
; 
Linear homogeneous recurrence with constant coefficients: 
; characteristic
polynomial 
; if characteristic
polynomial has distinct roots 
then general
solution is 
; case of repeated
roots discussed in Section 5.2.
binomial theorem (case of fractional exponent a): 
, where 
Solution: 
Relations and Their Properties Section 6.1
ordered n-tuple 
order matters:
Cartesian Product 
A relation R from A to B is a subset of 
a R b synonymous with 
graphical and matrix representations
A relation on a set A is a subset of 
.
R is reflexive if, for all 
, a R a
R is symmetric if a R b inplies b R a
R is transitive if aRb and b R c implies a R c
operations on relations: 
, 
, 
composition of rlations: 
if and only if
powers of relations:
Theorem: The following are equivalent:
;
.