13
votes
Strassen algorithm for matrix multiplication complexity analysis
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$ ...
- 268k
10
votes
Show how to do FFT by hand
Define the polynomials, where deg(A) = q and deg(B) = p. The deg(C) = q + p.
In this case,...
- 101
10
votes
Accepted
Divide and Conquer to identify a knight from n people
An efficient algorithm using stack
Initialize an empty stack.
For each person $p$ in the given people:
If the stack is empty, push $p$ to the stack.
Otherwise, pit $p$ against the person at the top ...
- 32.9k
9
votes
Accepted
Categorization of Binary search as Divide and Conquer
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 ...
- 1,168
8
votes
Divide and Conquer to identify a knight from n people
Our princess proceeds as follows:
she asks her suitors to form up on a line
starting from the left, she asks each person about the virtue of their neighbour (and vice versa)
if there is an ...
- 529
7
votes
Accepted
Sums of all pairs: possible less than quadratic?
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 ...
5
votes
Categorization of Binary search as Divide and Conquer
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 ...
- 268k
5
votes
Accepted
Counting Total Number of Non-Equivalent Configurations in a 2-D Grid
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$, ...
D.W.♦
- 140k
5
votes
Strassen algorithm for matrix multiplication complexity analysis
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 ...
- 3,497
4
votes
Accepted
Just another Divide-And-Conquer question - but somehow different
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 ...
- 268k
4
votes
Why is $X_m$ and $Y_m$ not included in the shaded region(where median can lie)?
$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 ...
- 9,179
4
votes
Accepted
Exercise on Divide&Conquer's technique
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[\;]$:
...
- 14.5k
4
votes
Accepted
Justifying a claim in the proof of the master theorem
Suppose that $f(n) = O(n^{\log_b a - \epsilon})$. According to the definition, there exist constants $N,C>0$ such that $f(n) \leq Cn^{\log_b a - \epsilon}$ for all $n \geq N$. Let $M$ be the ...
- 268k
3
votes
Accepted
Understanding Closest Pair Algorithm (CLRS)
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 ...
- 46
3
votes
Accepted
Can Strassen's multiplication algorithm be improved if we divide matrices to 3x3 or axa in general?
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 ...
- 268k
3
votes
Algorithm in O(logn)
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$...
- 853
3
votes
Strassen Algorithm for Unusal Matrices
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 ...
- 24.9k
3
votes
Accepted
Find the asymptotic bound $\Theta$ of $t(n)=t(\frac{n}{5})+t(\frac{n}{17})+n$
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 ...
- 32.9k
3
votes
Accepted
Applications of divide-and-conquer outside of merge sort and quicksort
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 ...
- 32.9k
3
votes
Accepted
Difference between sequential and parallel divide and conquer
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 ...
- 268k
3
votes
How to understand the recurrence relation and time-complexity of StoogeSort?
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 ...
- 268k
3
votes
Converting a greedy algorithm to a dynamic programming algorithm
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 ...
- 4,073
3
votes
Clarification on the algorithm for finding a majority element
The algorithm as written assumes that $n$ is a power of 2. But you can adjust it to support odd-length arrays, while still completing in $O(n)$ time, as follows:
Suppose that at some given point in ...
- 268k
3
votes
Algorithms question: Largest contiguous subset selection
O(n) solution:
Move index j from left to right and drag i behind so that the window from i ...
- 178
3
votes
Divide and Conquer to identify a knight from n people
This can be solved efficiently with the Boyer-Moore majority algorithm. Everyone casts a vote on the candidate currently occupying the hot seat. When the count reaches zero, the candidate is evicted ...
- 674
2
votes
$O(n \log n)$ simple polygon triangulation via divide and conquer
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.
- 268k
2
votes
How many times can you divide a list of n elements in 1/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 ...
- 268k
2
votes
Accepted
Help needed with lesson on recursion
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 ...
- 20.3k
2
votes
Divide and Conquer 3D Convex Hull
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, ...
D.W.♦
- 140k
2
votes
Divide-and-Conquer Exercise
Hint: Define $B[i] = A[i] - i$. What can you say about the array $B$? Use the fact that $A$ contains distinct integers.
- 268k
Only top scored, non community-wiki answers of a minimum length are eligible