23
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. ...
- 9,612
10
votes
Accepted
What's the fastest way to find the Kth smallest value in an unsorted list without sorting?
Use selection algorithm for linear time https://en.m.wikipedia.org/wiki/Selection_algorithm
- 1,086
10
votes
Accepted
Skip List randomization complexity
According to the hint, the number of elements in the levels beyond the first is expected to be
$$
n \cdot (1/2 + 1/4 + \cdots + 1/2^k).
$$
Presumably, $k \approx \log n$, though as we will see, this ...
- 270k
9
votes
Accepted
The fastest algorithm for intersection of two sorted lists?
Hwang and Lin's Algorithm (A simple algorithm for merging two disjoint linearly-ordered sets (1972) by F. K. Hwang , S. Lin) is the reference on how to merge (or intersect) ordered lists of unequal ...
- 1,254
8
votes
Accepted
The origin of list data structure
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,...
- 590
8
votes
Accepted
Sorting a large list of test scores
This is a very easy question, assuming all scores are integers.
Here is the simplest algorithm in plain words. We will initiate count, an integer array of 100 ...
- 34.1k
7
votes
Accepted
Finding number not in list with wildcards
Reduce from SAT. Consider a CNF formula $\phi = C_1 \land C_2 \land \ldots \land C_m$ over a set of variables $\{x_i\}_{i=1}^n$. Construct an instance of your problem as follows:
For each clause $C_i$...
- 2,190
6
votes
Accepted
Description of lists with functions in LISP
In PL theory, this is known as (a variant of) the Church-encoding of pairs.
The idea is the following: assume for the moment you only have a language with primitive booleans (true, false, if-then-...
- 14.2k
6
votes
Accepted
Find out duplicate number between 1 to N numbers
Here is the question:
You are given a list of length $n+1$ which contains the numbers $1,\ldots,n$, one of them appearing twice (and the rest appearing once).
Find the number which appears twice.
...
- 270k
6
votes
Accepted
Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?
For simplicity , assume the grid is a square $N \times N$ grid and $N$ is a prime.
Its easy to see that from each row we can pick $\leq 2$ points only , so the maximum number of points we can chose ...
- 111
6
votes
Accepted
How to best maintain a sorted list from a stream of integers?
A balanced binary search tree can support access to arbitrary elements in $O(\log N)$ time per access. Augment the data structure to store, in each node, the number of values stored in the subtree ...
D.W.♦
- 141k
5
votes
How can I get O(1) prepend on a random-access list?
A deque with growing arrays provides the operations you need in (amortized) constant time. Reversing a deque is simple, you don't move data around, you just switch the meaning of ...
- 5,910
5
votes
Accepted
Lambda calculus lists construction explanation
There are several ways to define lists in lambda calculus. You can find them here.
Your definition doesn't seem to fit exactly in any of those (please, check that).
Anyway, I'll try to answer to your ...
- 630
5
votes
What's the fastest way to find the Kth smallest value in an unsorted list without sorting?
Unfortunately I can't just comment but I have to post it as an answer.
Anyway, you could try to use a min-heap on your unsorted array, you should be able to get a time complexity of O(n+k*logn).
- 201
5
votes
Accepted
Time complexity to check if there is an edge between two nodes in an adjacency list
In an adjacency list each vertex $u \in V$ is associated with a list of adjacent vertices.
Given a graph $G=(V,E)$, in order to check if the edge $(u,v) \in E$ you need to check whether $v \in \text{...
- 1,615
4
votes
Efficiently finding duplicates in lists of numbers
Use any efficient set data structure, based e.g. on hashtables or balanced search trees.
Keep in mind that such optimizations are dwarfed by the exponential nature of any algorithm I assume you will ...
- 70.9k
4
votes
Accepted
Why does linear search have $\frac{n}{2}$ comparisons on average?
It's neither ${(n^2+3n)}/{(2n+2)}$ nor $n/2$. In fact, the question itself doesn't make much sense at all. In order to be able to talk about the average running time of an algorithm, you have to fix a ...
- 4,132
4
votes
Accepted
How to use structural induction to prove law on lists
You'll want a helper lemma to make this endeavor more digestible.
Notations for map and subs:
I'm going to condense the ...
- 1,107
4
votes
Accepted
Fastest way to search a word in a word list?
Trie might help, it stores your "word list" like this:
...
- 888
3
votes
The fastest algorithm for intersection of two sorted lists?
Essentially the same algorithm as you'd use to merge the two lists. In the general case, you can't possibly do better than looking at essentially every element of both lists because, if you don't ...
- 80.3k
3
votes
Accepted
Find the duplicates in a list of floating point numbers
Sorting
The simplest algorithm is to sort your floats, then compare adjacent entries. This will let you find all pairs that are $\le \frac1N$ apart in $O(N \lg N)$ time.
Hashing
It's also possible ...
D.W.♦
- 141k
3
votes
Accepted
Order-preserving update of a sublist of a list of mutable objects in sublinear time
At the time of writing I was not absolutely sure what the problem
was. This lead to a more general second answer. See details in
discussion at the end of this answer.
Apparently, the "idea that does ...
- 19.1k
3
votes
Accepted
Join large list of pairs
You can use a two pass approach:
In the first pass, identify all the different strings appearing in your input. (This can be done in various ways, e.g. hashing, trie, BST)
For the second pass ...
- 6,519
3
votes
counting arithmetic progressions $a, a+r, a+2r$ in a list
Given that the OP is rather unprecise as to the kind of numbers he is
considering (though he later said integers or integers modulo $p$ in a comment), I will try to answer nevertheless, by trying to ...
- 19.1k
3
votes
What's the fastest way to find the Kth smallest value in an unsorted list without sorting?
The Quickselect algorithm can do that in O(n) average complexity, it is one of the most often used selection algorithm according to Wikipedia.
It is derived from QuickSort and as such suffers from a ...
- 131
3
votes
Gauss-Jordan using stacks and list
What you want is called indirection. Instead of physically moving the rows/columns, you move their names.
Let's say I call row 1 r[0], and row 3 ...
- 12.3k
3
votes
When are adjacency lists or matrices the better choice?
Consider a graph with $N$ nodes and $E$ edges. Ignoring low-order terms, a bit matrix for a graph uses $N^2$ bits no matter how many edges there are.
How many bits do you actually need, though?
...
- 18.9k
3
votes
Accepted
Is there a name for the "tree" aproach to listing things?
Your technique is known as exhaustive search (with some pruning). It consists of trying all possibilities. In many cases, the way to implement exhaustive search is using a search tree. There are ...
- 270k
Only top scored, non community-wiki answers of a minimum length are eligible