Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now
30

What you described is Voronoi diagram. Here is an excerpt from Wikipedia. In the simplest case, shown in the first picture, we are given a finite set of points ${p_1, \cdots, p_n}$ in the Euclidean plane. In this case each site $p_k$ is simply a point, and its corresponding Voronoi cell $R_k$ consists of every point in the Euclidean plane whose ...


8

The Misra-Gries summary is a simple technique which will find, for a given $k$, all elements in a sequence of $n$ elements which occur more than $\lfloor n/k \rfloor$ times, introduced in the 1982 paper Finding Repeated Elements as a generalization of the more well-known Boyer-Moore majority vote algorithm, which is essentially the case where $k = 2$. The ...


8

Its about pragmatic efficiency. The big-O notation tends to simplify many aspects of the machine that the algorithm is executing on. It leaves out the constant multipliers, and constant additions. It doesn't address that even those operations take variable amounts of time. Nor does it address the fact that implementations do not have an infinite/very very ...


7

Here is a simple algorithm to solve the problem as in Yuval's comment. Algorithm Input: A positive number $w$ and array $A$ of $m$ numbers, $A[0],\cdots, A[m-1]$. The first $n$ numbers of $A$ are non-decreasing positive numbers and the rest are 0s. Output: An index $k$ such that $A[k]=w$ or -1 if $w$ is not an element of $A$. Procedure: Check elements ...


6

This is essentially a Segment tree which is a data structure that augments an array with a binary tree as you describe such that: You have fast set and get at any index You have fast "aggregate" queries on ranges You can support fast update queries on ranges, for some combinations of updates and queries The $j$th node at height $k$ in the tree "summarizes" ...


5

A trie is asymptotically optimal for this. No data structure can achieve better asymptotic running time. If you care about constant factors, the only way to know what will be optimal is to try multiple approaches and benchmark them. Standard theoretical running time analysis is not reliable at predicting constant factors. Another data structure to ...


5

Since you know you're going to have to deal with all $2^{32}$ values eventually, you're going to need at least $2^{32}$ bits of memory, one for each value. The pigeonhole principle means that there's no possible way to store all the information you need with fewer bits than this. So I recommend a straightforward bitmap. In other words, a simple array of ...


5

That's probably a typo or poor wording -- in the quote, "has" should be "is".


5

Knuth gives a good overview on the history of lists and linked data structures. From The Art of Computer Programming, Volume I, Section 2.6: Linked memory techniques were really born when A. Newell, J. C. Shaw, and H. A. Simon began their investigations of heuristic problem-solving by machine.


5

This answer refers to the version of the question in which the interval $[l,r]$ refers to the values of the elements rather than their indices. Without preprocessing: You can extract all elements in the range $[l,r]$ in linear time. You can then use the linear time selection algorithm to find the $k$'th largest element, and then you can easily find the sum ...


4

