
Re: Signuture Lesson Plans (intro)
Posted:
Apr 7, 2009 6:24 PM


Apropos of Dr. Renfro's recent remarks [0], there's a segregation of topics in 912 called "fish ladder math" that goes Alg1, Geom, Alg2, Calc, with Trig/Stats on the side, maybe some computer science (CS) as another elective, though that usually just means "Excel", other bizapps, little programming per se (all the programmers are off making money I think is the problem there  can't retain 'em).
Some constructivist curricula have offered more of a mix, to the dismay of objectivists, who dislike the "watering down" and far be it from me to champion competing brands that use the constructivist label (I come by it through Caleb Gattegno and the ATM, Britain's equivalent to the NCTM but far less obstructive). "More of a mix" just means keeping the dots connecting, showing the segues. It's more a disc jockey approach in that we show what easily blends into what ("seamless math" is another word for it, although topologically I think a graph of connected trails  Dr. Talman's image  is a better way to go (implies big holes, which we want to admit to, not cover up)).
The signature algorithm of the ages, named for Euclid is (drum roll) Euclid's Algorithm. You'd be surprise how many 912 state standards don't include it, even though it's an Alg1 topic, involves relative primality, reducing fractions (lowest terms) plus anchors the whole idea of what an "algorithm" is (just talking about "the four operations" as all we mean by "algorithms" is mind numbing and not to be encouraged).
In Python:
def gcd(a, b): while b: a , b = b, a % b return a
There's that % operator again, from "clock arithmetic", also not given much focus in Alg1, objectively speaking (just do a survey, get back to me with evidence?). The way this works is you try to divide one into the other and if there's no remainder (b is 0) you're done. Otherwise, take the remainder you *do* get and try it against the next larger leftover and so on, until you get down to 1 (unity), in which case a, b are relatively prime. Since 1 always divides evenly, b becomes zero at that point and you get 1 as your answer (a = 1). So maybe that wasn't so clear? You get more chances to get it, including with animations. We're into repetition, which objectivists like, but with the student, the learner, having a lot of control over where (and how) to deliver the reinforcement.
http://www.youtube.com/watch?v=Gjqibo2spv0 (Lower 48 kids, struggling to remain on task)
http://www.youtube.com/watch?v=wQ2w1aQaHSE (primitive camera, clear example)
Note that in Guido's version, we don't care if a > b or b < a to start because a % b, a < b, just returns a, which becomes the the next b, so the division attempt automatically reverses, no need for that extra logic.
Why do we care about the GCD? Not just because of our need to reduce Fractions (rational numbers Q, which we implement as math objects in Python). We also want to understand what's meant by "the totatives of a number".
At this point, 912 teachers are shaking their heads, because they know full well that upline academics have completely failed in their mission to keep the lower grades current or, to put it another way, the backlash in the wake of New Math decimated the ranks of reformer, pushing a lot of the best ones to the sidelines. The Gnu Math subculture, in picking up that mantle to some degree, at least has the Internet to work with, which SMSG did not. YouTube (written in Python) is one of our best selling points. But then many schools block it, won't assign YouTubes for homework, so back to square one (in those schools).
What happened in the 20th century is difficult to summarize in one short post, but basically it went "hyperdimensional" in various ways (I can think of three ways), while algebra took off along lines pioneered by Grassmann and Clifford. Topology grew up, giving us a more flexible and coordinatefree way of thinking. But hey, that's just a snapshot (Thurston was one of my math teachers by the way  a good thing about Princeton is you're really there to teach undergrads, all your other skills as a researcher are consider secondary to your teaching abilities, why undergrad rating systems are encouraged, officially, not just through the informal social networking systems  how about in your school? (remember, Bologna was so successful because the students had hire and fire powers, screened their own teachers!)).
In the topological realm, we got Euler's V + F = E + 2 (with variants, depending on "Euler characteristic") and this is so simple as to be teachable in 2nd or 3rd grade, in conjunction with building some of that geometric vocabulary that'll come in handy later, through all of life in fact. Remember: the virus tends to be "icosa hedral" and icosa means 20, where hedron means "face". A 20faced wireframe is one of the Platonics, its dual being the pentagonal dodecahedron (although "dual" is not strictly the same as "inverse", the five Platonics give a good mental picture of "group" in the sense of closure under the dual operation, with the central and simplest poly dual to itself, then maybe put as pairs on either side: (cube, octahedron), (pentagonal dodeca hedron, icosahedron)).
I mention Euler because we're using his theorem in public key cryptography as well, which is where the GCD comes in. The totatives of a number all all numbers relatively prime thereto and less than, down to 1 inclusive. So like for 12: 11, 7, 5 and 1 have no factors in common (other that 1 itself). In Python then:
>>> def totatives (n): return [ t for t in range(1, n) if gcd(t, n)==1 ]
>>> totatives(100) [1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49, 51, 53, 57, 59, 61, 63, 67, 69, 71, 73, 77, 79, 81, 83, 87, 89, 91, 93, 97, 99]
Note that we got away with *one line* of Python, once gcd had been defined (also very simply). We now have a constructivist environment. Students will try very large numbers and find this doesn't work, as there's an upper limit to what this somewhat inefficient algorithm might handle. Lots of calories, lots of memory... but it does the job we need it to do, for the small numbers we wish to sample.
What Euler's Theorem says is if you call "the number of totatives of N" the "totient of N", then if you raise some base to the totient of N power, modulo N, you always get 1 as a remainder. Stipulation: your base and N need to have no factors in common.[1]
Writing a totient function is easy, just count the number of totatives:
>>> def totient( n): return len(totatives(n))
>>> totient(100) 40
So now we might simply test Euler's Theorem, to see *what it means*. All too often, a proof is introduced before there's any understanding of the meaning or applications of a theorem. Here, we go for the meat, want to establish relevance first. Proofs will come later (maybe not until college in some cases).
>>> N = 100 >>> assert pow(3, totient(N), N) == 1 >>> pow(3, totient(N), N) == 1 True >>> N = 12 >>> assert pow(3, totient(N), N) == 1
Traceback (most recent call last): File "<pyshell#26>", line 1, in <module> assert pow(3, totient(N), N) == 1 AssertionError >>> assert pow(5, totient(N), N) == 1 >>>
Notice we broke our rule of no factors in common for a sec, had to change the base.
I don't find any YouTubes explaining this yet. My ShowMeDo clip on RSA doesn't count I don't think.
Why is any of this relevant. Because the next power higher than the totient power, or multiple thereof, will be b itself (the base). In public key cryptography, that base is our encrypted ciphertext, already to a power mod N, say the 7th power. In finding some d such that 7 * d == 1 mod totient(N), we're causing the ciphertext to divulge its prepower value. The only way to get d is to know N's two prime factors to begin with, and those we throw away. Finding them again is really computationally expensive (there're those calories again!). That's RSA in a nutshell, but in the actual curriculum, we have like four years to build out to it. We also study Diffie HelmanMerkle perhaps.[2]
We like to assign *trade book* readings more than physical textbook readings, e.g. 'In Code' and 'Cryptonomicon'. We handle exercises in class, over the Internet, or by scavenging from existing texts. FOSS gets us off that hugely expensive textbook treadmill, empowers teachers to swap lesson plans, use collaborative tools (like Anna knows about). This cost savings alone more than pays for the hardware, which is also inexpensive.
Again, we're talking industry standards here. At the Hyatt near O'Hare recently, I led a 3 hour workshop called Python for Teachers wherein I went through the RSA algorithm in some detail. Dr. Ian Benson (Tizard, Stanford) showed a video clip about HDM, which is used by Amazon.com apparently, to exchange confidential credit card information. We're talking real world relevant algorithms and a way to motivate what I think Dr. Renfro would consider "beyond Alg2" in some ways. However, thanks to our concrete, handson, constructivist approach, we're able to get there, at least in the pilots.[3]
Many complain that we "guinea pig" but cultures that don't experiment, try new things, simply wither on the vine. So I'm not about to apologize for being an experimentalist and encouraging others to be such as well. We explain everything to the parents, and mostly they approve of the results. Saturday Academy keeps asking me back. I have my eye on Alaska. I'd like to train more "clones of Kirby" although that's just an inhouse joke (we know we're not carbon copies of one another, each has a different angle and spin, even if we share a lot of the same materials).
Kirby
[0] http://mathforum.org/kb/thread.jspa?threadID=1918162&tstart=0
[1] http://en.wikipedia.org/wiki/Euler%27s_theorem
[2] """ DiffieHellman key agreement was invented in 1976 during a collaboration between Whitfield Diffie and Martin Hellman and was the first practical method for establishing a shared secret over an unprotected communications channel. Ralph Merkle's work on public key distribution was an influence. John Gill suggested application of the discrete logarithm problem. It had been discovered by Malcolm Williamson of GCHQ in the UK some years previously, but GCHQ chose not to make it public until 1997, by which time it had no influence on research in academia.
The method was followed shortly afterwards by RSA, another implementation of public key cryptography using asymmetric algorithms.
In 2002, Martin Hellman wrote:
The system...has since become known as DiffieHellman key exchange. While that system was first described in a paper by Diffie and me, it is a public key distribution system, a concept developed by Merkle, and hence should be called 'DiffieHellmanMerkle key exchange' if names are to be associated with it. I hope this small pulpit might help in that endeavor to recognize Merkle's equal contribution to the invention of public key cryptography. [1]
U.S. Patent 4,200,770 , now expired, describes the algorithm and credits Hellman, Diffie, and Merkle as inventors. """
[3]
We like the Escalante model, but why make him so dependent on LAUSD? Either let him teach teachers, or syndicate him through the Internet? Of course guys like that enjoy working directly with the kids, won't settle for some studio. On the other hand, you can have kids in the studio (Disney model, most kid programming  produce it as reality TV then?).
http://www.youtube.com/watch?v=FFMz8JRg8Y8
Do cutaways, don't just have talking heads. Saturday Morning is a wasteland these days, lots of moneygrubbing sugar pushers trying to supersize the kids, but without the common decency to put anything positively futuristic on the cereal boxes, not even the XO. The Lower 48 ag industrialists don't like children apparently. Why let misanthropes corner a strategic market? Homeland Security where are you?

