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