Articles in divide and conquer series

Fast Fourtier Transform

2019/1/30
| algorithm
Problem Given two vectors $a = (a_1, a_2, a_{n-1})$ and $b = (a_1, b_2, b_{n-1})$. The convolution of a * b is a vector with 2n - 1 coordinates, where coordinate k is $\sum_{(i,j):i+j=k|i,j < n} a_ib_j$, which is can be written as $$a ∗ b = (a_0b_0, a_0b_1 + a_1b_0, a_0b_2 + a_1b_1 + a_2b_0, … , a_{n−2}b_{n−1} + a_{n−1}b_{n−2}, a_{n−1}b_{n−1})$$ Or an n x n table, whose (i, j) entry is $a_ib_j$……

Read More

Integer Multiplication

2019/1/30
| algorithm
Problem Wiki Explanation Algorithm Let’s say we define $x = x_1 2^{n/2} + x_0$, then xy become \begin{align} xy &= (x_1 2^{n/2} + x_0)(y_1 2^{n/2} + y_0) \newline &= x_1 y_1 2^n + (x_1 y_0 + x_0 y_1)2^{n/2} + x_0 y_0 \end{align} So we have $$T(n) \leq 4T(n/2) + cn$$ But this is essentially $$T(n) \leq O(n^{\log_2 q}) = O(n^2)$$ However, we can reduce the time by observing that $(x_1 + x_0)(y_1 + y_0) = x_1y_1 + x_1y_0 + x_0y_1 + x_0y_0$.……

Read More

Closest Point

2019/1/29
| algorithm
Problem Given n points in the plane, find the pair that is closest together. Brute force takes $O(n^2)$. Algorithm Let’s $d(p_i, p_j)$ = Euclidean distance. In 1-d, we can simply sort points and compute the distance with the next point, we then have complexity of O(nlogn). In 2-d, we can’t applied the same thing. We will use divide and conquer. We find the closest pair in the left and closest pair in the right, and hoping to get it in linear time.……

Read More

Counting Inversion

2019/1/29
| algorithm
Problem Application in ranking, also called corraborative filtering. Comparing two rankings and decide how similar they are, or how many pairs are out of order. To quantify this, we count the number of inversions. The inversion is defined as two indices i < j that $a_i > a_j$. Algorithm Brute-Force $T(n) = O(n^2)$ Modified Merge-Sort By leverage the merge process form merger-sort, we can count the number of inversion. Basically, when the element from A is appended, there is not inversion.……

Read More

Merge Sort

2019/1/29
| algorithm
Problem Sort the elements Abstract the behavior: 1. Divide the input into two pieces of equal size O(n) 1. solve the two subproblems on these pieces separately by recursion 1. combine the two results into an overall solution O(n) Recurrence Time Complexity q = 2 T(n) ≤ 2T(n/2) + cn To analyze the above recurrence relation, check below image. At level j, we have $2^j$ nodes with size $n/2^j$ Each node takes $cn/2^j$, so level j takes $cn/2^j$ x $2^j = cn$ There are logn levels, so T(n) = O(nlogn) General Case For q > 2 T(n) ≤ qT(n/2) + cn……

Read More