tag:blogger.com,1999:blog-6555947.post8480955095329108791..comments2023-09-10T07:21:33.251-06:00Comments on The Geomblog: Happy Birthday, Don Knuth !Suresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-6555947.post-58149431121943540602008-03-09T01:46:00.000-07:002008-03-09T01:46:00.000-07:00I guess the solution makes more sense in a streami...I guess the solution makes more sense in a streaming context, where you can look at each item exactly once. In your solution, once you generate the random number, you'd have to pick an item, which would require reading it a second time (the first time was when you were counting the stream length). This is not allowedSuresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-21296150438679959982008-03-09T01:11:00.000-07:002008-03-09T01:11:00.000-07:00Maybe I'm missing something, but in the solution t...Maybe I'm missing something, but in the solution to the original problem you have to scan through the entire set of objects to get your random element. Why not just skip all the "replace with probability x" stuff and just run through all the objects, find out how many there are (say N) and get a random one by generating a random number in the range 1 to N?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-52874423095904920542008-01-10T14:12:00.000-07:002008-01-10T14:12:00.000-07:00That's nice. But I was hoping for a tribute to Kn...That's nice. But I was hoping for a tribute to Knuth's contributions to Computational Geometry. Like the randomized incremental algorithm for Delaunay Triangulations or something :(.Anonymousnoreply@blogger.com