## 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.