Description

Homework 1
(100 points total.)
• Please remember to staple if you turn in more than one page.
• Please write your team member’s name is you collaborate.
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.
(c) Worst-case complexity of quicksort (5 pts). Show that the worst case of quick sort takes O(n2) 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
,
where WN = e−i2Nπ, and
.
iii. Show that
Eek+N/2 = Eek, Oek+N/2 = Oek.
1
2. Basic linear algebra and statistical inference
(a) Rank of a product (5 pts). Suppose that A ∈ R4×3 has rank 2, and B ∈ R3×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 ∈ R4×3, rank(A) = 2, B ∈ R3×5, rank(B) = 1. (b) Repeat the above questions for A ∈ R4×2, rank(A) = 2, B ∈ R2×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
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

 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.
2