# Tag Info

122

There's a textbook waiting to be written at some point, with the working title Data Structures, Algorithms, and Tradeoffs. Almost every algorithm or data structure which you're likely to learn at the undergraduate level has some feature which makes it better for some applications than others. Let's take sorting as an example, since everyone is familiar with ...

66

Heap just guarantees that elements on higher levels are greater (for max-heap) or smaller (for min-heap) than elements on lower levels, whereas BST guarantees order (from "left" to "right"). If you want sorted elements, go with BST.by Dante is not a geek Heap is better at findMin/findMax (O(1)), while BST is good at all finds (O(logN)). Insert is O(logN)...

63

Consider the set of keys $K=\{0,1,...,100\}$ and a hash table where the number of buckets is $m=12$. Since $3$ is a factor of $12$, the keys that are multiples of $3$ will be hashed to buckets that are multiples of $3$: Keys $\{0,12,24,36,...\}$ will be hashed to bucket $0$. Keys $\{3,15,27,39,...\}$ will be hashed to bucket $3$. Keys $\{6,18,30,42,...\}$ ...

51

Aside from the fact that there are myriads of cost measures (running time, memory usage, cache misses, branch mispredictions, implementation complexity, feasibility of verification...) on myriads of machine models (TM, RAM, PRAM,...), average-vs-worst-case as well as amortization considerations to weigh against each other, there are often also functional ...

44

Answer why was the data considered to be a discrete mathematical entity rather than a continuous one This was not a choice; it is theoretically and practically impossible to represent continuous, concrete values in a digital computer, or actually in any kind of calculation. Note that "discrete" does not mean "integer" or something like that. "discrete" ...

44

Fixed-size queues are often implemented using what some people call circular buffers. If you remove the protection against it being full, you get the desired behaviour. Of course, no actual pushing will happen in the array -- that would be too expensive -- but it will look like it from the outside.

42

There are two settings under which you can get $O(1)$ worst-case times. If your setup is static, then FKS hashing will get you worst-case $O(1)$ guarantees. But as you indicated, your setting isn't static. If you use Cuckoo hashing, then queries and deletes are $O(1)$ worst-case, but insertion is only $O(1)$ expected. Cuckoo hashing works quite well if you ...

42

Sure. Certainly. Here's how to reconcile your discomfort. When we analyze the running time of algorithms, we do it with respect to a particular model of computation. The model of computation specifies things like the time it takes to perform each basic operation (is an array lookup $O(\log n)$ time or $O(1)$ time?). The running time of the algorithm ...

34

Both binary search trees and binary heaps are tree-based data structures. Heaps require the nodes to have a priority over their children. In a max heap, each node's children must be less than itself. This is the opposite for a min heap: Binary search trees (BST) follow a specific ordering (pre-order, in-order, post-order) among sibling nodes. The tree must ...

33

NO. Fredman and Saks proved that any data structure that supports these operations requires at least $\Omega(\log n/\log\log n)$ amortized time per operation. (This is reference [1] in the paper by Dietz that you mention in your first comment.) The lower bound holds in the very powerful cell probe model of computation, which only considers the number of ...

33

Summary Type BST (*) Heap Insert average log(n) 1 Insert worst log(n) log(n) or n (***) Find any worst log(n) n Find max worst 1 (**) 1 Create worst n log(n) n Delete worst log(n) log(n) All average times on this table are the same as their worst times except for Insert. *: everywhere in ...

31

