Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 3511: Algorithms Honors Homework 2
Instructions:
- Upload your solutions to as a single PDF on Gradescope. Please anonymize all your submissions (i.e., do not list your name in the PDF), but if you forget, it’s OK.
- You may collaborate with any classmates, textbooks, any resource on the internet (but don’t search for the problem solution), etc. Please upload a brief “collaboration state ment” listing any collaborators as the last page of your solutions PDF on Gradescope. But after the collaboration, always write your solutions individually.
- For each problem, you should aim to keep your writeup below one page. For some problems, this may be infeasible, and for some problems you may write significantly less than a page. This is not a hard constraint, but part of the assignment is figuring out how to easily convince the grader of correctness, and to do so concisely. “One page” is just a guideline: if your solution is longer because you chose to use figures (or large margins, display math, etc.) that’s fine.
- Each problem is worth ten points (even those with multiple subparts).
Problems:
§1 (Vandermonde Matrices). Recall the definition of n×n matrix M(x) defined in class, where the entry of the j-th row and k-th column of matrix M(x) is x (j−1)(k−1). Let ω = exp(2πi/n) be the n-th root of unity.
(a) Prove that the columns of matrix M(ω) are orthogonal to each other, i.e., for any two distinct column vectors u, v of M(ω), we have P n j =1 ujvj ∗ = 0 for vj ∗ being the complex conjugate of vj .
(b) Use Part (a) to deduce that the product of matrices M(ω) and M∗ (ω) is nI, where I is an n×n identity matrix and M∗ (ω) is a matrix obtained by taking tranpose of matrix M(ω) followed by replacing each entry with its complex conjugate.
(c) Part (b) implies that the inverse of M(ω) is 1 nM∗ (ω). Prove that M∗ (ω) = M(ω −1 ).
§2 (Divide and Conquer) Suppose you are given n points (x1, y1),(x2, y2), . . . ,(xn, yn) in a 2-d plane. (Assume no two points have the same first or the second coordinate.) The goal is to find the distance (i.e., p (xi − xj ) 2 + (yi − yj ) 2) between the two closest distinct points (xi , yi) and (xj , yj ). We analyze the following algorithm.
Start by finding the median x of the first-coordinates of the points, i.e., n/2 points have xi ≤ x and n/2 points have xi > x. Call these the left L and right R points. Our algorithm recursively finds the pair of points that are closest in L (with distance dL) and the pair of points that are closest in R (with distance dR). Let d = min{dL, dR]}. For the conquer step, we need to check if there exist some point u ∈ L and v ∈ R with their distance less than d.
Discard all points in L with xi < x − d and all points in R with xi > x + d. The remaining points M are sorted w.r.t. their second-coordinate. In this sorted order, we compute for each point (xi , yi) in M its distance to the next 7 points in M. Among all these distances (roughly 7 times the size of M), let dM denote the smallest distance.
(a) Prove that any square of size d × d contains at most four points of L.
(b) Using Part (a), prove that the above algorithm is correct.
(c) Write the recursion for the algorithm and prove that it has running time O(n log2 n).
(d) How can we improve the algorithm to O(n log n) time?
(a) Suppose you are given a binary tree T with n nodes and root r. The diameter of T is defined to be the longest path between any two vertices in T. Design an O(n) time algorithm to find the diamater of T.
(b) Given a graph G = (V, E), use DFS to design a linear time algorithm that finds all vertices v ∈ V such that removing v makes the induced subgraph of G on vertices V \ {v} disconnected.
- Non-trivial: ∅ ∈ I.
- Downwards-closed: If S ∈ I, then T ∈ I for all T ⊆ S.
- Augmentation: If S, T ∈ I, and |S| > |T|, then there exists an i ∈ S \ T such that T ∪ {i} ∈ I. 1
i. (Uniform matroid) Sets of size at most k (that is, the elements are [n], and I = {X ⊆ [n]| |X| ≤ k}).
ii. (Graphic matroid) Acyclic subgraphs of any undirected graph G = (V, E) (that is, the elements are E and I = {X ⊆ E|X contains no cycles}).