Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.
5

The classical framework is the one of bilinear algorithms and tensor rank decompositions; basically, you construct the 3-way tensor associated to the bilinear map $f(A,B) = A \cdot B$, in the basis of the coefficients, then look for a decomposition of it as a sum of rank-one tensors (i.e., those of the form $T_{i,j,k} = u_i v_j w_k$). You'll find this ...


4

This problem, which I'll call CO for Column Ordering, is NP-hard. Here's a reduction from the NP-hard problem Vertex Cover (VC) to it: Decision problem forms of VC and CO Let the input VC instance be $(V, E, k)$. It represents the question: "Given the graph $(V, E)$, is it possible to choose a set of at most $k$ vertices from $V$ such that every edge in $...


4

I will show you how you can improve the computational complexity of Tom's solution. Let's rewrite his recursive relationship: $$RR(N) = RR(N - 1) + 2BR(N - 1)$$ $$BR(N) = RR(N - 1) + BR(N - 1)$$ You can express this relationship using matrix multiplication. $ \left( \begin{array}{cc} RR(N) \\ BR(N) \end{array} \right) % = \left( \begin{array}{cc} 1 & ...


4

One can view this problem as a dynamic programming problem with $3N$ subproblems. Let $RR(N)$ be the number of solutions for a $2\times N$ matrix where the first row is colored with red-red, $RB(N)$ the number of solutions where the top cell is red and the bottom one blue, and $BR(N)$ the number of solutions where the top cell is blue and the bottom one red....


3

This answer fills the gap in the accepted answer by Tom van der Zanden, where the generating function is given by look-up magic without proper justification. This answer also produces the closed form of $RR(N)$. Here are the recurrence relations. $$\begin{align} RR(N)&=RR(N-1)+2BR(N-1) \tag{1}\\ BR(N)&=RR(N-1)+BR(N-1) \tag{2} \end{align}$$ ...


3

I am going to take a guess that you are having trouble with understanding how BFS will work on this game. First, you may wonder "what is the graph we are searching on?" Let's first start with, you are not searching through the game board. This is not what you are doing at all. How to represent Game State You are search through game states. I am using game ...


3

To complement Tom's answer: the coefficient of $x^n$ of the generating function $G(x)=\frac{1+x}{1-2x-x^2}$ is $$[x^n]G(x)=\frac{\sqrt{2}+1}{2}\left(\frac{1}{\sqrt{2}-1}\right)^n-\frac{\sqrt{2}-1}{2}\left(\frac{-1}{\sqrt{2}+1}\right)^n$$ so you have a closed form for the number of colorings. Note that this is the same as counting the number of (blue) ...


3

Efficient Generation of Random Nonsingular Matrices by Dana Randall covers exactly this topic. In particular Corollary 1.1 states: We can uniformly generate a matrix and its inverse in time $2M(n) + \mathbb{E}[O(n^2)]$. Where $M(n)$ is the time it takes to multiply two $n \times n$ matrices. Unfortunately this is not better than what you had hoped for.


3

What you want to do is view your problem as a problem on a directed layered graph. This will allow you to solve the problem using algorithms for the $k$-th shortest paths problem. In your example you would construct this graph: The arcs with no label have weight zero. Finding the $k$-th shortest paths from $s$ to $t$ will find the $k$ top scores ...


3

This is the perfect matching problem in a bipartite graph: construct a bipartite graph with nodes $1,...,N$ on one side and nodes $-1,...,-N$ on the other side, and with an edge from $i$ to $-j$ if your matrix has a 1 in row $i$, column $j$. Then a perfect matching in this graph corresponds to a subset of ones in the matrix having the property that no two of ...


2

Yes, "all of the propositional logical operators can be done with a unique binary 2×2 matrix". In fact, every possible map $g: \{0,1\}\times\{0,1\}\to\{0,1\}$ can be done with a unique binary 2x2 matrix. Here is a proof. $$\begin{align} &\quad \begin{bmatrix} X, \ \neg X \end{bmatrix}\begin{bmatrix} A & B\\ C & D\\ \end{bmatrix} \begin{...


2

It states that matrix powering is computationaly equivalent to computation. From another angle, Coppersmith–Winograd algorithm for matrix multiplication has complexity $\mathcal O(n^{2.373})$ and the same complexity is for determinant computation by fast multiplication. The result comes from Triangularization and inversion via fast multiplication by James R. ...


2

I don't know if there is actually a polynomial solution. Nevertheless based on Pål GD's comment, you can build a simplification function. The initial matrix is simplificated as you build the output sequence $S$. function simplification: while(true) if any row i$ has no 1 or no -1 left, remove it if any column j has no -1 then, remove it and ...


2

Yes, there are differences in accuracy since with machine numbers the usual properties of arithmetics don't hold. Machine numbers are defined as $$ F(\beta,t,m,M)= \{ 0 \} \cup \{ x \in \mathbb{R} : x = sign(x)\beta^{p} \sum_{i=1}^{t}d_i\beta^{-i},\ 0 \leq d_i \lt \beta\ ,\ d_1\ne 0\ , -m \le p \le M \} $$ and represent the subset of $\mathbb{R}$ that ...


2

Your image appears darker because standard RGB is used in transformation, with problem inherent to color - grayscale conversion as standard RGB transformation does not preserve luminance. Simple modification is to switch RGB channels to color space using perceived luminance: $Y = 0.299*R + 0.587*G + 0.114*B$. That way, luminance and chrominance blurring ...


2

Let $R=\{r_1, \cdots, r_n\}$ be the set of all rows. Let $C=\{c_1, \cdots, c_m\}$ be the set of all columns. If and only if the matrix entry at row $i$ and column $j$ is 1, we connect $r_i$ with $c_j$ with an edge. Now we have a bipartite graph $G=((R,C), V)$, since there is no edge between two rows nor between two columns. A vertex cover of $G$ ...


1

The problem of finding a Hamiltonian path in a partial grid graph (that is, an arbitrary subgraph of a grid, not necessarily even induced) remains NP-complete [1]. Thus, you are likely out of luck for a polynomial-time approach. A good choice for a heuristic might depend on your instance size and further structure. However, in general, you could try say a ...


1

I'm assuming that $W$ is an integer upper bound to $\sum_i w_i$, as asked by xskxzr, that all $w_i$ are positive integers, and that the values $w$ in the queries are also integers upper bounded by $W$. For $i \ge 1$, let $S[i,w]$ be the largest index $j \in \{1, \dots, i\}$ such that it is possible to select a subset of $\{w_k : j \le k \le i \}$ of weight ...


1

I won't go into the details of your specific case but try to answer the general problem. In the unrestricted case there is a mapping from each of the $n$ (=512) input states to one of 2 output states and you want to restrict the function as follows: Create a partitioning of the initial $n$ input states into subsets. Your adapted function maps each of these ...


1

For every point $(a,b)$ and number of steps $t \leq k$, compute inductively (i.e., using dynamic programming) the probability of reaching $(a,b) \neq (x,y)$ in $t$ steps without hitting $(x,y)$. Given this information, you can easily compute the probability of hitting $(x,y)$ in at most $k$ steps.


1

(Copied from a post on StackOverflow) Here's a simple approach: Start at the bottom-left corner. If the target is less than that value, it must be above us, so move up one. Otherwise we know that the target can't be in that column, so move right one. Goto 2. For an NxM array, this runs in O(N+M). I think it would be difficult to do better. :) Edit: ...


1

Look at the paper by Stephen Cook (numbered $[3]$ in the references of the paper you have mentioned). There, in proposition $5.2$ in page $13$, he shows the "computational equivalence" between matrix powering and determinant computation (and other problems).


1

This is the classic problem of matrix chain multiplication. Here is the pseudocode in Java from Wikipedia, which computes, for each $2 \le k \le n$, the minimum costs of all subsequences of length k using the costs of smaller subsequences already computed. It runs in $O(n^3)$, where $n$ is is the number of matrices, assuming the number of rows and columns ...


1

Snook, Counting bases of representable matroids shows that counting the number of maximal linearly independent subsets of columns is $\mathsf{\# P}$-complete. Your problem is probably also $\mathsf{\#P}$-complete. This suggests that you need an enumerative approach. On the other hand, you can efficiently (in theory) approximate the number of maximal ...


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