28
Suppose we use fourth roots of unity, which corresponds to substituting $1,i,-1,-i$ for $x$. We also use decimation-in-time rather than decimation-in-frequency in the FFT algorithm. (We also apply a bit-reversal operation seamlessly.)
In order to compute the transform of the first polynomial, we start by writing the coefficients:
$$ 3,1,0,0. $$
The Fourier ...
13
It's true that the parameter $n$ usually denotes the size of the input, but this is not always the case. For square matrix multiplication, $n$ denotes the number of rows (or columns). For graphs, $n$ often denotes the number of vertices, and $m$ the number of edges. For algorithms on Boolean functions, $n$ denotes the number of inputs, though the truth table ...
9
This might seem silly but here we go.
Let our array be $A$ and the current range we are searching in be denoted as $[L,R]$ and let $mid = \frac{L+R}{2}$.
The divide step - We divide our search space into two ranges - $[L,mid-1]$ and $[mid,R]$.
The conquer step - Let's assume that WLOG the element $x$ that we are searching for is such that $x < A[mid]$. ...
8
Define the polynomials, where deg(A) = q and deg(B) = p. The deg(C) = q + p.
In this case, deg(C) = 1 + 2 = 3.
$$
A = 3 + x \\
B = 2x^2 + 2 \\
C = A*B = ?
$$
We can easily find C in $O(n^2)$ time by brute-force multiplication of coefficients. By applying FFT (and inverse FFT), we could achieve this in $O(n\log(n))$ time. Explicitly:
Convert the ...
7
Yes, it is possible using $O(n \log n)$ preprocessing and $O(\log n)$ query time.
Given the set $S$, construct the polynomial $P(x)=\Sigma_{s\in S}\textrm{ } x^s$. Then use the FFT multiplication algorithm to compute $P^2(x)=P(x)*P(x)$ in $O(n \log n)$.
A value $q$ s a sum-of-pairs of $S$ if and only if the coefficient of $x^q$ in $P^2(x)$ is non-zero. Use ...
6
"Divide & Conquer" is not a very fixed notion. It usually goes along the lines of
D&C algorithms divide the problem and solve recursively.
That's not very strong, for the following reasons.
What I would call inductive algorithms do this, but are usually not considered divide & conquer algorithms. Given a problem of size $n$, inductive ...
5
A formal treatment (somewhat resembling the model proposed in the question) of the subject using what is called pseudo-morphisms (that is, functions that are almost morphisms, with some pre- and post-computation done), as well as considerations of complexity analysis and parallel implementation of such algorithms are given in:
An algebraic model for divide-...
5
There is no accepted formal definition of the divide and conquer paradigm (see this question for some suggestions), and so we must regard this paradigm as an informal concept. The main idea in divide and conquer is to split the original problem into smaller subproblems of a similar nature, and then combine them to deduce the final answer. In the case of ...
5
We will use Burnside's lemma, plus some additional optimizations.
Note that row swaps and column swaps commute, so the group of allowable transformations to the grid is exactly $G = S_w \times S_h$, where $S_n$ is the symmetric group on $n$ symbols. Note that $G$ embeds in $S_{wh}$ via a canonical embedding $\varphi : G \to S_{wh}$, given by $\varphi(\pi,\...
5
It's back to the size of the matrix. Suppose the original matrix is $n\times n$. Hence we will consider $T(n)$ as a computation of two matrix with size of $n\times n$. When we divide the original matrix to 4 part, size of each part is $\frac{n}{2}\times \frac{n}{2}$. Hence, the computation cost of multiplication of two matrices with this size is $T(\frac{n}{...
4
Given an array of elements $a[i], 0\le i\le n-1$, we know we can sort it in time $O(n\log n)$. Then do the following to produce an array $b[\;]$:
declare b to be of size n
old = a[0]
b[0] = a[0]
j = 1
for i = 1, ... , n
if a[i] =/= old // found a new value
old = a[i] // save it
b[j] = a[i] // store it in b[j]
j = j + 1 ...
4
$X_m$ and $Y_m$ are not shaded, because each of them is potentially the median of $X \cup Y$.
Consider two examples (Below I take the $\lfloor (n+1)/2 \rfloor$-th element as the median of an array of size $n$):
(1) $X = \{ 2, 4, 6 \}$ and $Y = \{ 3, 5, 7 \}$.
(2) $X = \{ 2, 4, 6 , 8 \}$ and $Y = \{ 3, 5, 7, 9 \}$.
I think the caption of Figure 1 is ...
4
Does a D&C algorithm have to have O(nlogn) complexity and divide the problem in half every time?
No.
Consider Karatsuba's multiplication algorithm. Given two $n$-bit integers $x$ and $y$, the algorithm multiplies them as follows:
a = x >> n/2;
b = x - (a << n/2);
c = y >> n/2;
d = y - (c << n/2);
u = a*c // recurse!...
4
Your solution doesn't work since it could output $i_2,j_1$ which isn't legal since $i_2 > j_1$. Your code also has a few bugs — are you returning indices or stock prices?
The idea behind the divide and conquer solution is that the optimal solution is of one of three forms:
Buy and sell within the first half.
Buy and sell within the second half.
...
4
Hint: Divide $A$ evenly into two smaller arrays $A_1,A_2$, and solve the problem (recursively) on $A_1$ and $A_2$. Can that help you find the optimum on $A$? Don't forget you're allowed to use extra processing costing up to $O(n)$.
Another hint: Suppose that $p,q$ is the optimal pair for $A$. Either $p,q \in A_1$, or $p,q \in A_2$, or neither of these cases ...
3
There are FFT algorithms for prime sizes such as Rader's algorithm. Given a factorization of $n$ as a product of (not necessarily different) primes, you can compute the DFT by running Rader's algorithm for each prime, in the same way that the usual FFT works by in effect computing FFTs of size $2$. You can read the details in a paper by Frigo and Johnson ...
3
Your algorithm, while recursive, is not really D&C.
An algorithm is usually referred to as D&C if it solves the problem by dividing the instance into smaller instances of the same problem, and solving each smaller part using the same algorithm. The division does not have to be into two parts (and in particular not to two equal parts), nor does it ...
3
What I'd have done is to scan the array of prices, keeping track of the best range seen so far and the best starting point for the range ending here. I.e., when standing at day $k$, know the best range before $k$ (say $i$ to $j$, and its value $b$; and keep track what $l$ is so that the range $l$ to $k$ is maximal, say $B$, and if $B$ is better than $b$ ...
3
Assume that a point exists in every corner in the figure (including the inside corners). If points cannot overlap, then you have 6 points that can reside in the 𝛿x2𝛿 box, and since you must be looking at one of them, you need only compare it to the next 5 in Y'.
3
There is nothing special about 2×2 matrices. In fact you can do much better using larger matrices. The reason that you are only being explained the 2×2 algorithm is that it is simple to describe. The special thing about 2×2 matrices are that they are the smallest square matrices which are larger than 1×1.
You can read more in this recent survey by Dumas and ...
3
This can be viewed as an array with indices given by $1,2,3,\dots,n$ such that $f(i)$ is stored at index $i$.
As $f(i)$ is monotonic, and the sign changes from positive to negative with increasing $i$, it can be concluded that $f(i)$ is a decreasing function, which tells us that the array is sorted in decreasing order.
Here, we are looking for the smallest ...
3
Almost the same as Yuval's answer, except...
If I gave you two 1025 x 1025 matrices, you wouldn't extend them to 2048 x 2048. You'd extend them to 1026 x 1026, and use one layer of Strassen's algorithm with 513 x 513 matrices - if you decided that this is faster than direct calculation of a 1025 x 1025 product. One recursion level lower, you'd decide ...
3
If we are not restricted by "using the master theorem", then either a better version of the master theorem, the versatile Akra-Bazzi method or the elementary way to show many recurrence relations mean $\Theta(n)$ or $\Theta(n\ln n)$ is an easy approach.
Otherwise, let us see how we can use the master theorem. We assume here $t(n)\geq 0$ for all $n \geq 0$, ...
3
There are many algorithms that uses the divide-and-conquer paradigm besides merge sort and quicksort.
"There is no accepted formal definition of the divide and conquer paradigm, and so we must regard this paradigm as an informal concept.", reads an answer by Yuval Filmus. I will use Wikipedia entry on divide-and-conquer as the reference to interpret its ...
3
Just like you wrote, you can solve independent subproblems in parallel. Here are two examples:
In merge sort, you can sort the two halves of the input in parallel, and then merge them together sequentially.
In quicksort, you split the input into two halves sequentially, and can then sort both of them in parallel.
In the first case there is no divide step, ...
3
Here are some more hints:
The algorithm partitions the array $A$ into three parts $B,C,D$ such that $|C| \geq |B|,|D|$ and then sorts $BC$ (the array formed by the first two parts), $CD$ (the array formed by the last two parts), and then $BC$ again. Show that for any such partition, the result is sorted. You can use the 0-1 principle.
When $n=4$, the ...
3
The example you specified is not turning a greedy algorithm to a dynamic programming solution. You reduced a problem to another using a greedy argument and solved the other problem using dynamic programming. That is why it is still not clear to me what do you mean by converting greedy to dynamic programming. However, that being said I have three points to ...
3
No. Any algorithm to locate those two peaks will take $\Omega(N)$ time, assuming that the only operation allowed is to compare two elements in the array, i.e., the comparison mode.
Otherwise, suppose algorithm $A$ do not need that much time. Let $arr[0], arr[1], \cdots, arr[N-1]$ be the given array. Then for some $N$ large enough, $A$ will have only checked ...
2
I'm not aware of something as concrete as Bellman's Optimality Principle for Divide and Conquer algorithms. However, the underlying foundation of divide and conquer seems to me to be a recursive (or inductive) definition of the problem's input and then a means of combining solutions to the problem in to larger solutions. The key insight here is thinking ...
Only top voted, non community-wiki answers of a minimum length are eligible
