Re: Any pointers?

Sheri wrote:
Have an array 1..n initialized to 0. Randomly pick a number k (from 1
.. n ) and set the array position k to 1.If there is collision , ie if
Array[k] == 1 retry the same step until a suitable position is found
Can this be mapped to a recurrence? What is the average running time of
this algorithm? Where can I find good reads on the net for such
problems

Sheri,

if there is a collision and you keep on trying with new /random/ k, you theoretically might end up with never finding an empty cell within your vector (namely when all cells are already occupied). As the occupied:empty ratio increases while in operation, you generally run into a situation in which you need to create more and more pseudorandoms to eventually find an empty cell.

A better approach would be to simply increment k by 1 until you find an empty cell (or detect that there are no more free cells in which case you need to do some "End of Memory" handling).

This problem is common in "Hashing". If your problem is related to such, you may want to check out http://burtleburtle.net/bob/hash/ with quite a lot of material about it.

Regards
//Herbert


--
http://herbert.wikispaces.com
.

Relevant Pages

  • Re: Reading all of the the tree control text
    ... Thanks Darren, but tree control allows to have an empty cell followed by a non-empty one, so this algorithm would stop at 1st empty cell in a row and miss any text that follows. ...
    (comp.lang.labview)
  • Re: Trivial problem
    ... suitable position is found Can this be mapped to a recurrence? ... What is the average running time of this algorithm? ...
    (comp.programming)
  • Any pointers?
    ... Can this be mapped to a recurrence? ... this algorithm? ... PS - any pointers to good reads on the INTERNET about randomized ...
    (comp.theory)