6

Hint #1: Hint #2:


6

This problem is known as discrete tomography, and in your case two-dimensional discrete tomography. A nice approachable introduction is written Arjen Pieter Stolk's thesis Discrete tomography for integer-valued functions in Chapter 1. It gives a simple greedy algorithm for solving this problem: While the proof of theorem (1.1.13) is somewhat involved, the ...


4

Copied from here. The mathematics Consider the group $G=S_w\times S_h$, where $S_w$ and $S_h$ are the symmetric group of the sets $W=\{1,2,3,\ldots,w\}$ and $H=\{1,2,3,\ldots,h\}$ with $w$ and $h$ elements, respectively. The group $G$ acts on the set $X=W\times H$, which we view as the set of indexes of the entries of the matrices. Each matrix is a function ...


4

The problem is NP-hard; it is at least as hard as the biclique problem. If you can solve the problem for a single shaped box, you can solve for all boxes by just iterating over all the boxes. So your problem reduces to: Given a matrix $M$ and integers $h', w'$, find a $h'\times w'$ submatrix of $M$ that is all ones, or report that none exists. This ...


3

I would consider a sentence such as this to be unambiguous: We flattened the $h \times w \times 3$ input data down to a two-dimensional $hw \times 3$ shape. I don't believe a reference explaining this would be necessary.


3

There is an easy reduction from the well-known NP-complete problem MAX-CLIQUE to your problem. Recall that in MAX-CLIQUE we are given a graph $G$ and an integer $k$, and have to decide whether $G$ contains a $k$-clique. We can recast this as an instance of your problem as follows: the matrix $A$ is the adjacency matrix of your graph, and the goal is to ...


3

We can imagine simulating the random walk on an infinite line, keeping track of the "extension", which is the distance between the rightmost point visited and the leftmost point visited. Let $\ell(a,b)$ denote the probability that the extension became $b-a$ due to a move to $a$, and let $r(a,b)$ denote the probability that the extension became $b-a$ due to a ...


2

Try building a summed area tableā€”a table where the value in each cell is the sum of all the values above and to the left, inclusive, of the cell in the original table. See if you can figure out an $O(n^2)$ solution from that.


2

Suppose that if $N = 2^c$ then you can multiply two $N \times N$ matrices in time $O(N^{\log_2 7})$. For concreteness, let us say that two such matrices can be multiplied in time at most $CN^{\log_27}$. Now suppose that we are given two $n\times n$ matrices. We pad them to $N \times N$ matrices, where $N = 2^{\lceil \log_2 n \rceil} < 2n$. We can extract ...


1

It's unnecessary to perform an LU factorization each time. Instead, you can compute a projection matrix $P$ from your dense matrix. Then, for any vector $x$ in your set, just check if $Px = x$. In particular, suppose your original dense matrix $A^T$ has all of its rows independent (if it doesn't just delete rows until it does) and you wanted to know if ...


1

Based on the, apparently famous paper on the field, Ryser 56, and the thesis recommended by @orlp, the test to know if a row and column sum vectors forms a match, e.g., a matrix $M_{h,w}$ exists having these row and column sum vectors, is the following one: Let $R_h$ be a vector of $h$ elements sorted in a non-increasing order ($r_1\geq r_2\geq\ldots\geq ...


1

Let $U$ be the set of rows in the given matrix and $V$ the set of columns. For each $x$ at row $i$ and column $j$, add an edge between row $i$ and column $j$. You will have an (unweighted) bipartite graph $G=(U,V, E)$. The problem is to find a perfect matching, which is basically the same as find the maximum matching of $G$. There are various algorithms that ...


1

This is no different than asking for an algorithm for deciding if the entries of an array contain a nonzero. So what you describe is optimal, i.e. an adversary argument shows that any algorithm must examine each entry for otherwise you can't know for sure.


1

There is no algorithm with worst-case running time better than $O(n^2)$. There is a simple adversary argument to prove this. Consider any algorithm that is purported to be correct, and that always inspects fewer than $n^2$ entries of the matrix. Thus, there must always be some entry that is uninspected. Consider a matrix that has 1's in the entire first ...


1

If the matrix has two distinct eigenvalues, you can find them using power iteration. Let $\lambda_1,\lambda_2$ be the 2 eigenvalues, where $|\lambda_1| > |\lambda_2|$. Then you can use power iteration to find $\lambda_1$. Next, set $A' = A - \lambda_1 \text{Id}$. $A'$ is a symmetric matrix with eigenvalues $\lambda_2,0$, so power iteration on $A'$ ...


1

These are called Catalan numbers, and the term $\binom{2N}{N}$ is called a central binomial coefficient. There are several formulas for these numbers which can be used to compute them efficiently, such as the one you present, or $$C_n = \prod_{k=2}^n \frac{n+k}{k}$$ The problem with writing down the time complexity for computing these numbers is that the ...


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