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]$. ...
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 ...
7
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 ...
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
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
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 ...
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 ...
3
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 ...
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
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 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.
...
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
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
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 ...
2
You haven't explained what "divide in half" means, but let's assume that it means to divide the list into two halves of as equal size as possible (equal if the number of elements is even, almost equal if it's odd).
You can draw recursive "division in half" as a tree. The root is labelled by the original number of vertices, $n$. A node labelled $1$ is a leaf....
2
Garey, Johnson, Preparata and Tarjan came up with a simple $O(n\log n)$ algorithm back in 1978. It is described in many lecture notes, for example these lecture notes of Piotr Indyk.
2
You can do the counting in linear time for each merge step by iterating over the right list and keeping track of the following information regarding the left list:
pointers to the first and last element that formed an inversion with the previous element of the right list
the number of elements between those pointers
Since this is homework, I'll leave it to ...
2
The value $m$ can be used to advantage by simply sorting the list, and applying whatever $O(n)$ algorithm you had in mind on the list pruned to exclude items greater than the requested sum (which is $< 2m$). You get $O(m + log(n))$ complexity then.
2
The paper explains why the number of comparisons is $O(n)$ in the next few sentences immediately after the statement you're asking for a justification of. Just keep reading for a few more sentences, and you'll immediately find the justification. As it says,
"First of all, we notice that each type 1 comparison definitively eliminates one edge ... Since ...
2
Here are several approaches to compute $x^n$ from smaller powers of $x$:
doing $x \times x^{n-1}$. The former is $P(1)$ the latter is $P(n-1)$.
doing $x^2 \times x^{n-2}$. The former is $P(2)$, the latter $P(n-2)$.
But we don't need to use $P(1)$ and $P(2)$ at each step, right? we can use any $P(k)$ with $k<n$. So how about,
doing $x^{n/2} \times x^{n/...
Only top voted, non community-wiki answers of a minimum length are eligible
