spoiler below… one approach is to sort both lists. then you can go through both of them in sorted order, advancing whichever list has its current value lower in sorted order, and find any duplicates. alternately, just sort the union of the two lists, and then scan for adjacent strings that are identical. sorting can be done on O(n log n) in lots of ways, and then the scanning process is just O(n). C
On Apr 12, 2019, at 11:29 AM, James Propp <jamespropp@gmail.com> wrote:
I don't see how to do it in amortized time O(n). (For that matter, I don't see how to do O(n log n) either.)
Hints? Answers? References?
Jim
On Fri, Apr 12, 2019 at 12:19 PM Tomas Rokicki <rokicki@gmail.com> wrote:
And after figuring out how to do it in O(n log n) then they can realize you only need to store one list, and you can do it in amortized O(n) (ignoring the length of the message).
Even better, you don't actually need to store the lists, but just some small number of bits per message . . .
On Fri, Apr 12, 2019 at 9:10 AM Cris Moore <moore@santafe.edu> wrote:
p.s. in Endnote #2, "The trick is to encode x using all million possible single-stage encryption procedures, obtaining a list of a million
nonsense
strings, and decode x” using all million possible single-stage decryption procedures, obtaining another list of a million nonsense strings, and then look for a string that’s in both lists.”: you might want to challenge the reader to figure out how to “look for a string that’s in both lists” in time which is only about O(n log n) where n=a million.
C
On Apr 12, 2019, at 8:21 AM, James Propp <jamespropp@gmail.com> wrote:
I've posted a draft of the essay I plan to post on the morning of the 17th (or maybe the night before) at
http://mathenchant.org/047-draft1.pdf
I don't expect to get comments from many of you, but all comments will be appreciated and acknowledged.
One thing that's missing from the essay is a good reference for readers who want to learn more about modern mazes. For that matter, do any of you know of any good references about how to create proofs that explicitly advocate the work-from-the-outside-in tactic? I've never read "How to Read and Do Proofs" or the many similar books that are out there, but if you think readers of my blog would like a particular book in this genre, I'd be glad to mention it.
Thanks,
Jim _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cris Moore moore@santafe.edu I confess to an uneasy Physiocratic suspicion, perhaps unbecoming in an academic, that we are throwing more and more of our resources, including the cream of our youth, into financial activities remote from the production of goods and services, into activities that generate high private rewards disproportionate to their social productivity. — James Tobin, 1984