Description
1. Let X1, X2, . . . , Xn be a sample from the standard uniform U(0, 1) distribution. Find
the distribution of (Pn
i=1 Xi)mod1. [10 points]
2. Let F be a cumulative distribution function (c.d.f.). Define F
[−1](u) = min{x | F(x) ≥
u}. Show that if U ∼ U(0, 1), then F
[−1](U) ∼ F. [5 points]
3. There are many methods of Sampling from the Standard Normal distribution.
(a) Prove that the Box-Muller algorithm provides two independent standard normal
random deviates. [5 points]
(b) Prove that the Polar algorithm for simulating from the standard normal distribution provides two independent standard normal random deviates. [5 points]
4. Sampling from the tail of a standard normal. Perform a simulation experiment in R (or
any other software) to map the rejection rate with increasing d. Compare the result
with the theoretical naive rejection rate. (For this experiment, no code is required to
be turned in, but you are required to describe the experiment that you set up, and also
detail the results, using appropriate figures (and tables) if needed.) [10 points]
5. Compressed Column Storage. Consider the n × p sparse matrix W = ((wij ) with m
non-zero entries and stored in the following Compressed Column Storage (CCS) format:
• Consider the triple given by A = (a, r, c). where a = (a1, a2, . . . , am) is a mdimensional vector containing the non-zero values in W (stored column-wise),
r = (r1, r2, . . . , rm) is the m-dimensional vector with ri storing the row index
of the corresponding ai
, and c = (c1, c2, . . . , cp) is a (p + 1)-dimensional vector
with ci
indicating the element of a that starts the column of A. By convention,
cp+1 = m + 1. Thus, ai ≡ wri,k, where ck ≤ i < ck+1. Matrices may alternatively
be stored in the Compressed Row Storage format (CRS) defined correspondingly.
(a) Consider the product of A with a p-variate vector x. Let y = W x. Provide an
algorithm for calculating the j element of y. That is, write an algorithm which
will calculate yj given W in CCS format A = (a, r, c) and without expanding it
back to W. No programming is required, but only the algorithm in pseudo-code
should be provided. [10 points]
(b) Suppose that we now have a sparse symmetric p × p matrix V . Answer the
following questions:
i. Develop a similar CCS-type strategy for storing the matrix V in a packed
CCS format. [5 points]
ii. Provide, in pseudo-code, an algorithm for finding the jth element yj of y =
V x. [5 points]
6. Let U1, U2, . . . , UnU be a sample from Population 1 and V 1,V 2, . . . ,V nV be a sample from Population 2. Consider the following samples hypothesized (but not known
for sure) to be from different populations a follows: W1,W2, . . . ,WnW from Population 1, X1, X2, . . . , XnX
to be from Population 2, Y1, Y2, . . . , YnY
from Population 3,
Z1, Z2, . . . , ZnZ
from Population 4. The total within sum of squares (WSS) in this
scenario is given by
XnU
i=1
kUi − µˆ 1k
2 +
XnV
i=1
kV i − µˆ 2k
2 +
XnW
i=1
kWi − µˆ 1k
2 +
XnX
i=1
kXi − µˆ 2k
2
+
XnY
i=1
kY i − µˆ 3k
2 +
XnZ
i=1
kZi − µˆ 4k
2
,
(1)
where µˆ 1 = (nUU¯ + nWW)/(nU + nW ), µˆ 2 = (nV V¯ + nXX¯ )/(nV + nX), µˆ 3 = Y¯
and µˆ 4 = Z¯ . The above total WSS can be rewritten to be a sum of WSS from the
samples U1, U2, . . . , UnU
and V 1,V 2, . . . ,V nV plus some terms. (This is important
in the context of the following questions.) We are interested in finding how the total
WSS changes when we reassign an (unsure) observation from one population to the
other. To do so, we will investigate the three possibilities (there is actually a fourth,
but that is the converse of Case (b) below).
(a) Suppose we reassign WnW from Population 1 to Population 2. How does the total
WSS in (1) change? (Note that such a reassignment affects both µˆ 1 and µˆ 2
). [10
points]
(b) Suppose that from the original setup leading to (1). we reassign WnW from
Population 1 to Population 3. How does the total WSS in (1) change? (Note that
such a reassignment affects both µˆ 1 and µˆ 3
). [10 points]
(c) Suppose that from the original setup behind (1). we reassign Y nY
from Population
3 to Population 4. How does the total WSS in (1) change? (Note that such a
reassignment affects both µˆ 3 and µˆ 4
.
Note that an extension of this is the basis for
the Hartigan-Wong (1979) implementation of the k-means algorithm.) [10 points]
The reductions in all three parts above provides a stripped-down context of the basis
for an efficient implementation of the k-means semi-supervised clustering algorithm.
7. For each program, please write out how you compiled, executed the program and result.
You may include this code in as a comment.
(a) Write an annotated C program which converts temperature, from Fahrenheit to
the Celsius scale and vice-versa. [7 points]
(b) Write an annotated C program which takes in two integers i = 320 and j = 256
and reports their product. Store the product as a short and as an int and print
the result. What differences do you see? Please put in your observations and
reasoning as a comment in the C program. [8 points]