I would like to propose my revisited version of Hiroki's answer. Currently it's been sitting in peer-review (https://cs.stackexchange.com/review/suggested-edits/66932) for a while, so it's not being of use to anyone. Credits to Hiroki for the original answer and structure. I've simply clarified the math and made every step explicit and chosen a slightly ...


4

It's unlikely that a data structure exists that supports both $insert(\cdot)$ and $find(\cdot)$ queries in $o(n/\log^2 n)$ time, since if it did, then we could use it to solve the 3SUM problem in $o(n^2/\log^2 n)$ time, beating the best known algorithm for this problem, which takes $O(n^2 (\log \log n)^{O(1)}/\log^2 n)$ time. In 3SUM, we are asked to find 3 ...


4

Suppose that every element is at most $k$ elements away from its true position. In order to sort the array, you maintain a heap. At step $i$, you add $A_i$ to the heap, and pop the minimum element as $A_{i-k}$. You do no popping in the first $k$ steps, and no adding in the last $k$ steps; there are $n+k$ steps in total. Since the heap is always of size $k+1$,...


4

This is something you will encounter over and over, not just in science but also in engineering, in law, in programming, and generally in jargon. If there is a definition for a term, then that term means exactly what the definition says it means. No more. No less. In particular, you may have an intuitive notion of what the term means in English, but this is ...


4

This answer refers to the version of the question in which the range $[l,r]$ refers to indices of the array, and in which we have $Q$ queries. The question asked whether we could beat $O(Qn\log n)$. Without preprocessing: Using the linear time selection algorithm, you can answer each query in $O(n)$, for a total of $O(Qn)$, which is better than $O(Qn\log n)$...


4

First note that $\text{increase-key}$ must be $O(\log n)$ if we wish for $\text{insert}$ and $\text{find-min}$ to stay $O(1)$ as they are in a Fibonacci heap. If it weren't you'd be able to sort in $O(n)$ time by doing $n$ $\text{insert}$s, followed by repeatedly using $\text{find-min}$ to get the minimum and then $\text{increase-key}$ on the head by $\...


4

As an exercise to the reader, two lemmas: Lemma 1. If $a, b$ are strings of symbols with a partial order, and $\text{numinv}$ counts the number of inversions in a string of symbols then $$\text{numinv}(ab) = \text{numinv}(a) + \text{numinv}(b) + \text{crossinv}(a, b)$$ where $$\text{crossinv}(a, b) = |\{(i,j) \in \{1,\dots,|a|\}\times\{1,\dots,|b|\} ...


4

If $k>N$, this cannot be done (as $\forall p_1,\dots, p_k\geq 0,\sum_{i=1}^k 2^{p_i}\geq k>N$) If $k\leq N$: Write $N$ in binary, and denote by $n$ the number of $1$s. We have written $N$ as a sum of $n$ powers of two (which happen to all be distinct). If $n\leq k$, then you can always split some of the powers of two (iteratively if needed) in order ...


4

This is only a sketch of solution (there might be some off-by-ones) Looking at a permutation of $\{1\ldots,n\}$ is equivalent at looking its inversion table $(a_1, \ldots, a_n)$ where $a_i$ is the number of elements to the left of $i$ that are greater than $i$. Basically that gives you a bijection between $S_n$ and $\prod_{1\le i\le n} \{0,\ldots,i-1\}$ and ...


3

Because they are using the pointer to access to an index of the array, hence the access time is constant. Moreover, as indices of the array are stored beside each other (to access in constant time), insertion to the array needs to extend the allocated storage of the array to insert a value, and it needs to copy all values of the array to the newly allocated ...


3

Here is a simple randomized $O(n)$ time algorithm. We start by rephrasing your problem slightly. Suppose that the original array is $a_1,\ldots,a_n$. Form a new array $b_0,\ldots,b_n$ containing the running sums of the previous array: $$ b_0 = 0, \qquad b_i = a_1 + \cdots + a_i. $$ Notice that $a_i + \cdots + a_j = b_j - b_{i-1}$. Therefore we can rephrase ...


3

You are looking for a Multi-Class Classification Algorithm. I suggest you have a look at: K-Nearest Neighbors algorithm (or KNN). Here is an introductory blog post. Support Vector Machines. You can start reading up on it here.


3

I think that many programmers would look at it in terms of the conversions between the two formats, and say that each format can be converted to the other losslessly, and that it's possible to make a round-trip without losing any data. It's not a standard usage, but if you said that the two formats were round-trippable wrt each other, you would probably be ...


3

Consider a SUBSET SUM instance with weights $w_1,\ldots,w_n$ and target $C$. We create an instance of your problem, with the same value of $C$. There are $n+1$ nodes $v_1,\ldots,v_n$, where node $v_i$ has cost and weight $w_i$. There is an edge from $v_i$ to $v_j$ iff $i < j$. Any directed path in this DAG corresponds to a subset of the weights $w_1,\...


3

Wikipedia describes a procedure, due to Floyd, which constructs a heap from an array in linear time. It also mentions a procedure for merging two heaps, of sizes $n$ and $k$, in time $O(k + \log k \log n)$. Altogether, we can add $k$ elements to a heap of length $n$ in time $O(k + \log k \log n)$: first build a heap containing $k$ elements to be inserted (...


3

A citation without too much consideration or research: heap bulk insert, Elmasry/Katajainen style (figure 3): procedure: bulk-insert input: $A[1..n_0+l]$: array; $n_0$: index; $l$: index data structures: $A[1..n_0]$: partial heap; $A[n_0+ 1..n_0+l]$: buffer $right$ ← $n_0+l$ $left$ ← $\max \{n_0+ 1, \lfloor (n_0 + l)/2 \rfloor\}$ while $right \ne 1$    $...


3

Answer #2. An alternative approach (arguably more elegant). This basically does the same operations as my other answer, just in a different order. It is as follows: build-tree(list A of length n): if n == 1: return singleton tree of the 1 element in A. let m be the median element of A # linear time select let L be all elements in A less than m ...


3

$\alpha$ indicates the Inverse Ackermann Function: $\alpha(n)$ is the number such that $A(\alpha(n), \alpha(n)) = n$. In practice, $\alpha(n) \lt 5$ for any input less than about $^72$. So $O(\alpha(n))$ is basically $O(1)$. The difference only matters in theory, never really in practice. You'll find $O(\alpha(n))$ mostly when working with disjoint sets, ...


3

The way it works is that your sets are connected components of the graph. You build such components incrementally, adding one edge at a time. When you add each edge, you ask if the vertices are part of the same component, if so then you have a cycle, if not, then you join the two components (perform a set union). Keep adding edges until you run out of them ...


3

An abstract data type (ADT) is an interface: it describes the operations that can be performed and what their externally visible behavior should be. There are typically many possible ways to implement that interface. A data structure is an implementation of such an interface: it provides code or fully specifies the internal behavior. A binary search tree ...


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