CS 206 : Summer, 2003
Homework assignments
Homework solutions
Midterms
Selected Solutions to Midterms
(Some) Solutions to Midterm 1.
Notes on Selected topics
Most of these are taken off Ross :
- Crib sheet for the final
- Handwritten solutions for hw2 :
- Handwritten solutions for Practice Problems :
- Handwritten notes :
- Geometric Random Variables :
- Linearity of Expectation :
- Binomial Random Variables :
- Negative Binomial & Hypergeometric Random Variables :
- Poisson random variables :
- Bill's notes on Variance, Generating functions et al.:
Lesson Plans.
- Monday, July 7th :
- Midterm 2 will be held on Friday, Aug. 1st, from 7 pm to
10 pm either in Hill 114 or Hill 425.
- Throughout the course, little omega (o of the greek alphabet)
will represent an outcome in a sample space.
- Recap. of r.v's : a random variable is a function over the
sample space to the set of real numbers. What is Ran(X), etc?
- Recap. of events defined via r.v's : Why is X = a (for some
real number a) an "event" (throughout the course, capital letters
X, Y, Z will represent r.v's unless otherwise stated).
- Examples of r.v's : repeated tossing of a fair coin and
counting the number of heads turned up.
- Definition of Expectation of a r.v. : E[X] is just a
generalization of the notion of average to general probability
distributions (it is in fact a weighted average).
- Basic properties of E[X] : for nonnegative random variables,
the expectation is nonnegative viz. the average of nonnegative
quantities is also nonnegative.
- The sum of two random variables is the pointwise sum of
the functions (over the sample space) that they represent.
- Linearity of E[X] : Expectation of the sum = sum of the
expectations.
- Different definitions of E[X] where the sum ranges over
either the outcomes in the Sample Space, or over elements of
the range of the r.v. X. (note : |S| >= |Ran(X)|)
- Indicator random variables. How they "indicate" occurence of
events, and their expectation.
- Applications of the three items above : in the hat experiment, the
expected number of people getting their own hats back is...
Motto : Think of r.v's as functions and think of what one can do with
functions.
- Wednesday, July 9th :
- E[constant] = constant : What do we mean by a constant r.v.?
- Given two functions f & g, how do you define f*g? Given a random
variable X, what do you mean by a r.v. X^2?
- What is the probability mass function, distribution function of a
r.v.?
- Joint distribution of two random variables, X & Y.
- Independence of two random variables, X & Y.
- E[aX+b] = aE[X]+b : How to use linearity of expecation resourcefully.
- Definition of Var(X), motivation. Standard deviation.
- Bernoulli and Binomial random variables. Examples.
- Properties of Binomial random variables. For a binomial r.v. X
with parameters (n,p), E[X] = np, Var(X) = np(1-p).
- Monday, July 14th :
- Geometric random variables. Infinite sample spaces. Why are
geometric random variables called so?
- Rough intuition and correlation between Binomial and Geometric
random variables. Given X is a Geometric random variable, what is
E[X]? Var(X)?
- For two independent r.v's X, Y : E[XY] = ...
- Is Var(X) linear? When is Var(X + Y) = Var(X) + Var(Y) ?
- Monday, July 28th :
- Recurrence Relations : motivation, examples.
- A recurrence relation for Derangements.
- Linearity of recurrence relations. Homogeneity. Degree.
- Linear Homogeneous recurrence relations with constant
coefficients. Examples : tiling of a 2 x n rectangle by dominoes,
Fibonacci numbers, bit strings of length n which don't have the
substring '00'
- Properties of Linear Homogeneous recurrence relations : if
f, g are solutions, then so also are (1) cf (c a constant) and
(2) f + g.
- Boundary conditions or initial conditions of a recurrence
relation.
- Solving a homogeneous linear recurrence relation based on
intuition from geometric progressions. Characteristic polynomial
corresponding to a linear homogeneous recurrence relation.
- Case of distinct roots of the characteristic polynomial.
Case of repeated roots.
- Nonhomogeneous linear recurrence relations. Example, Towers
of Hanoi. Definition of a particular solution, a general solution
of a nonhomogeneous linear recurrence relation = the particular
solution + the general solution to the homogeneous part.
- Wednesday, July 30th :
- Recurrence Relations : Divide and conquer relations.
- Markov's and Chebyshev's Inequalities.
- A few problems based on above.
- Pigeon hole principle. Applications.
- Monday, Aug. 4th :
- Hypergeometric and Negative Binomial Distributions.
- Comparison with the Binomial and the Geometric.
- Calculation of Variance, Expectation of the Hypergeometric,
Negative Binomial
- Poisson distribution as an approximation of the Binomial
for large values of n and small values of p.
- Intuitive derivation of the expectation and variance of the
above distributions from the Binomial.
- Wednesday, Aug. 6th :
- Introduction to generating functions.
- How to solve usual linear recurrence relations using
generating functions. Example : the Fibonacci recurrence
relation.
- More : how to solve simultaneous recurrence relations
using generating functions.
- Catalan numbers : the number of ways to parenthesize
a multiplication of (n+1) numbers. Derivation of a generating
function for the Catalan numbers.
- Applying generating functions to solve the (nonlinear)
recurrence relation
Acknowledgements
Are due to Bill
for letting me use his notes for a past course on CS206, and to
Detlef for helping
me with the latex documentation.
Miscellaneous
