tag:blogger.com,1999:blog-3722233.post113049702237851786..comments2021-09-14T11:25:32.611-05:00Comments on Computational Complexity: Algorithms for a Ten-Year OldLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-3722233.post-57353850317802057782013-07-03T12:18:12.732-05:002013-07-03T12:18:12.732-05:00After my son (he is 5) saw the sorting mail packag...After my son (he is 5) saw the sorting mail packages episode on Curious George, he kept asking, so if we sort the packages it becomes easier? I think I must have answered yes to his 10 different articulations of the same question. Heaven!<br /><br />I am itching till he gets his addition skills up a bit so we can progress to sums of series.<br /><br />But in terms of spatial algorithms (something I have no expertise in), he seems to be doing something which other kids do as well, and which I don't see is well understood. How the kids solve those shape puzzles (some of those are hard!) is a bit beyond me.<br />Amrinder Arorahttp://www.standardwisdom.com/softwarejournal/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59750614053739030312011-03-20T07:30:23.678-05:002011-03-20T07:30:23.678-05:00Solution to NP complete Hamilton Circuit Problem
...Solution to NP complete Hamilton Circuit Problem<br /><br />An algorithm solves at least a subset of the NP complete Hamilton Circuit problem in n^3 time.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40378313605628033442008-08-13T17:31:00.000-05:002008-08-13T17:31:00.000-05:00Well it is something similar to comic I had read ....Well it is something similar to comic I had read .. I guess it was xkcd or phdcomics... <BR/>but the crux of it was that PhDs can't answer simple questions for sure because the depth in research makes them unsure.. ;)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130827146217267542005-11-01T00:39:00.000-06:002005-11-01T00:39:00.000-06:00If factoring were NP-complete, then you would have...If factoring were NP-complete, then you would have NP = co-NP, which people think doesn't happen. Moreover, factoring is in BQP, and people think that NP-complete problems are well outside of BQP.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130655052602292232005-10-30T01:50:00.000-05:002005-10-30T01:50:00.000-05:00Claire: I would, along with your son, write a prog...Claire: I would, along with your son, write a program which takes division problems as input and produces beautifully formatted Latex output. Then, have him use this program for all further problems and allow him to spend the remaining time reading Knuth, playing outside, etc.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130604827062423662005-10-29T11:53:00.000-05:002005-10-29T11:53:00.000-05:00"Lesson for us: kids need time to build some gut-l..."<I>Lesson for us: kids need time to build some gut-level domain ontology before it's rewarding for them to study/design algorithms.</I>"<BR/><BR/>I can think of no better way to teach children algorithms than with computer graphics and then eventually video games. Perhaps that's just because that's how I first got into programming, but languages like Logo and Joe and Squeak seem to teach the concepts well.Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130542508320317912005-10-28T18:35:00.000-05:002005-10-28T18:35:00.000-05:00Yesterday my sixth-grade son, doing his math homew...Yesterday my sixth-grade son, doing his math homework, asked Is there a faster way to divide a number by another other than with long division? I had no good answer to that. Any suggestions for an alternative to tedious long divisions?<BR/><BR/>I expect that the reason why kids are taught to fing greatest common factors by factorization is that the main point is to understand the concept of factorization: associativity of multiplication, and the uniqueness of decomposition into prime factors. Greatest common factors, I expect, is just a side application to explore the concept.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130535573792658232005-10-28T16:39:00.000-05:002005-10-28T16:39:00.000-05:00Yes, calculus was pushed forward, but whole swaths...Yes, calculus was pushed forward, but whole swaths of algebra and geometry, that used to make the eventual fruits of calculus more richly appreciated, were lost. <BR/>Taking symbolic antiderivatives is a rather meaningless activity for me, and I'm less good at it, because I had less prior immersion in the domains where explicit ones turn out to exist (not that this is a huge loss).<BR/><BR/>Lesson for us: kids need time to build some gut-level domain ontology before it's rewarding for them to study/design algorithms. <BR/><BR/>Adults, too. The rage for order and intellectual mastery that drives much algorithmic research can get results, but in my experience it's more rewarding, and you get better algorithms, if you think 'with feeling' about specific problem examples, find relevances and anthropomorphize a bit, before trying to coerce a problem into an algorithmic paradigm.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130518705695220942005-10-28T11:58:00.000-05:002005-10-28T11:58:00.000-05:00This made me laugh out loud. I can remember the d...This made me laugh out loud. <BR/><BR/>I can remember the day my dad tried to explain parabolas as the path that falling objects take after I asked him for help on my math homework involving solving linear equations. I think my reaction was similar to your daughter's. <BR/><BR/>Kris HildrumAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130514485709107232005-10-28T10:48:00.000-05:002005-10-28T10:48:00.000-05:00Fifth Grade is too early for QuantumComputing (and...Fifth Grade is too early for Quantum<BR/>Computing (and Shor's algorithm) NOW.<BR/>But in 1000 years- who knows.<BR/>Over time Calculus has gone from<BR/>being a Senior course in College to<BR/>being a freshman course, and now in<BR/>many High Schools. Some Computer Science<BR/>concepts may do the same. <BR/>Thought quantum- hard to say.<BR/><BR/>Problem 4 on CS AP exam in the year 3000:<BR/>Show that Factoring is in QP-P.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130513239756254812005-10-28T10:27:00.000-05:002005-10-28T10:27:00.000-05:00I guess 5th grade IS a little early to learn quant...I guess 5th grade IS a little early to learn quantum theory ;)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130511411506481062005-10-28T09:56:00.000-05:002005-10-28T09:56:00.000-05:00Factoring has not beenproved NP-complete.If P is n...Factoring has not been<BR/>proved NP-complete.<BR/>If P is not NP, it is unlikely that factoring<BR/>is NP complete.<BR/><BR/>See:http://en.wikipedia.org/wiki/Integer_factorization<BR/><BR/>Since factor tree method<BR/>is exponential, and a<BR/>lot of algorithms of factoring are subexponential,<BR/>so I think that answer<BR/>to the last question should be Yes.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130511203381394842005-10-28T09:53:00.000-05:002005-10-28T09:53:00.000-05:00I don't understand why kids are taught to fing gre...I don't understand why kids are taught to fing greatest common factors by factorization. I reinvented euclid's algorithm in junior high because it's easier. Then I taught it to a few other students, and the teacher started marking them wrong.<BR/><BR/>Technically speaking, factorization *is* building a syntax tree, the question is whether it's possible to find factors more quickly than using erathosthenes's seive, to which the answer 'no' isn't exactly wrong - it's worthwile to do a seive for all possible factors up to around 2^32, which would make any speedups start providing benefits at values way beyond anything an elementary school student might work with.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130509219507054962005-10-28T09:20:00.000-05:002005-10-28T09:20:00.000-05:00Quick theory question. Has factoring been proven t...Quick theory question. Has factoring been proven to be NP complete? If so could you give a reference to the reduction?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130507538814784162005-10-28T08:52:00.000-05:002005-10-28T08:52:00.000-05:00No, Lance responded like a true constructivist CS ...No, Lance responded like a true constructivist CS (or logic) person.<BR/><BR/>For a constructivist "there is an object O" means "there is a procedure that produces O", and in this sense there is no better algorithm for a ten year old. I would certainly not be able to explain eliptic curves to a ten year old -- ten year olds are very strict constructionists.<BR/><BR/>Janos SimonAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1130503783049341192005-10-28T07:49:00.000-05:002005-10-28T07:49:00.000-05:00Lance, you take the time to explain Euclid's Algor...Lance, you take the time to explain Euclid's Algorithm, but lie about whether or not there are fast factorization algorithms? Shame. The answer should have been, "I don't know, but no one else does either".<BR/><BR/>And wow, learning gcd, factorization, trees, etc in 5th grade? Its been a long time since I was in grade school, but I don't remember doing anything that advanced that early.<BR/><BR/>Are you grooming a future complexity theorist?Anonymousnoreply@blogger.com