New answers tagged

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$


0

I've found the conceptual problem. In a BFS kind of search, when optimization is needed because the length of the queue grows at critical speed, you have to take track of the visited items. The goal is to avoid adding another item to the queue when it is already present a better item there. Just some code, only to clarify the concept. In my case I've ...


0

For detailed analysis of complexity see: https://11011110.github.io/blog/2008/01/10/analyzing-algorithm-x.html


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


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


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

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

Yes, using sorting algorithms like merge sort we can achieve this by O(N*logN) we can do better here. The additional information given regarding the bound of test scores is very useful here. do we care about duplicates ? if we are dealing with just scores and doesn't care about the other information like student_name or subject_info and we just want the ...


8

This is a very easy question, assuming all scores are integers. Here is the simplest algorithm in plain words. We will initiate count, an integer array of 100 zeros. For each score s, we will add 1 to count[s]. To produce the wanted sorted scores, we will output count[1] 1s, count[2] 2s, ..., and finally count[100] 100s. This kind of sorting algorithm is ...


4

Here is an illustration. The graph is a slight modification on your example of $ K_{2n,2n}$. It is the complete bipartite graph of vertices sets $\{0,1,2,\cdots, 2n-1\}$ and $\{2n, 2n+1,\cdots, 4n-1\}$, plus edges $\{0,2n-1\}, \{1, 2n-2\}, \cdots, \{n-1, n\}$, $\{2n, 4n-1\}, \{2n+1, 4n-2\}, \cdots, \{3n-1,4n\}$. The initial cut is shown by that red line in ...


5

Let's denote by $u_1,\ldots,u_{2n}$ and $v_1,\ldots,v_{2n}$ the nodes in the two sides of $K_{2n,2n}$ respectively. We remove the $2n$ edges $(u_1,v_1),(u_2,v_2),\ldots,(u_{2n},v_{2n})$ from $K_{2n,2n}$. You can verify the resulting graph is an example showing the approximation ratio of your algorithm is at least $2-1/n$, when the initial cut is $\left(\{u_1,...


Top 50 recent answers are included