20
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.
Now, when we use matrix representation we allocate $n\times n$ matrix to store node-connectivity information, e.g., $M[i][j] = 1$ if there is edge between ...
10
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 doesn't really matter.
Let's plug in some numbers to see how this behaves. When $n = 100$ and $k = 10$, we get
$$
100 \cdot (1/2 + 1/4 + \cdots + 1/2^{10}) \...
10
Use selection algorithm for linear time https://en.m.wikipedia.org/wiki/Selection_algorithm
8
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 sizes with (possibly) fewer comparisons. It works by calculating a stride from the ratio m/n and doing the comparison against that element in the larger list; ...
8
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 zeros. For each score s, we will add 1 to count[s]. To produce the wanted sorted scores, we will output count[1] 1s, count[2] 2s, ..., and finally count[100] 100s.
This kind of sorting algorithm is ...
7
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$, create a row (i.e. binary string) $B_i = b_1 b_2 \ldots b_n$, where
$$ b_k = \begin{cases}
1 & \text{if }\overline x_k \in C_i \\
0 & \text{if } ...
6
Let's start with the case when the lists are sorted. In that case, you can apply a simple modification of the basic merge algorithm on sorted lists: discard the elements instead of constructing a merged list, and only keep track of whether an element from list 1 was missing from list 2.
In the pseudo-code below, head(list) is the first element of list, and ...
answered Nov 26 '13 at 1:26
Gilles 'SO- stop being evil'
38.9k7 gold badges103 silver badges167 bronze badges
6
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.
The sum of numbers from $1$ to $n$ is $\frac{n(n+1)}{2}$, so if you subtract that from the sum of the list you get the number appearing twice.
6
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-else) and primitive (first-class) functions. Pairs are not primitive, yet they can be encoded as follows.
In place of a pair $(x,y)$ we can consider the ...
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
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 prepend and append and massage the index for at and update.
But you don't seem to want to reverse the list anyway.
5
It's easier to change notation. Suppose the array is $A$, with the $i$-th element denoted $A[i]$ for $i=1,2,\dots,n$, and that element $i$ has attributes $A[i].x$ and $A[i].y$. Associate a directed graph $G$ with the array as follows. The vertices of $G$ are the indices $1\dots n$ of the array. Vertex $i$ is connected to vertex $j\ $ if both conditions $...
5
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 questions.
Lists (and many data types) can be defined in lambda calculus in terms of the way to deconstruct them.
If you are familiared with the fold ...
5
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).
5
Let us assume that required element is equally likely to be in any position between $1$ and $n$. Let $x _i $ be a random variable. Random variable $x_i = 1$ means required element is in ith position and vice-versa. Now probability that required element is in position between $1$ and $n$ is $$ Pr[x_i = 1] = \frac{1}{n}$$ Now Expected value is given by $$\...
5
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 is $2N$.
Now consider the set of points $\{(i,i^2\ mod\ n)\ |\ 0\leq i \leq n-1 \}$.
For any set of 3 points to be collinear (Lets call them $(x_1,y_1),(x_2,...
4
Have a look at Wadler et al's How to add laziness to a strict language without even being odd. It presents a number of techniques (for Standard ML) and provides a good survey of the literature of the time.
The most naive way is to delay the evaluation of term $t$ by making it, using a term such as $\text{delay }t=\lambda ().t$, and to force the evaluation ...
4
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 come up with.
That said, you may want to check out pseudo-polynomial algorithms for Knapsack, and problem variants that have polynomial-time algorithms.
4
You'll want a helper lemma to make this endeavor more digestible.
Notations for map and subs:
I'm going to condense the map notation a bit so that we can express it as the binary operator $f \diamond l = \mathrm{map} ~ f ~ l$. Similarly, we will express the subs as a unary operation $\lfloor\!\!\lfloor l \rfloor\!\!\rfloor = \mathrm{subs} ~ l$.
This might ...
4
Trie might help, it stores your "word list" like this:
a
/ \
[a] a
/ \
[a] h
\
e
\
[d]
And you can query by some operation like trie['a']['a']['h']['e'], which is just array index operation. It takes ...
4
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 under that node. Then you can find the $i$th largest value in the list in $O(\log N)$ time as well; thus, all basic operations can be done in $O(\log N)$ time.
3
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 look at the elements, you don't know what's in the lists, so you don't know what's in the intersection. (OK, you can stop as soon as you've run out of elements in ...
3
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 to come up with a linear-time algorithm, i.e., to check whether there is any nearby pair of floats and if so find at least, in $O(N)$ time.
Let $M=\lfloor N/2 ...
3
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 not work" does not work because you do
not know the index of an element $S_i$ in $F$ organized as a tree.
This is what is addressed here. The problem is ...
3
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 limit the
number of assumptions I can make. And while I am at it anyway, I will
generalize a bit.
This builds on the contributions of previous answer and ...
3
It is a typical example of a space-time tradeoff trading increased time (CPU instructions required) for decreased space (memory required). There are many examples of this.
In this particular case I'd say it is a (simple) form of lossless compression. This because the data is stored in a minified but unusable form and needs some computation (decompression) ...
3
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 initialize a Disjoint-set data structure with the strings found in the first pass and perform a union operation for each pair in the input.
3
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 O(n²) worst case complexity if you use a bad pivot (a problem that can be avoided in practice).
The algorithm in a nutshell: After the pivoting like in ...
3
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 probability distribution for the input. As an example, it is well known that the average running time of naive quicksort is $\Theta(n \log n)$, but that result ...
Only top voted, non community-wiki answers of a minimum length are eligible
