This work is licensed under a
Creative Commons License.
|
Friday, October 28, 2005
Algorithms for a Ten-Year Old
Posted by Lance
Yesterday my fifth-grade daughter, doing her math homework, askedIs there a faster way to find greatest common factors other than with factor trees?I live for these days. After I impressed her with Euclid's algorithm she askedIs there a faster way to factor than with factor trees?I thought for a while and then just answered "No."5:55 AM
# 14 comments
-
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".
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.
Are you grooming a future complexity theorist?
-
No, Lance responded like a true constructivist CS (or logic) person.
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.
Janos Simon
-
Quick theory question. Has factoring been proven to be NP complete? If so could you give a reference to the reduction?
-
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.
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.
-
Factoring has not been
proved NP-complete.
If P is not NP, it is unlikely that factoring
is NP complete.
See:http://en.wikipedia.org/wiki/Integer_factorization
Since factor tree method
is exponential, and a
lot of algorithms of factoring are subexponential,
so I think that answer
to the last question should be Yes.
-
I guess 5th grade IS a little early to learn quantum theory ;)
-
Fifth Grade is too early for Quantum
Computing (and Shor's algorithm) NOW.
But in 1000 years- who knows.
Over time Calculus has gone from
being a Senior course in College to
being a freshman course, and now in
many High Schools. Some Computer Science
concepts may do the same.
Thought quantum- hard to say.
Problem 4 on CS AP exam in the year 3000:
Show that Factoring is in QP-P.
-
This made me laugh out loud.
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.
Kris Hildrum
-
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.
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).
Lesson for us: kids need time to build some gut-level domain ontology before it's rewarding for them to study/design algorithms.
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.
-
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?
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.
-
"Lesson for us: kids need time to build some gut-level domain ontology before it's rewarding for them to study/design algorithms."
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.
-
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.
-
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.
-
Well it is something similar to comic I had read .. I guess it was xkcd or phdcomics...
but the crux of it was that PhDs can't answer simple questions for sure because the depth in research makes them unsure.. ;)
Links to this post:
Weblog Home
Archives
