Description
1. Algorithms
(a) Simple questions (10 pts/2.5 pts each question.)
• What does algorithm efficiency mean? What are two types of algorithm efficiency
measures?
• What does algorithm robustness mean? Given one example of robust algorithm.
• What does algorithm stability mean? What’s the difference of algorithm stability
and robustness?
• Given two commonly seen definition of algorithm accuracy. Why do we sometimes
prefer approximate algorithms?
(b) Bisection (20 pts). Write MATLAB (or Python or R) code to implement bisection
algorithm to find the α = 0.95-quantile of a t distribution with n = 5 degrees of
freedom. Start with initial interval [1.291, 2.582]. Stop when the length of the interval
is less than 10−4
.
(Hint: You may use for loop in matlab. You do not have to be concerned with
efficiency of the code for now.)
(c) Worst-case complexity of quicksort (5 pts). Show that the worst case of quick
sort takes O(n
2
) operations.
(d) Fourier transform of a delayed signal (5 pts). Show that
F(x(t − τ )) = e
−i2πfτX(f).
(e) Steps for deriving FFT (20 pts). Let xn be a signal that is 0 outside the interval
0 ≤ n ≤ N −1. Suppose N is even. Let en = x2n represent the even-indexed samples,
and let on = x2n+1 represent the odd-indexed samples
i. Show that en and on are zero outside the interval 0 ≤ n ≤ (N/2) − 1.
ii. Show that
xek =
1
2
Eek +
1
2
Wk
N Oek, k = 0, 1, . . . , N − 1,
where WN = e
−i
2π
N , and
Eek = 2
N/
X
2−1
n=0
enWnk
N/2
, Oek = 2
N/
X
2−1
n=0
onWnk
N/2
.
iii. Show that
Ee
k+N/2 = Eek, Oe
k+N/2 = Oek.
2. Basic linear algebra and statistical inference
(a) Rank of a product (5 pts). Suppose that A ∈ R
4×3 has rank 2, and B ∈ R
3×5
has rank 3. What values can r = Rank(AB) possibly have? For each value r that is
possible, given an example, i.e., a specific A and B with the dimensions and ranks
given above, for which Rank(AB) = r.
(Optional): (a) Repeat the above questions for A ∈ R
4×3
, rank(A) = 2, B ∈ R
3×5
,
rank(B) = 1. (b) Repeat the above questions for A ∈ R
4×2
, rank(A) = 2, B ∈ R
2×5
,
rank(B) = 1.
(b) Simple Bayesian inference (20 pts).
i. Let x ∼ N (µ, σ2
), and assume a prior distribution µ ∼ N (θ, τ 2
). Derive to show
that the posterior distribution µ|x ∼ N (
τ
2
τ
2+σ2 x +
σ
2
σ2+τ
2 θ, σ
2τ
2
σ2+τ
2 ).
ii. Now if we change the prior distribution to be µ ∼ Unif[0, 1], what will be the
form of the posterior distribution µ|x?
(c) Maximum likelihood estimator (10 pts). Let X1, . . . , Xn independent random
variables identically distributed with density function
f(x) =
1
b−a
, a ≤ x ≤ b
0, otherwise
• Find the Maximum Likelihood Estimator for a ∈ R and b.
• (Optional) Are they unbiased estimators? (Hint: consider order statistics).
(d) Hypothesis test of the mean (5 pts). The drying time for a certain type of paint
under specified test conditions is known to be normally distributed with mean value
75 min and standard deviation σ = 9 min. Chemists have proposed a new additive
designed to decrease average drying time.
It is believed that the drying times with
this additive will remain normally distributed with σ = 9. Because of the expense
associated with the additive, evidence should strongly suggest an improvement in
average drying time before such a conclusion is adopted. Experimental data consist
of drying times from n = 25 test specimens. State the hypotheses to be tested.
Construct a likelihood ratio test and calculate the threshold so that the probability
of false detection is 0.05.