Tag Info

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

7

Despite common belief, maintaining the maximum (or minimum) element out of the last $k$ elements does not involve a $O(\log k)$ factor, and can be done in amortized $O(1)$. Using this twice (once for max and once for min) you can solve your problem in $O(n)$. The trick is done using a monotonic double-ended queue, one where all the elements are either in ...

6

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

6

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

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

5

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

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

5

No, the term doesn't have a formal definition. You might be interested in the notion of an abstract data type, which does have a formalization.

4

$\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, ...

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 ... 4 Augment the tree to store, for each subtree, the minimum of the prefix sums of the sequence of elements in that subtree. Then you can check the supergood condition in$O(\log n)$time. It's your exercise, so I'll let you work out the details. Hint #1: every prefix can be decomposed into a union of$O(\log n)$subtrees. Hint #2: the minimum of the prefix-... 4 Arrays and linked lists are indeed simple data structures, but they are not more "fundamental" than other data structures. Everything in software is built out of contiguous memory to which the CPU has random access by address. All data structures are just abstractions built on top of that foundation. A tree data structure is not composed of arrays and ... 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+lleft$←$\max \{n_0+ 1, \lfloor (n_0 + l)/2 \rfloor\}$while$right \ne 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

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

My vote is on (4) from an intuition point of view. I just started learning this recently so take this with a grain of salt but as mentioned by D.W. the set of states can be anything you want. It is an abstract concept. However, it is natural to think of states as being valuations of the variables in the system. For example, we may think of the current state ...

3

There is an $O(k)$ algorithm [1]. [1] Frederickson, G. N. (1993). An optimal algorithm for selection in a min-heap. Information and Computation, 104(2), 197-214.

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

3

This approach suggest to pick any constant factor $k>1$ and use that whenever one needs to reallocate the array. That is, each time the array becomes full and has $n$ elements, a new array of size $k\cdot n$ is allocated, and data is copied from the old array. It is important here to multiply the size by a constant $k$ rather than, say, adding a fixed ...

3

You must refer to the definition of a Binary Heap: A Binary heap is by definition a complete binary tree ,that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right. It is by definition that it is never unbalanced. The ...

3

In an email with one of the authors it became clear that the following pseudo-code rule applies. (this is not an actual quote, but the format seems better for this) Whenever there is an else clause. The first statement of that else clause will be on the same line as the else clause. This can be a variable assignment, an if-statement or other things. If ...

3

MinHash already is super-fast. I suggest you check whether you understand correctly how MinHash works. Take any standard hash function $H$; then all you have to do is compute $H$ once on each element of the set. You can implement $H$ with as fast a hash algorithm as you want. The update operation requires one call to $H$ (namely, if your set's hash is ...

3

Assuming that the three dependencies are a cover of the dependencies of the relation schema R, to find all the candidate keys we could start from a canonical cover of the FDs, for instance the following one: { A B C → D A B C → F D E F → A D E F → C D → B } From these dependencies we can see that E must belong to all the candidate keys, since it ...

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