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$ ...
user avatar
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,...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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$, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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[\;]$: ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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$...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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.
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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, ...
user avatar
  • 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.
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible