22

Sure. But in practice that is rare: the sorting algorithms we usually use or analyze in practice do at most a constant number of other operations per comparison, so this isn't an issue for the sorting algorithms we actually care about. This means that measuring the number of comparisons or the number of steps taken gives you the same asymptotic running ...


15

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 replace one of the letters with a special character, not found in any of the strings. While you add them, check that they are not already in the set. If they are ...


12

It's possible to achieve $O(nk \log k)$ worst-case running time. Let's start simple. If you care about an easy to implement solution that will be efficient on many inputs, but not all, here is a simple, pragmatic, easy to implement solution that many suffice in practice for many situations. It does fall back to quadratic running time in the worst case, ...


9

If moving an item were n times more expensive than comparing, selection sort would suddenly be the most efficient algorithm. But if moving an item were expensive, we could sort an array of array indices, and then sort the original array in place with at most 1.5n moves. (That would actually be n/2 swaps; if a swap is cheaper than 3 moves then worst case is 4/...


7

Imagine having a tournament made of the array elements. Group the array elements into pairs, then compare each pair. Put the larger numbers into one group and the smallers number into another group. The maximum value of the original array must be the max of the larger group and the minimum value of the original array must be the min of the smaller group. ...


7

I would make $k$ hashtables $H_1, \dots, H_k$, each of which has a $(k-1)$-length string as the key and a list of numbers (string IDs) as the value. The hashtable $H_i$ will contain all strings processed so far but with the character at position $i$ deleted. For example, if $k=6$, then $H_3[ABDEF]$ will contain a list of all strings seen so far that have ...


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


6

what if the number of comparisons can be O(n log n) or O(n), but then, other operations had to be O(n²) or O(n log n), then wouldn't the higher O() still override the number of comparisons? Um, yeah. That's why, in such cases, we do use those other operations for the analysis. For example: Binary insertion sort employs a binary search to determine the ...


5

The other answers provide correct solutions. However, you can do a bit better considering multivariate complexity. Note that the provided running times in the other answers are not quite specific since they ignore either the size of the first array or the lengths of the strings. Here are 2 different methods with their specific running times. The first of ...


4

If for all $|r - s| < 1$ it is the case that $K(r) = K(s)$ then $K$ is constant (exercise). What you are asking is impossible. One thing which is possible is to compare keys with three rather than two possible outcomes: If $K(r)$ is close to $K(s)$ then $|r - s| < 1$. If $K(r)$ is far from $K(s)$ then $|r - s| \geq 1$. Otherwise, we don't know. Of ...


4

You asked about what approach to take, so I'll explain the general approach to take for this kind of problem. The way to prove that 5 comparisons are sufficient is to exhibit a specific algorithm for merging these two sequences, and prove that your algorithm uses no more than 5 comparisons (no matter what the input is). So, here's the approach I'd suggest ...


4

Suppose that every element is at most $k$ elements away from its true position. In order to sort the array, you maintain a heap. At step $i$, you add $A_i$ to the heap, and pop the minimum element as $A_{i-k}$. You do no popping in the first $k$ steps, and no adding in the last $k$ steps; there are $n+k$ steps in total. Since the heap is always of size $k+1$,...


3

The ‘k-translation correlation’ is probably a good candidate for what you are looking for. It measures the maximum correlation between a pair of two filters $\mathbf{W_i}$ and $\mathbf{W_j}$ achieved by translating one filter up to k steps along any spatial dimension and then selecting the maximum thereof: $$\rho_k(\mathbf{W_i,W_j})=\max_{(x,y)\...


3

You can use a simple adversary argument (in Jeff's lecture note) to prove that every correct algorithm has to compare $a_i$ with $a_{i+1}$ for $i=0,1, \ldots, n−2$. If it is not the case, you can carefully choose the values such that $a_{i+1} < a_{i}$, without violating any other comparison results. You are encouraged to fill the details.


3

The problem is not decidable (by reduction from the Halting problem), so there is no perfect algorithm that always terminates and always gives the correct answer. Therefore, you'll need to make some tradeoffs. That will depend on the specifics of your particular application, so it's hard to recommend a particular technique without knowing how you plan to ...


3

This is a pretty common version of partition and in this case you need N+1 comparisons. For example consider an array containing ${1,2,\ldots,N}$. Now, 1 is your pivot (partitioning item). pivot 1 is compared with first element 1 and it is greater than or equal it, so you got the left item. Here you need 1 comparison. Then, pivot 1 is compared with $N,N-...


3

Your proof is correct. But I don't think 5 comparisons is achievable. Here is the algorithm that finds the median in 6 comparisons. Sort the first two pairs. [ 2 comparisons] Order the pairs w.r.t. their respective larger element. [ 1 comparison] Call the result $[a,b,c,d,e]$; we know $a<b<d$ and $c<d$. Now there are 3 elements less than $d$, ...


3

The question is about a three-valued function in a situation where a boolean is often used (eg <=). I personally refer to this as the sign or signum: the sign of the difference of the comparands. However I have not seen a widely-used term; the best supportable answer I can give is that there is none. In Quicksort, when a three-way partition (based on ...


3

The $\Omega(n \log n)$ lower bound still applies; you still can't do better than $O(n \log n)$. (Proof: Take any array of numbers. You can find the maximum and minimum in $O(n)$ time. Then, rescale the array. In particular, if the minimum and maximum are $\alpha$ and $\beta$, replace each element $x$ of the array with $(x-\alpha)/(\beta-\alpha)$. After ...


3

Let's say the size of the array is such that there are $2^{k-1} < x ≤ 2^k$ possible permutations, so the theoretical lower bound to sort this array is k comparisons. Any comparison divides the set of possible permutations in two subsets, consistent with each outcome of the comparison. You'd first need a comparison that splits the set of all possible ...


3

Yes, running back and forth comparing letters is the best you can do. You could always read and remember two, three or any fixed amount of symbols at a time; then there would be less running back and forth, but the programming would be even worse. And yes, in general you have to rewrite everything when you change something. There are no functions, ...


2

In theory sorting a long sequence of int should be a prime candidate for radix sort as it grows linear in the number of elements to be sorted, while any comparison based sorting algorithm can't be faster than N log N.


2

As others have said, what you want is impossible. But you might want to look at locality-sensitive hashing. It achieves something vaguely similar: if two elements are similar, then with significant probability they will have the same hash. It is possible to amplify the probability by hashing with multiple independent hash functions. With high probability,...


2

The second variant isn't much better: $\forall s,r: |r-s| < 1 \Rightarrow K(r) = L(s)$ implies that $\forall r: K(r) = L(r)$, as $r = s$ is only a special case. On the other hand, you are down to two comparisons: $K(x) := \lfloor 0.5\cdot r + 0.5 \rfloor \\ L(s) := \lfloor 0.5\cdot s \rfloor \\ \forall r,s: |r-s|<1 \Rightarrow K(r) = L(s) \lor K(r) = ...


2

One approach is to use low-rank matrix factorization to approximate the ratings matrix, then use a nearest neighbors data structure. In particular, let $M$ be the $m \times n$ ratings matrix, where $M_{ij}$ is the rating that user $i$ has provided to user $j$. Look for a $m\times r$ matrix $U$ and a $r \times n$ matrix $V$ such that $M$ is well-...


2

A general algorithm is to compute the SHA256 hash of each file, then sort the hashes and look for duplicates. After sorting any duplicates that may exist will be consecutive. For all practical purposes, you can assume that two files will be identical if and only if their SHA256 hash is the same. If you're asking how to do this from the command line or ...


2

You can't. There isn't enough information in a single elimination tournament to know who the $n$ best players are. All you can infer is who the best player is. You can't even tell who is second best; the second-best player could be any of the people who lost to the best player. If you're not limited to a single-elimination tournament, I recommend you use ...


2

The following answer is based on the following graph, taken from Wikipedia: If $x_i,x_j > 0$ then you can use the monotonicity of the arctangent to get the equivalent condition $y_i/x_i < y_j/x_j$, or $y_ix_j < y_jx_i$. If $x_i < 0$ and $x_j > 0$ then the answer depends only on the sign of $y_i$, and if $x_i > 0$ and $x_j < 0$ then the ...


2

Here is a more robust hashtable approach than the polynomial-hash method. First generate $k$ random positive integers $r_{1..k}$ that are coprime to the hashtable size $M$. Namely, $0 \le r_i < M$. Then hash each string $x_{1..k}$ to $(\sum_{i=1}^k x_i r_i ) \bmod M$. There is almost nothing an adversary can do to cause very uneven collisions, since you ...


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