Tag Info

6

This is a nice question. In the comparison model or, what is more general, the algebraic decision-tree model, the problem of element distinctness has a lower bound of $\Theta(n\log n)$ time-complexity in the worst case as said in this Wikipedia article. So there is no algorithm to count distinct elements in linear time in the worst case, even without ...

5

The way I can think of to do this is by some sort of normalization: that is, you need to find a function $f$ such that, if $\equiv$ is your custom equality and $==$ is the normal C++ (or whatever language you use) equality, for all $x,y$, we have $x \equiv y$ if and only if $f(x)==f(y)$. We call $f(x)$ the normal form of $x$. Then, the trick is, instead of ...

4

Let $U = [m]$, and let $h$ be the identity function. If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i \in [m]$, given by $$h_i(x) = \begin{cases} x & \text{if } x \neq m+1, \\ i & \text{if } x = m+1. \end{cases}$$ The same approach can be used for arbitrary $|U|$: fix the first $m$ ...

3

If you don’t know the equality function then you let hash(x) = 0. Seriously. All your algorithms will work, but slowly because of collisions. All the other suggestions will make your hashing slow instead so you lose nothing. Actually, if you have multiple dictionaries containing these keys, operations are quadratic in the size of each dictionary, instead of ...

3

If the only operation allowed between any two (possibly the same) elements in the two arrays is to determine which one is the smaller one, then it will take $\Theta(n\log n)$ time in worst case for any algorithm. This can be seen from the situation when array $a$ is sorted while array $b$ is arbitrary before we apply the algorithm. Knowing the index $I(k)$ ...

3

Let $H$ be a family of strongly universal hash functions from $U$ to $[m]$. Construct a new family of hash functions from $U \cup \{x\} \to [m]$ by extending all functions $h \in H$ with $h(x) = 1$. The family is weakly universal since $h(u)$ is distributed uniformly for every $u \in U$, but it is clearly not strongly universal.

2

I don't agree that the author was talking about iterating over a set with constant time per element. I've never seen iteration described in time per element. It's certainly not common enough to be an unspoken assumption. I would guess that instead it's simply an editing miss.

2

The load factor of a hash table is defined as: $$\lambda = \frac{n}{k}$$ where $n$ is the number of items stored in the table and $k$ is the number of buckets. So the load factor is greater than 1 if there are more entries than buckets. Storing more than one entry in a bucket is very common. The most familiar example is separate chaining (e.g. a linked ...

2

$h'(k)$ is the value returned by the original unmodified hash function when applied to the element $k$. If the $h(k)$ slot is not free then $h(k,i)$ for $i=0,1,2,\dots$ gives a sequence of modified hash values which can be tried in turn until a free slot is found.

1

Your question is a bit vague, but it seems that you're missing one mechanism: dynamic memory allocation. Some data structures such as linked lists are heavily based on dynamic memory allocation, and so although linked lists are very similar to arrays in function, they are implemented very differently. Dynamic memory allocation is treated as a primitive in C....

1

Suppose the objects you want to compare are strings containing terminating programs that output either 1 or 0 (and written in Visual Basic, because why not), and the equality function returns true if and only if the output of the two programs given as operands is the same. (The termination assumption is there to ensure that this equality is well-defined.) ...

1

I think the answer is no, SUHA does not imply anything regarding worst-case time complexity. The bottom line is that the hashing is still viewed as random, and the keys still unknown. Regardless of how small the probability is for all keys to hash to the same bucket, it's still a theoretical possibility, thus the theoretical worst-case is still O(n). I ...

1

Your solution has $O(n)$ computational complexity but it doesn't implement the first fit algorithm. The thought behind your solution is to insert the items one by one in the given order (that's correct) and to insert the current item in the last bin if it fits in it or to create a new bin if the current item doesn't fit in the current bin (that's wrong). ...

1

Your approach 3 can be made safe using a solution to exercise 2.12 of Aho, Hopcroft, and Ullman (1974) The Design and Analysis of Computer Algorithms as described, for example, in Using uninitialized memory for fun and profit. Basically, in addition to your array of N elements with the counts you have two arrays of N elements and one auxiliary count to ...

1

There exist randomized algorithms whose expected running time is $O(n)$; or where the probability that the running time takes longer than $cn$ is exponentially small in $c$. In particular, randomly choose a 2-universal hash function, then use it to hash all of the elements of the array. This achieves the stated running times, if you choose the length of ...

1

A stack of hashtables would be a perfectly fine representation. A hashtable of stacks wouldn't be a good choice, but a stack of hashtables would work. When you leave a scope (e.g., the } symbol), you need to pop off all of the symbol names defined in that scope. That's easy with a stack of hashtables, but a bit more annoying with a hashtable of stacks. A ...

1

I came up with and algorithm of moving the last non-Null element of the probe sequence to the place of the deleted element to make the probe sequence contiguous. But this would make it impossible to retrieve the moved element if its hash index value was greater than that of the removed element. So is there any correct algorithm for this? Yes. There is ...

1

I suppose one could define the word however you like, but I've always understood it to mean the same thing you are talking about. Here I'm assuming if you try to insert a key the second time, no change is made, as it is already present. If inserting the key caused a second copy to be inserted somewhere, then I think it's more ambiguous and in any formal ...

1

From your picture, one definitely see a hash table collision solution. If one carefully examine it, will see that the table uses itself to solve the collision, that is Open Addressing. In open addressing, the collision can be resolved by many methods; Linear Probing Quadratic Probing Double hashing. It might be Double Hashing or Quadratic Probing but the ...

1

Two letters from a name are an extraordinarily bad hash code. There are only 576 possibilities, but letters are not random (you will find very few names with initials Z. Z.). With 10,000 records, I'd expect easily 100 records with the same hash code. There is no way on earth you can get the expected number of comparisons below 20 with this hash code. Take a ...

1

In algorithm complexity analysis theory, O(1) means the algorithm computes the answer independently of the number of elements -- for the particular case of a perfect hash algorithm, the "number of elements" is relative to the possible keys it may be presented to. However, such algorithms still have a complexity in regard to the length of the key present. ...

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