Prerequisite Quiz

CS 610

Spring 2002

1. n balls are thrown into n bins. Each ball is thrown independently and uniformly at random; i.e., the probability that it goes into a particular bin is 1/n. What is the probability that a particular bin remains empty? What is the expected number of empty bins? What is the expected fraction of empty bins for large n?

2. For two random events X and Y the contingency table of joint probabilities are given below.

\begin{aligned}& Ȳ & Y \\ X̄ & p_{00} & p_{01} \\ X & p_{10} & p_{11} \end{aligned}

If X and Y are independent, what relation will hold between p_{00}, p_{01}, p_{10} and p_{11}?

3. You are given a large 10^{5} ×10^{5} matrix A of floating point numbers (each 4 bytes) stored in a file (4 × 10^{1}0 bytes long) in row-major order (A_{1,1}, A_{1,2}, …, A_{1,10^{5}}, A_{2,1}, …, A_{2,10^{5}} etc.) on a computer with only 100 × 10^{6} bytes of RAM. How best can you write out the matrix in column-major format (A_{1,1}, A_{2,1}, …, A_{10^{5},1}, A_{1,2}, etc.) to another disk file?

4. What is the length of the projection of vector x⃗ on the vector y⃗? You can use any standard vector operators like dot product, vector norms, cross products, etc. in your answer.

5. There are n points on the line, some red and others blue. You are presented the input data points in arbitrary order as {(x_{i}, c_{i}), i = 1, …, n} where x_{i} is the position and c_{i} the color of the ith point. You need to find a point on this line such that points on one side are mostly red and points on the other side are mostly blue, and the number of exceptions is minimized. How will you do this and how quickly can you do this?