129 votes
Accepted

What are the reasons to learn different algorithms / data structures serving the same purpose?

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 ...
Pseudonym's user avatar
  • 22.1k
127 votes
Accepted

Why is it best to use a prime number as a mod in a hashing function?

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 ...
Mario Cervera's user avatar
52 votes

What are the reasons to learn different algorithms / data structures serving the same purpose?

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 ...
Raphael's user avatar
  • 72.4k
45 votes
Accepted

Why is data in computer science considered to be discrete?

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, ...
AnoE's user avatar
  • 1,273
44 votes
Accepted

Is there an existing data structure that is of fixed size, and will push the oldest/last element out if a new element is inserted?

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 ...
Raphael's user avatar
  • 72.4k
44 votes
Accepted

Will hardware/implementation affect the time/space complexity of algorithms?

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 ...
D.W.'s user avatar
  • 159k
36 votes
Accepted

What is the difference between radix trees and Patricia tries?

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 ...
Mario Cervera's user avatar
33 votes

What is this data structure/concept where a plot of points defines a partition to a space

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 ...
John L.'s user avatar
  • 39k
30 votes

Why is data in computer science considered to be discrete?

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 ...
Christian Matt's user avatar
29 votes
Accepted

What is the advantage of heaps over sorted arrays?

$\small \texttt{find-min}$ (resp. $\small \texttt{find-max}$), $\small \texttt{delete-min}$ (resp. $\small \texttt{delete-max}$) and $\small \texttt{insert}$ are the three most important operations of ...
PSPACEhard's user avatar
29 votes
Accepted

Data structure for fast insertion and fast random element removal

You can achieve constant amortized time per operation by keeping a dynamically-sized array $A$ (using the doubling/halving technique). To insert an element append it at the end. To implement ...
Steven's user avatar
  • 29.5k
29 votes
Accepted

Why are graphs represented as adjacency lists instead of adjacency sets?

In many algorithms we don't need to check whether two vertices are adjacent, like in search algorithms, DFS, BFS, Dijkstra's, and many other algorithms. In the cases where we only need to enumerate ...
Pål GD's user avatar
  • 16.1k
24 votes

How to find middle element of linked list in one pass?

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 ...
Hendrik Jan's user avatar
  • 30.6k
24 votes

When are adjacency lists or matrices the better choice?

First of all note that sparse means that you have very few edges, and dense means many edges, or almost complete graph. In a complete graph you have $n(n-1)/2$ edges, where $n$ is the number of nodes. ...
fade2black's user avatar
  • 9,837
21 votes

Is Group Theory useful in Computer Science in areas other than cryptography?

Algorithms for isomorphism problems such as graph isomorphism rely heavily on group theory. An unusual example of group theory applied to computer science is the famous proof of Barrington's theorem, ...
Aaron Rotenberg's user avatar
18 votes
Accepted

Why is the Java HashMap load factor 0.75?

I don't know the answer, but I can walk you through what might be going through the mind of someone designing such a data structure. Assuming a "good" hash function, and that $n$ is large ...
Pseudonym's user avatar
  • 22.1k
17 votes
Accepted

Why is the inverted index called so and not simply index?

Here is an array: A[0] = Alice A[1] = Bob A[2] = Charlie Here 0,1,2 are indices. Now suppose that we want to know which index contains a given word. Then we use a dictionary: D[Alice] = 0 D[Bob] = ...
Yuval Filmus's user avatar
16 votes
Accepted

Finding k'th smallest element from a given sequence only with O(k) memory O(n) time

Create a buffer of size $2k$. Read in $2k$ elements from the array. Use a linear-time selection algorithm to partition the buffer so that the $k$ smallest elements are first; this takes $O(k)$ time. ...
jbapple's user avatar
  • 3,380
16 votes
Accepted

Does every data type just boil down to nodes with pointers?

Well, that is basically what all data structures boil down to. Data with connections. The nodes are all artificial - they don't actually exist physically. This is where the binary part comes in. You ...
user3853544's user avatar
16 votes

Why use binary search trees when hash tables exist?

The most obvious answer is that trees can be traversed in their natural order very efficiently. If you need to visit every element of a dictionary in alphabetical order, a tree can support this ...
ddyer's user avatar
  • 379
15 votes

Why are Red-Black trees so popular?

I've been researching this topic recently as well, so here are my findings, but keep in mind that I am not an expert in data structures! There are some cases where you can't use B-trees at all. One ...
matklad's user avatar
  • 151
15 votes

Does every data type just boil down to nodes with pointers?

It seems like every data concept can always boil down to just nodes with pointers to some other appropriate node. Oh, dear no. You are hurting me. Like I tried to explain elsewhere ("What's the ...
Hendrik Jan's user avatar
  • 30.6k
15 votes

Data structure or algorithm for quickly finding differences between strings

My solution is similar to j_random_hacker's but uses only a single hash set. I would create a hash set of strings. For each string in the input, add to the set $k$ strings. In each of these strings ...
Simon Prins's user avatar
15 votes
Accepted

Incremental strongly connected components

To the best of my knowledge, the best algorithm for decremental strongly connected components is presented in [1] with $O(m \sqrt{n} \log n)$ total expected update time. [1] Decremental Single-...
Alexander Svozil's user avatar
15 votes
Accepted

Why use heap over red-black tree?

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 ...
Kain0_0's user avatar
  • 291
15 votes

Is Group Theory useful in Computer Science in areas other than cryptography?

Group theory is indeed useful in algorithm design. For example, matrix multiplication is a fundamental problem for which such approaches have been used (see e.g., Cohn et al. [1] or these lecture ...
Juho's user avatar
  • 22.6k
15 votes

Data structure for fast insertion and fast random element removal

Since you clearly don't care about the order of elements changing, I think the simplest approach is to use a resizable array (like C++'s std::vector or Java's ...
ruakh's user avatar
  • 633
14 votes
Accepted

What does "map" mean?

So, there are two distinct uses of the word "map", that I'll unpack here. The first is very generic, where map means "to associate," particularly by way of a function. If we say "$f$ maps each $x$ to ...
Joey Eremondi's user avatar
13 votes
Accepted

Find all values repeating more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time

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 ...
rici's user avatar
  • 12k
12 votes
Accepted

Why is b-tree search O(log n)?

You have introduced $n$ and $m$ as the order of B-tree, I will stick to $m$. Their height will be in the best case $\lceil log_m(N + 1) \rceil$, and the worst case is height $\lceil log_{\frac{m}{2}}(...
Evil's user avatar
  • 9,455

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