4

It looks like magic because the proof of Kirchhoff's Matrix Tree Theorem is nontrivial. It relies on several algebraic properties of the matrix constructed in steps 1-3, which is called the Laplacian matrix of the graph. Let $A$ be the adjacency matrix, and let $D$ be the diagonal matrix with the degrees of the nodes on the diagonal. Steps 1-3 build the ...


3

If you want just some basic ideas what you might test. The simplest test just generates a million random numbers and puts them into say 100 buckets depending on their value. Each bucket should contain about 10,000 random numbers. If not, your random number generator is off. However, just generating 1, 2, 3, 4, 5, ... will pass this test, so it's not a very ...


2

Use the product construction to build a graph on $NK$ vertices and $MK$ edges, where each vertex records both which island you are at and how much hull you have left. Then, use Dijkstra's algorithm on that graph. The graph can be built on the fly and does not need to be constructed explicitly.


2

I can't argue with the second paragraph of D.W.'s answer, and D.W. is right that all tests have limitations: That's intrinsic to PRNG-testing. But TestU01 is still pretty much state of the art. You can use the NIST suite, too, which includes some tests not in TestU01, I believe. You might want to skim L'Ecuyer and Simard's paper on TestU01 and O'Neill's ...


2

In order to compare two quantities/expression, it is often easier if they are in the same form. Here try expressing $t_a(n)$ as $2^{s_a(n)}$ and compare $s_a(n)$ with $\sqrt{\log_2 n}$. Additionally, beware of using a program to check asymptotic comparisons: e.g. $f(n)=n^{10^6}$ and $g(n)=(1,0000000000000001)^n$


1

The proof is by induction. The base case $t = k$ is clear. Suppose that the claim is true at some time $t$. We will prove it for time $t+1$. Let the first $t+1$ elements be $x_1,\ldots,x_{t+1}$. By the induction hypothesis, at time $t$ each of the $\binom{t}{k}$ possible $k$-subsets of $x_1,\ldots,x_t$ is found in the array with equal probability. The ...


1

This algorithm runs in linear time in the size of the input $O(n)$. To see why try to count how many times you read/write to a position in the string. Note that asymptotically this is equal to the total running time.


1

So you suggested the basic technique of checking all pairs which is $O(mn^2)$. Here are some things you can try first, at lower complexity, before falling back to an approach with a similar worst-case bound but likely better constants. We represent each point $p_i = (x^i_1, \dots, x^i_m)$. Then clearly there is a dominated pair if $\min_i \max_j x^i_j \leq ...


1

There is no deterministic algorithm whose worst-case running time is asymptotically better than $O(N^2)$. One can prove this with an adversarial argument. Consider running the algorithm on the following input: Input #1: $F(x_i,x_i)=1$, and $F(x_i,x_j)=0$ if $i \ne j$. Keep track of the sequence of pairs $(x_i,x_j)$ of objects that $F$ is evaluated on ...


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