2
$\begingroup$

For the following question from Introduction to Algorithms book, "We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for implementing a direct address dictionary on a huge array. Each stored object should use $ O(1)$ space; the operations SEARCH, INSERT, and DELETE should take $O(1)$ time each; and the initialization of the data structure should take $O(1)$ time. (Hint: Use an additional stack, whose size is the number of keys actually stored in the dictionary, to help determine whether a given entry in the huge array is valid or not.)"

Problem: can you please help explaining the wording of the question in your own words? No solution is needed.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Are you sure about the additional stack? To me it doesn't sound as an efficient data structure for supporting lookups in a hash table. $\endgroup$
    – Chaos
    Aug 29 '21 at 13:18
  • $\begingroup$ @Chaos. Thanks for reply. Yes, this is from the book! $\endgroup$
    – Avv
    Aug 29 '21 at 13:20
  • 1
    $\begingroup$ Ok, i see what they did there. $\endgroup$
    – Chaos
    Aug 29 '21 at 13:22
  • 1
    $\begingroup$ Glad you liked my answer! :) $\endgroup$
    – Chaos
    Aug 29 '21 at 13:32
1
$\begingroup$

"We wish to implement a dictionary by means of an hashing function that maps all its possible inputs to a huge but finite set of natural numbers of size $k$. The function is implemented by values of an array witnessing the presence/lack of any element. The array is expensive to setup, so we ask that the algorithm does not clear it. (It is used for holding pointers to present elements.) Describe an algorithm for granting, constant time operations, constant space usage for items storage (pointers to objects) and constant initialisation time. ( Hint. Employ and additional stack for avoiding false positives on insert/removal and lookup operations.)"

False positives are due to the presence of garbage. Possibly the most nebulous part is the usage of the stack. Since it is bounded in size (at most $k$), you will have to scan from it at most $k$ elements. Since it's size is bounded you can have lookups in O($k$) and that's constant time.

Improve this answer
$\endgroup$
9
  • 3
    $\begingroup$ How is $O(k)$ constant time? nobody said anything about the size of $k$ being bounded. $\endgroup$
    – nir shahar
    Aug 29 '21 at 13:48
  • 1
    $\begingroup$ Direct hashing requires $k$ to be known and constant and as such bounded. It can be set at compile time (actual constant) o before the algorithm is run (configuration value). What matters is that it does not change during execution. $\endgroup$
    – Chaos
    Aug 29 '21 at 13:50
  • 1
    $\begingroup$ What is $k$ in your definition? I thought you meant it is the number of items in the map $\endgroup$
    – nir shahar
    Aug 29 '21 at 13:51
  • $\begingroup$ It is the size of the range of the hash function, also the size of the array. Well, it depends on how you actually definite the hash function but it at least must be the size of the array. $\endgroup$
    – Chaos
    Aug 29 '21 at 13:53
  • 1
    $\begingroup$ The size of the array is said to be "huge" and thus it is impractical to go through the entire array. Did I misunderstand you? $\endgroup$
    – nir shahar
    Aug 29 '21 at 13:55
2
$\begingroup$

Here is another hint: how would you find whether an element is valid in $O(1)$ in this auxiliary stack? Try to somehow "connect" the index at the original huge array, to the place in the stack that says that this element is indeed valid. Don't be afraid to use another auxiliary array for this!

Improve this answer
$\endgroup$
9
  • 2
    $\begingroup$ Initializing the auxiliary stack won't be $O(1)$. Is it? $\endgroup$
    – Inuyasha Yagami
    Aug 29 '21 at 14:01
  • 1
    $\begingroup$ @InuyashaYagami Without clearing the data in it, there is a way to do this. since its a stack - we know exactly which elements are valid: all elements with an index less than the current number of items in the stack. $\endgroup$
    – nir shahar
    Aug 29 '21 at 15:08
  • 1
    $\begingroup$ @Avra I think you got it right - something along the lines that you wrote in the first comment should work. If something wasn't initialized then it will either map to outside the stack size (and hence is invalid) or will map to an element within the stack, which will point back to a different value, hence we know it is not really valid. $\endgroup$
    – nir shahar
    Aug 29 '21 at 15:12
  • 1
    $\begingroup$ @InuyashaYagami we don't need to. There is a way to do it without this initialization. If you want, I can post it as a full answer (but it doesn't look like the OP wanted a full answer anyways) $\endgroup$
    – nir shahar
    Aug 29 '21 at 18:24
  • 1
    $\begingroup$ tildesites.bowdoin.edu/~ltoma/teaching/cs231/fall09/Homeworks/… $\endgroup$
    – Nayuki
    Aug 30 '21 at 5:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.