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


4

Consider the product $ABC$, where $A$ is $5\times 2$ $B$ is $2\times 3$ $C$ is $3\times 100$ Your algorithm first computes $BC$ (600 products) and then $A(BC)$ (1000 products), for a total of 1600 products. The optimal solution first computes $AB$ (30 products) and then $(AB)C$ (1500 products), for a total of only 1530 products. Suppose that $A$ is $a\...


3

In the tropical semiring, the "addition" operation is the minimum, and the "multiplication" operation is addition. If you want to adapt matrix multiplication to the tropical semiring, you literally need to replace every occurrence of $+$ with $\min$, and $*$ with $+$. To this effect, look at the line: sum+= A[i][k]*B[k][j] Let's rewrite it "properly", ...


3

The fact that the total number of candies is at maximum 12 is an important constraint. Let the candies and start and end points (total <=14 points) be key points in the grid. Now use BFS from each of the key points to find the distances between the key points, and form a new graph with only the key points. Since the number of nodes in the new graph is so ...


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


3

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


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


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

The $2\times 2$ matrix has determinant close to zero, and so its condition number is very large, causing numerical instability. The explicit solution of your system is $$ x=\frac{a}{a^2-b^2}, y=-\frac{b}{a^2-b^2}. $$ Therefore $$ x+y = \frac{a-b}{a^2-b^2} = \frac{1}{a+b}, $$ thus avoiding the numerical issues.


1

It’s a 3x3 matrix, so it can be done in constant time O(1). I can’t see where a “k” comes into this problem.


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