Re: midterm for 94.404 at UMass Lowell

David Wagner wrote:
TheGist wrote:
Consider a set S of n>=2 distinct numbers given in unsorted order. c) In O(n) time, determine x,y in S such that x+y=Z, where Z is given or determine that no two such numbers exist.

Ok, you got me. How do you solve this one in O(n) time?

Basically, go through the list of numbers and create a hash table
key is Z, value is (x,y). Hash Table creation is O(n)
Now, given Z look it up in the has tbale for the appropriate, if any
x and y. Hash Table lookup is O(1). Thus, in total O(n).
.

Relevant Pages

  • Re: Entropy Loss in Hashing
    ... David Wagner wrote: ... >>Does sending the output from a hash back into itself cause a loss of ... Though this time he spares us the math, ...
    (sci.crypt)
  • Re: Deleting hash keys, but ending up with other keys
    ... David Wagner wrote: ... > I have two hashes and each is made up of two keys. ... I change the numeric value in the first hash. ...
    (perl.beginners)
  • Re: new /dev/random
    ... On Thu, 7 Oct 2004, David Wagner wrote: ... The Leftover Hash Lemma only starts to ... for a hash function to be 2-universal, ... There are also bounds on "strong extractors" ...
    (sci.crypt)
  • Re: Complex Theoretical One Way Hash Question
    ... David Wagner wrote: ... 2^700 ways of drawing that hash in the image. ... Pinging self with 32 bites of banana cake: ...
    (sci.crypt)
  • Re: constructing a specified hash function
    ... David Wagner wrote: ... Note that the last construction I suggested is standard stuff and can be ... This hash function will be used in my project about e-business. ...
    (sci.crypt)