Claim: Red-black trees can be arbitrarily un-$\mu$-balanced. Proof Idea: Fill the right subtree with as many nodes as possible and the left with as few nodes as possible for a given number $k$ of black nodes on every root-leaf path. Proof: Define a sequence $T_k$ of red-black trees so that $T_k$ has $k$ black nodes on every path from the root to any (...

30

The simpler balancing algorithm can require $\Omega(n)$ amortized time per rotation in the worst case. Suppose the tree is just a totally unbalanced path of right children; no node has a left child. The only leaf in this tree is the tree with the maximum key. If you rotate this step by step up to the root, you've used $n-1$ rotations, and the resulting ...

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

29

Computers represent a piece of data as a finite number of bits (zeros and ones) and the set of all finite bit strings is discrete. You can only work with, say, real numbers if you find some finite representation for them. For example, you can say "this data corresponds to the number $\pi$", but you cannot store all digits of $\pi$ in a computer. Hence, ...

27

Our idea is to use threaded splay trees. Other than the Wikipedia article we will thread the trees so that every node has a pointer next to its successor in the in-order traversal; we also hold a pointer start to the smallest element in the tree. It is easy to see that extracting the smallest element is possible in (worst case) time $\mathcal{O}(1)$: just ...

26

A whole treatise could be written on this topic; I'm just going to cover some salient points, and I'll keep the discussion of other data structures to a minimum (there are many variants indeed). Throughout this answer, $n$ is the number of keys in the dictionary. The short answer is that hash tables are faster in most cases, but can be very bad at their ...

24

As far as I'm concerned, null, nil, none and nothing are common names for the same concept: a value which represents the “absence of a value”, and which is present in many different types (called nullable types). This value is typically used where a value is normally present, but may be omitted, for example an optional parameter. Different programming ...

24

By cheating, and doing two passes at the same time, in parallel. But I do not know whether the recruiters will like this. Can be done on a single linked list, with a nice trick. Two pointers travel over the list, one with double speed. When the fast one reaches the end, the other one is half-way.

23

I found this post very helpful. To see the difference between Patricia tries and radix trees, it is important to understand: The notion of radix, since Patricia tries are radix trees with radix equal to 2. The way keys are treated: as streams of bits. Keys are compared $r$ bits at a time, where $2^r$ is the radix of the trie. Suppose that we insert the ...

22

This answer summarises parts of TAoCP Vol 3, Ch 6.4. Assume we have a set of values $V$, $n$ of which we want to store in an array $A$ of size $m$. We employ a hash function $h : V \to [0..M)$; typically, $M \ll |V|$. We call $\alpha = \frac{n}{m}$ the load factor of $A$. Here, we will assume the natural $m=M$; in practical scenarios, we have $m \ll M$, ...

22

I did not find a closed form, but according to this entry in the Online Encyclopedia of Integer Sequences the sequence starts with 1, 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, 19200, 79200, 506880, 2745600, 21964800, 108108000, 820019200, 5227622400, 48881664000, 319258368000, ... You can find a not-so-nice recursion in the OEIS database. Basically the idea ...

22

Positive result: persistence does not cost too much. One can show that every data structure can be made fully persistent with at most a $O(\lg n)$ slowdown. Proof: You can take an array and make it persistent using standard data structures (e.g., a balanced binary tree; see the end of this answer for a bit more detail). This incurs a $O(\lg n)$ slowdown: ...

20

Insert: $\mathcal{O}(\log n)$ Get-Min: $\mathcal{O}(1)$ Extract-Min: $\mathcal{O}(1)$ Amortized Time Simple implementations of a priority queue (e.g. any balanced BST, or the standard binary min-heap) can achieve these (amortized) running times by simply charging the cost of Extract-Min to insert, and maintaining a pointer to the minimum element. For ...

20

Let's first think about this intuitively. In the best-case scenario, the tree is perfectly balanced; in the worst-case scenario, the tree is entirely unbalanced: Starting from the root node $p$, this left tree has twice as many nodes at each succeeding depth, such that the tree has $n=\sum_{i=0}^{h}2^i =2^{h+1}-1$ nodes and a height $h$ (which is in this ...

19

When you work with immutable data objects, functions have the property that every time you call them with the same inputs, they produce the same outputs. This makes it easier to conceptualize computations and get them right. It also makes them easier to test. That is just a start. Since mathematics has long worked with functions, there are plenty of ...

18

Claim: No, there is no such $\mu$. Proof: We give an infinite sequence of AVL trees of growing size whose weight-balance value tends to $0$, contradicting the claim. Let $C_h$ the complete tree of height $h$; it has $2^{h+1}-1$ nodes. Let $S_h$ the Fibonacci tree of height $h$; it has $F_{h+2} - 1$ nodes. [1,2,TAoCP 3] Now let $(T_h)_{i\geq 1}$ with $T_h ... 18 What you are looking for is "approximate near neighbor search" (ANNS) in the Levenshtein/edit distance. From a theoretical perspective, edit distance has so far turned out to be relatively hard for near-neighbor searches, afaik. Still, there are many results, see the references in this Ostrovsky and Rabani paper. If you are willing to consider alternative ... 18 First encode natural numbers and pairs, as described by jmad. Represent an integer$k$as a pair of natural numbers$(a,b)$such that$k = a - b$. Then you can define the usual operations on integers as (using Haskell notation for$\lambda\$-calculus): neg = \k -> (snd k, fst k) add = \k m -> (fst k + fst m, snd k + snd m) sub = \k m -> add k (neg ...

18

A Fenwick tree is a binary tree used to efficiently handle cumulative frequencies or sums in an array. Without loss of generality we shall examine a 16-element array. Imagine a binary tree imposed on top of the array. Furthermore, label all the left edges in this tree with a "0" and all the right edges with a "1". We get something like this: This is the so ...

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