Tag Info

3

Your random number generator might not be able to produce all numbers. Without looking at Math.Random, if it returned an integer then it would never match 0.123456. If it returned a double precision floating point number 0 <= rnd < 1, it might produce a 53 bit integer from 0 to 2^53-1, and multiply by 2^-53. In this case it is quite possible that 0....

2

I don't know much about the amortized running time of binomial heap, but after reading Wikipedia, I suspect the following might be true: the amortized time of a long sequence of consecutive insert operations is $O(1)$; but this is only true for consecutive insert operations that don't have any other operations mixed in. Based on that, I wouldn't really ...

2

The disproof is wrong because in your Red-Black tree, all possible leaves need to be represented (see exemples on wikipedia). That means that the real tree represented should be: It is easy to see that it does not respect the fourth condition of the definition. In the claim, when it is said that: a key […] has exactly one child (which isn't null) it ...

2

By noticing that $H$ remains a tree except when $H \gets H \cup (a,b)$ happens, you can use a ST-Tree[1], which you can easily modify to support queries of the form "what is the maximum weight edge on the path from $a$ to $b$" Instead of adding $(a,b)$ directly to $H$ first you check if $a$ and $b$ are connected (using the ST-Tree or a Union-Find)...

2

In the book Kernelization by Fomin, Lokshtanov, Saurabh, Zehavi (which is downloadable as a PDF on the first author's homepage) you find Chapter 4. Crown decomposition. This should point you to the answer.

2

You need to decide what sort of resilience you are expecting from your hash function. While it is true that once picked, your hash function does not change (and in a sense "the rest of the family doesn't exist") but you're ignoring the crucial part of picking the function at random. Suppose that $\mathcal{H}\subseteq U^{[m]}$ is a universal family, ...

2

The running time of quicksort satisfies the recurrence $$T(n) \leq \max_{n_1+n_2+1=n} T(n_1) + T(n_2) + Cn,$$ with base cases of $T(1) = C$ and $T(0) = 0$, say. Let us now prove by induction that $T(n) \leq Cn^2$. The base cases obviously hold. As for the inductive step, \begin{align} T(n) &\leq \max_{n_1+n_2+1=n} C(n_1^2 + n_2^2) + Cn \\ &= \max_{...

2

For the first task you can use a solution similar to yours. Let the input array be $A[1, \dots n]$. Create an array $B$ indexed with the integers from $10$ to $10n$ where each entry is a boolean value initially set to false. Then, for each input element $A[i]$, set $B[A[i]]$ to true. At the end of the above loop, return the number of indices $y$ such that $B[... 1 I am not sure counting sort would work, since it does not depend on the base, but on the range of the sorted values. In this case, you would need to create an array of size$(n-1)\sqrt{n}$to count, so you would be in$\Omega(n^{3/2})$. As suggested in the comment, radix sort may do the trick here. It is not possible to sort in$O(n)$for one of the other ... 1 It probably means "the number of array elements whose value is between$a$and$b$". For the solution, it is crucial that the number of possible values of array elements is$O(1)$. 1 You can solve the second task with$O(n)$expected running time (average-case running time), if you use a hash table with a 2-universal hash function. As far as I know, no deterministic$O(n)$-time algorithm is known. 1 Well, it technically is possible (with a small caveat). This is due to the fact a computer has finite memory, and hence cannot represent all possible numbers, but rather only a very very small fraction of them (and thus the probability to "hit" some particular number it can represent is not 0). However, it still depends on the random function's ... 1 A possibility (don't think it's the simplest way, though) is: Transform the array into a max-heap; find (without extracting) the$\log n$largests elements in the heap. The first step can be done in$O(n)$. For the second step, let's give a little bit details: The largest element is found among one element (it's the root); the second largest must be found ... 1 If I understand correctly the title (which is a bit clearer than the post itself), an example of such an array would be$[1, 4, 1, 2, 1, 2, 5, 2, 1, 1, 4, 1, 2, 1, 1]$. If that's the case, you can: Count the number of occurrences of each value, with a hashtable for example; Sort the unique values with descending order of occurrences; Recreate the sorted ... 1 Since$T(n)=T(n-1)$, using induction we can prove that$T(n)= 1 + \sum_{k=1}^n k(k-1) \le 2\sum_{k=1}^n k(k-1)$Now, calculating$\sum_{k=1}^n k(k-1)$gives us:$\sum_{k=1}^n k(k-1)=\sum_{k=1}^n (k^2 - k) = \sum_{k=1}^n k^2 - \sum_{k=1}^n k$Using this formula, we know that$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$, and its not hard to show that$\sum_{k=1}...

1

Given a line $L = b$, the distance from any point $(x, y)$ to $L$ is $\left| y - b\right|$. The sum of a distances for a set of points $S = \{(x_1, y_1), \dots, (x_n, y_n)\}$ is then $$\left| y_1 - b \right| + \cdots + \left| y_n - b \right|$$ which is minimized for which $b$?

1

The minimum element will the root. So in constant time you can find the minimum element. Delete the minimum element from the root. Now min-heapify (make it minheap) the resultant tree. The second minimum element will be the root again. Repeat the procedure mentioned above. By this procedure, you will find $k$-th minimum element in time $O(k \log n)$ where $n$...

1

The short answer is yes. Because of information theoretical bounds, any probabilistic data structure representing a set that stores arbitrarily large keys with bounded space per key and lets you query arbitrary data for membership must use $\log_2(1/\epsilon)$ bits per inserted element, where $\epsilon$ is the false positive rate. Afaik, optimal bloom ...

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