Correctness Proofs and Time Bounds for Algorithms Sections 2.1, 2.2
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
: number of k-permutations of an n-set;
(also denoted ): number of k-element subsets of an n-set
if k > n
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.
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;
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
Relations and Their Properties Section 6.1
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: