Hot answers tagged

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 ...


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}{...


3

Every path must hit the top left and bottom right corners. Let $x$ be the minimal element among the remaining $NM-2$ elements. The lexicographically smallest path must go through $x$. If $x$ is at address $(i,j)$, this decomposes the original problem to two problems of the same form: one on an $i \times j$ matrix, and the other on an $(N-i+1) \times (M-j+1)$ ...


3

Once you get the point, you can use Flood Fill Algorithm to replace the current color in the region containing the point with the new color. Basically, this algorithm starts from a specified point and then recursively(or iteratively) keep replacing the current color with the new specified color in the neighbouring points till it reaches the boundary of the ...


2

Suppose that $A$ and $B$ are vectors of length $n$, where $n$ is a power of 2. We index $A$ and $B$ using binary vectors of length $\log_2 n$, and define their convolution $C$ as $$ C_i = \sum_{j \oplus k = i} A_j B_k. $$ You can calculate the convolution of $A$ and $B$ using the following algorithm: Compute the Walsh transform of $A$: $\alpha = H_n A$. ...


2

The solution is to pad the matrices with zeroes, using the block matrix identity $$ \begin{bmatrix} A & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} B & 0 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} AB & 0 \\ 0 & 0 \end{bmatrix} . $$ Here $A,B$ are $n\times n$ matrices, and the big matrices are $N\times N$ for some $N > n$. In other ...


1

The classical recursive algorithm to calculate the Cartesian product $A_1 \times \cdots \times A_n$ goes as follows: If $n = 0$, return the empty tuple. Otherwise, for every $x_1 \in A_1$ and $(x_2,\ldots,x_n) \in A_2 \times \cdots \times A_n$, output $(x_1,x_2,\ldots,x_n)$. In the second step, you compute $A_2 \times \cdots \times A_n$ recursively. You ...


1

The idea is that $$ \mathbb{E}[u^{\prime T} v'] = \mathbb{E}[u^T S^T S v] = u^T \mathbb{E}[S^T S] v, $$ due to linearity of expectation. You can take it from here.


1

I'm going to assume you're asking for an algorithm, since coding questions are generally off-topic here (you might want to try StackOverflow instead). Remember that the diagonal elements of a matrix $M$ are $M_{ii}$ for all $i$. This makes the algorithm very similar to summing a list (i.e. taking the sum of $A_i$ for all $i$). A recursive algorithm for ...


1

There is trivial reduction from set cover. Consider 0-1 matrix where columns are subsets, rows are set elements and 1 means that subset contains element. Algorithm for your problem then can find K subsets to cover (sum max elements to n) set. So your problem is NP-hard, no chances.


1

These are triangular numbers, so: $i = \lfloor(-0.5 + \sqrt{0.25 + 2 * n}\rfloor - 1\\ triangular = \frac{i * (i + 1)}{2}\\ j = n - triangular - 1$ Minus one comes from indexing from 1.


1

I eventually found an answer. The image of a hypercube in $\Bbb R^3$ under a linear map is called a zonohedron. They can be calculated efficiently, for example using the algorithm in An Efficient Algorithm for Generating Zonohedra (PostScript file) by Paul Heckbert.


1

It appears that the analysis assumes that integer variables are stored in registers, whereas array elements have to be loaded from and stored to memory. The point you've missed is that the statemnt X += Y requires reading X and then writing the new value of X. sum += a[i][k] * b[k][j]; This loads a[i][k], loads b[k][j], multiplies them, reads sum, adds sum ...


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