Visualizing DNA? (Probably not!)

Tags

Last week we did a week-long unit on ecosystem dynamics and evolution, which included the usual activities: looking at pond water microbes under the microscope, DNA extraction, walks in the woods (saw a snake!), predator-prey modeling, and so forth.

(Incidentally, we did our modeling in NetLogo, which is a terrific tool for teaching multi-agent modeling; I should do a separate post about this!)

Most this was run-of-the-mill science, and not too worthy of report, except for one interesting event.

DNA extraction from strawberries — using dish soap, salt, and alcohol — is about the most fun lab activity you can do in your kitchen! Here’s one of many all-the-same protocols you can find online. Unfortunately, all you get at the end is a huge clump of what is supposedly DNA. Since we were doing microscope work earlier in the week, I decided to try to visualize the DNA. My microscope goes up to about 470x (without oil), and since you need an electron microscope to see the helical structure at all, I figured that we wouldn’t see much in my light microscope.

However, when I was working in the lab we used a simple technique, called molecular combing, to stretch out the chromosomes in order to count them and get their sizes. I didn’t think that this would do anything useful in our kitchen, as you generally have to attach fluorescent markers to see the chromosomes in the lab, but I decided to give it a try anyhow.

Amazingly, just using the cover slip of the microscope slide to “comb” the strawberry DNA extract, we were able to visualize … well, I have no idea what this is:

20180822MolecularCombing

They sure do look like helical structures of some sort. I’m guessing that these aren’t DNA, unless strawberry DNA are humongous! Rather, they are probably some sort of connective tissue from the strawberries. But for our first try at visualizing something DNA-like, it was pretty exciting. (I didn’t let on to Leo that these are almost certainly NOT DNA!)

Incidentally, this “photomicrograph” was taken by just putting my iPhone up to the eyepiece of the microscope. It took a few tries, but I’m slightly amazed that it worked at all!



 

Raven Redux

Tags

, , , ,

(I actually had to look up “redux” to make sure that it wasn’t a synonym of “reduce”.)

Anyway…

So, you probably don’t recall — because I hardly did — that about year ago Leo and I wrote a Lisp program to randomly generate “poems” by randomly selecting words from The Raven. Leo has recently been reading my Lisp book (heaven help him!), and got interested in revisiting our old program. Rather than just rehash it, I thought that we could do something a bit more clever this time around, I explained n-gram language models (although not in those terms), and then hash tables, with the goal of writing much more interesting poems.

Leo started out in Snuffy Code, which is a programming language he invented for himself some time ago, and which is actually pretty close to what computer scientists call pseudo-code. Here’s his Snuffy Code version of the algorithm:

20180822SnuffyCodeRaven

You can see bits of our working on the data structures at the top, and to the right is a bit of our work on translating his Snuffy Code into Lisp. Here’s the Lisp:

(defvar *table* (make-hash-table :test #'equal))

(defun learn ()
  (clrhash *table*)
  (loop for sentence in *sentences*
        do
        (loop for (cur nxt) on `(:start ,@sentence :end)
                 do (push nxt (gethash cur *table*)))))

(defun compose-line ()
  (loop with cur = :start
        as options = (gethash cur *table*)
        as nxt = (nth (random (length options)) options)
        until (eq nxt :end)
        do (setq cur nxt)
        collect cur))

(defun compose-poem ()
  (loop for sentence in *sentences*
        as this-length = (length sentence)
        if (= this-length 0)
        do (print nil)
        else do (print (loop for random-line = (compose-line)
                              until (= this-length (length random-line))
                              finally (return random-line)))))

(In the previous post what is here called *sentences* was there called patterns, or p.)

All you need to do, then is:

(learn)
(compose-poem)

Et voila! (I’ve replaced the nils at paragraph breaks with double newlines.)

(DARKNESS PEERING LONG I PONDERED WEAK AND OMINOUS BIRD OR DEVIL)
(THEN THE RARE AND SAT ENGAGED IN THERE WONDERING FEARING)
(THIS EBONY BIRD AND THIS GRIM UNGAINLY FOWL TO BORROW)
(BY HORROR HAUNTED TELL THIS KIND NEPENTHE FROM AN UNSEEN CENSER)
(QUAFF OH QUAFF OH QUAFF OH QUAFF THIS MYSTERY EXPLORE)
(BUT THE NIGHTS PLUTONIAN SHORE)

(ON THE FACT IS THERE BALM IN THE NIGHTLY SHORE)
(WRETCH I PONDERED WEAK AND FOLLOWED FASTER TILL I SHRIEKED UPSTARTING)
(THOUGH THY MEMORIES OF A TAPPING AT MY FANCY INTO SMILING)
(FANCY UNTO FANCY THINKING WHAT THY FORM FROM AN UNSEEN CENSER)
(QUAFF OH QUAFF THIS I OPENED WIDE THE BUST AND STORE)
(TILL HIS CHAMBER DOOR)

(SHE SHALL CLASP A FEATHER THEN NO LIVING HUMAN BEING)
(IS SOMETHING AT MY HEART BE SHORN AND NOTHING MORE)
(NOTHING FARTHER THEN THIS AND BUST OF A FLIRT AND AN UNSEEN CENSER)
(OVER MANY A DEMONS THAT ONE WORD HE FLUTTERED)
(RESPITE AND CURIOUS VOLUME OF EVIL PROPHET SAID NEVERMORE)
(FOR THE LAMP-LIGHT GLOATED O ER)

(SIR SAID I NODDED NEARLY NAPPING SUDDENLY THERE SPOKEN)
(TIS THE PLACID BUST ABOVE HIS SONGS ONE GENTLY RAPPING)
(STARTLED AT MY BOOKS SURCEASE OF LORD OR BEAST UPON THE RAVEN NEVERMORE)
(ON THE RAVEN OF THE SAINTLY DAYS OF LORD OR DEVIL)
(PERCHED UPON A SAINTED MAIDEN WHOM THE SCULPTURED BUST OF THE NIGHTS PLUTONIAN SHORE)
(BACK THE NIGHTS PLUTONIAN SHORE)

(AS A MINUTE STOPPED OR BEAST UPON THE RAVEN OF YORE)
(THIS EBONY BIRD OF SORROW FOR THE COUNTENANCE IT WORE)
(TELL ME TELL ME AS OF BIRD BEGUILING MY CHAMBER DOOR)
(NOT A TAPPING TAPPING TAPPING AT MY HOPES HAVE FLOWN BEFORE)
(BUT THE SILENCE WAS UNBROKEN QUIT THE BIRD OF FORGOTTEN LORE)
(THEN METHOUGHT THE TUFTED FLOOR)

(BY THE SHUTTER WHEN WITH THE GRAVE AND THE CHAMBER DOOR)
(SWUNG BY THAT LIES FLOATING ON THE LAMP-LIGHT O ER)
(TIS THE SHUTTER WHEN WITH SORROW LADEN IF HIS CHAMBER DOOR)
(SHE SHALL CLASP A DEMONS THAT IS DREAMING DREAMS NO LONGER)
(SOME ONE GENTLY RAPPING RAPPING AT MY HEART BE LIFTED NEVERMORE)
(THAT IS ITS ONLY WORD LENORE)

(DESOLATE YET ALL THE ONLY THIS AND THIS KIND NEPENTHE AND THE FLOOR)
(FOR THE SILENCE WAS SURE I HEARD YOU CAME A TAPPING TAPPING)
(FANCY THINKING WHAT THIS SOUL WITHIN THE TEMPEST TOSSED THEE HERE I IMPLORE)
(SIR SAID I WHEELED A RARE AND THE STILLNESS GAVE NO CRAVEN)
(TIS SOME VISITOR I PONDERED WEAK AND THIS DESERT LAND ENCHANTED)
(NOT A TOKEN OF FORGOTTEN LORE)

(SHALL PRESS AH DISTINCTLY I HAD SOUGHT TO DREAM BEFORE)
(IN THE CUSHIONS VELVET SINKING I WISHED THE LAMP-LIGHT O ER)
(BUT THE FOWL WHOSE FIERY EYES NOW BURNED INTO THE LAMP-LIGHT GLOATED O ER)
(AH DISTINCTLY I CRIED THY SOUL WITH SUCH NAME LENORE)
(QUOTH THE COUNTENANCE IT IS SITTING STILL IF WITHIN THE NIGHTLY SHORE)
(AND SO APTLY SPOKEN)

(IT UTTERS IS I HEARD A BUST SPOKE ONLY WORD LENORE)
(WRETCH I SAT ENGAGED IN THE MORROW HE)
(TIS SOME LATE VISITOR ENTREATING ENTRANCE AT MY CHAMBER DOOR)
(SOME VISITOR ENTREATING ENTRANCE AT MY SOUL IN FRONT OF LENORE)
(CAUGHT FROM SOME LATE VISITOR ENTREATING ENTRANCE AT MY CHAMBER DOOR)
(OF A STATELY RAVEN NEVERMORE)

(QUOTH THE SHUTTER WHEN WITH MY HEART BE THAT IS DREAMING)
(BUT THE WHISPERED AND NOTHING FARTHER THEN HE UTTERED NOT A BUST OF YORE)
(SWUNG BY REPLY SO FAINTLY YOU CAME RAPPING AT EASE RECLINING)
(THAT NOW BURNED INTO THAT IS ON THIS AND NOTHING MORE)
(DESOLATE YET ALL THE AIR GREW DENSER PERFUMED FROM THE ANGELS NAME LENORE)
(THAT NOW TO DREAM BEFORE)

(TIS SOME LATE VISITOR ENTREATING ENTRANCE AT MY CHAMBER DOOR)
(AND THE RAVEN STILL A FEATHER THEN THE LAMP-LIGHT GLOATING O ER)
(GET THEE BY THE SEEMING OF THE FLOOR)
(AND BUST AND RADIANT MAIDEN WHOM THE BIRD BEGUILING MY DOOR)
(TIS SOME VISITOR ENTREATING ENTRANCE AT MY HEART AND MORE)
(PRESENTLY MY DOOR)

(TO THE ONLY STOCK AND THIS AND AN UNSEEN CENSER)
(SHALL PRESS AH DISTINCTLY I WHISPERED AND FOLLOWED FASTER TILL THE WHISPERED WORD LENORE)
(FANCY UNTO FANCY THINKING WHAT THEREAT IS AND NOTHING MORE)
(DOUBTLESS SAID I WHEELED A BUST ABOVE HIS CHAMBER DOOR)
(FOLLOWED FASTER TILL I THING OF SOME VISITOR I SHRIEKED UPSTARTING)
(LEAVE MY CHAMBER DOOR)

(THEN UPON A SAINTED MAIDEN WHOM THE ANGELS NAME LENORE)
(BUT WHOSE FOOT-FALLS TINKLED ON THIS EBONY BIRD OF EACH PURPLE CURTAIN)
(AND NEPENTHE FROM THY SOUL FROM MY SOUL WITH THE RAVEN SITTING)
(SIR SAID I SCARCE WAS UNBROKEN QUIT THE NIGHTS PLUTONIAN SHORE)
(TIS SOME LATE VISITOR ENTREATING ENTRANCE AT MY CHAMBER DOOR)
(BE SHORN AND NOTHING MORE)

(THRILLED ME WITH MY HEART BE STILL IF BIRD OF LENORE)
(MEANT IN THAT SHADOW ON THE SAINTLY DAYS OF YORE)
(MEANT IN GILEAD TELL ME AS IF WITHIN THE RAVEN STILL IS AND SO PLAINLY)
(BIRD OR FIEND I FLUNG THE NIGHTS PLUTONIAN SHORE)
(WHILE I STOOD THERE CAME A MINUTE STOPPED OR STAYED HE)
(THIS DESERT LAND ENCHANTED)

(WRETCH I WISHED THE FACT IS ON THE RAVEN NEVER FELT BEFORE)
(EVER YET WAS IN GUESSING BUT THE NIGHTS PLUTONIAN SHORE)
(PERCHED UPON THE TEMPEST AND STERN DECORUM OF LENORE)
(TELL ME I HEARD YOU CAME TAPPING AT MY CHAMBER DOOR)
(MERELY THIS SOUL WITH MY CHAMBER TURNING ALL THE ONLY WORD THERE SPOKEN)
(THIS DESERT LAND ENCHANTED)

(BY HORROR HAUNTED TELL ME TRULY YOUR FORGIVENESS I REMEMBER IT WORE)
(WHAT THY BEAK FROM AN ECHO MURMURED BACK INTO THE NIGHTS PLUTONIAN SHORE)
(BUT THE FACT IS SITTING LONELY ON THE NIGHTS PLUTONIAN SHORE)
(MEANT IN GILEAD TELL THIS GRIM UNGAINLY FOWL TO DREAM BEFORE)
(THIS GRIM UNGAINLY FOWL WHOSE VELVET-VIOLET LINING THAT THE MORROW HE)
(RESPITE AND SO PLAINLY)

(THEN METHOUGHT THE GRAVE AND FORGET THIS I THING OF MY WINDOW LATTICE)
(AS A RARE AND CURIOUS VOLUME OF PARTING BIRD OR DEVIL)
(TIS THE ONLY WORD AS A MIDNIGHT DREARY WHILE I WAS THE RAVEN NEVERMORE)
(RESPITE AND FORGET THIS HOME BY THESE ANGELS HE FLUTTERED)
(AND FOLLOWED FAST AND SO THAT ONE WORD THERE CAME RAPPING AT MY CHAMBER DOOR)
(THEN THE RAVEN NEVERMORE)

(LEAVE ME I SAID I NODDED NEARLY NAPPING SUDDENLY THERE SPOKEN)
(TELL THIS I STOOD THERE CAME A QUAINT AND NOTHING MORE)
(FOLLOWED FAST AND THE PALLID BUST OF HIS SOUL FROM THE DISTANT AIDENN)
(EAGERLY I MUTTERED TAPPING SOMEWHAT LOUDER THAN MUTTERED OTHER FRIENDS HAVE FLOWN BEFORE)
(BUT WITH MIEN OF PALLAS JUST ABOVE US BY THAT GOD HATH SPOKEN)
(ONCE UPON THE FLOOR)


Before going any father I must point out some of the gems from this run, and a few others from other runs of the same code:

(QUAFF OH QUAFF OH QUAFF OH QUAFF THIS MYSTERY EXPLORE)
(FANCY UNTO FANCY THINKING WHAT THY FORM FROM AN UNSEEN CENSER)
(TIS SOME VISITOR ENTREATING ENTRANCE AT MY HEART AND MORE)
(PROPHET STILL IS SOMETHING AT MY LONELINESS UNBROKEN QUIT THE RAVEN OF LENORE)
(RESPITE RESPITE RESPITE RESPITE RESPITE RESPITE RESPITE RESPITE RESPITE RESPITE AND FLUTTER)
(QUOTH THE CUSHIONS VELVET LINING WITH FANTASTIC TERRORS NEVER NEVERMORE)

and my personal favorite:

(THOUGH ITS ANSWER LITTLE MEANING LITTLE MEANING LITTLE MEANING LITTLE MEANING LITTLE RELEVANCY BORE)

That was fun. After Leo went off to other things I decided to do a little refinement of my own, so I did a trivial little hack to improve the flow a little. First I rewrote the data by separating the paragraphs (whereas, in *sentences* there’s no concept of a paragraph, except for the nils between them.) That is, I created this structure:

(defparameter *paragraphs*
  '(
    (
     (Once upon a midnight dreary  while I pondered  weak and weary  )
     (Over many a quaint and curious volume of forgotten lore  )
     (    While I nodded  nearly napping  suddenly there came a tapping  )
     (As of some one gently rapping  rapping at my chamber door  )
     ( Tis some visitor  I muttered  tapping at my chamber door  )
     (            Only this and nothing more  )
     )
    (
     (    Ah  distinctly I remember it was in the bleak December  )
     (And each separate dying ember wrought its ghost upon the floor  )
     (    Eagerly I wished the morrow  vainly I had sought to borrow )
     (    From my books surcease of sorrow sorrow for the lost Lenore  )
     (For the rare and radiant maiden whom the angels name Lenore  )
     (            Nameless here for evermore  )
     )
...and so on...
))

Then, by integrating learning and composition, and then simply localizing the global *sentence*, which both the learning and composition use, first to 3-paragraph windows for learning, and the to each paragraph for composition:

(defun compose-progressive-poem ()
  (loop for (p1 p2 p3) on *paragraphs*
        do (let ((*sentences* (append p1 (append p2 p3)))) (learn))
        (print '==============)
        (let ((*sentences* p1))
          (compose-poem))))

we get much better conceptual localization:

(EAGERLY I HAD SOUGHT TO STILL THE RARE AND NOTHING MORE)
(AH DISTINCTLY I WISHED THE BEATING OF EACH PURPLE CURTAIN)
(THIS IT IS AND CURIOUS VOLUME OF EACH PURPLE CURTAIN)
(WHILE I REMEMBER IT WAS IN THE BEATING OF FORGOTTEN LORE)
(TIS SOME LATE VISITOR ENTREATING ENTRANCE AT MY CHAMBER DOOR)
(AH DISTINCTLY I STOOD REPEATING)
==============
(TIS SOME LATE VISITOR ENTREATING ENTRANCE AT MY CHAMBER DOOR)
(AH DISTINCTLY I OR MADAM TRULY YOUR FORGIVENESS I STOOD REPEATING)
(THIS IT WAS SURE I SCARCE WAS NAPPING AND NOTHING MORE)
(NAMELESS HERE I SCARCE WAS SURE I HAD SOUGHT TO BORROW)
(SIR SAID I OR MADAM TRULY YOUR FORGIVENESS I STOOD REPEATING)
(NAMELESS HERE I IMPLORE)
==============
(PRESENTLY MY HEART I SCARCE WAS UNBROKEN AND NOTHING MORE)
(AND SO FAINTLY YOU CAME TAPPING AT MY CHAMBER DOOR)
(DEEP INTO THAT I WHISPERED AND SO FAINTLY YOU HERE I STOOD REPEATING)
(MERELY THIS IT IS I HEARD YOU CAME RAPPING)
(THIS IT IS I STOOD THERE AND NOTHING MORE)
(AND SO FAINTLY YOU CAME RAPPING)
==============
(PRESENTLY MY SOUL WITHIN ME SEE THEN NO TOKEN)
(TIS THE WIND AND THE SILENCE WAS THE CHAMBER DOOR)
(BACK THE SILENCE WAS SURE I OPENED WIDE THE WHISPERED AND NOTHING MORE)
(BUT THE STILLNESS GAVE NO MORTAL EVER DARED TO DREAM BEFORE)
(DEEP INTO THE FACT IS I SCARCE WAS SURE I SURELY THAT I IMPLORE)
(DOUBTING DREAMING DREAMS NO TOKEN)
==============
(NOT THE STILLNESS GAVE NO MORTAL EVER DARED TO DREAM BEFORE)
(LET MY CHAMBER TURNING ALL MY SOUL WITHIN ME BURNING)
(DEEP INTO THAT DARKNESS PEERING LONG I WHISPERED AND NOTHING MORE)
(TIS THE LEAST OBEISANCE MADE HE NOT THE ONLY WORD LENORE)
(DEEP INTO THE SAINTLY DAYS OF THE WHISPERED AND NOTHING MORE)
(TIS THE WHISPERED WORD LENORE)
==============
(THEN WHAT THY LORDLY NAME IS SOMETHING AT MY CHAMBER DOOR)
(PERCHED AND ANCIENT RAVEN WANDERING FROM THE NIGHTS PLUTONIAN SHORE)
(THOUGH THY CREST BE STILL A TAPPING SOMEWHAT LOUDER THAN BEFORE)
(TELL ME SEE THEN THIS EBONY BIRD BEGUILING MY WINDOW LATTICE)
(SOON AGAIN I SAID I SURELY THAT IS AND NOTHING MORE)
(BY THE LEAST OBEISANCE MADE HE)
==============
(PERCHED UPON A MINUTE STOPPED OR BEAST UPON THE SAINTLY DAYS OF YORE)
(NOT A FLIRT AND ANCIENT RAVEN OF THE SCULPTURED BUST OF YORE)
(IN THERE STEPPED A MINUTE STOPPED OR LADY PERCHED ABOVE MY CHAMBER DOOR)
(TELL ME WHAT THY LORDLY NAME IS ON THE COUNTENANCE IT WORE)
(WITH MIEN OF LORD OR LADY PERCHED ABOVE HIS CHAMBER DOOR)
(PERCHED UPON THE NIGHTS PLUTONIAN SHORE)
==============
(THOUGH THY LORDLY NAME AS MY SAD FANCY INTO SMILING)
(THEN THIS EBONY BIRD SAID ART SURE NO LIVING HUMAN BEING)
(THEN THE RAVEN SITTING LONELY ON THE MORROW HE WILL LEAVE ME AS NEVERMORE)
(FOR WE CANNOT HELP AGREEING THAT ONE WORD AS NEVERMORE)
(THOUGH THY CREST BE SHORN AND STERN DECORUM OF THE RAVEN NEVERMORE)
(BY THE NIGHTLY SHORE)
==============
(FOLLOWED FASTER TILL HIS SOUL IN THAT NO LIVING HUMAN BEING)
(CAUGHT FROM SOME UNHAPPY MASTER WHOM UNMERCIFUL DISASTER)
(FOLLOWED FAST AND FOLLOWED FAST AND FOLLOWED FAST AND STORE)
(TILL I MARVELLED THIS UNGAINLY FOWL TO HEAR DISCOURSE SO PLAINLY)
(TILL I SCARCELY MORE THAN MUTTERED OTHER FRIENDS HAVE FLOWN BEFORE)
(NOTHING FARTHER THEN HE FLUTTERED)
==============
(ON THE MORROW HE UTTERED NOT A FEATHER THEN HE FLUTTERED)
(ON THE MORROW HE UTTERED NOT A CUSHIONED SEAT IN THAT MELANCHOLY BURDEN BORE)
(ON THE RAVEN STILL BEGUILING ALL MY HOPES HAVE FLOWN BEFORE)
(TILL I SCARCELY MORE THAN MUTTERED OTHER FRIENDS HAVE FLOWN BEFORE)
(FOLLOWED FASTER TILL I WHAT IT UTTERS IS ITS ONLY STOCK AND DOOR)
(FANCY UNTO FANCY INTO SMILING)
==============
(STARTLED AT THE STILLNESS BROKEN BY REPLY SO APTLY SPOKEN)
(STRAIGHT I WHEELED A CUSHIONED SEAT IN FRONT OF BIRD OF YORE)
(WHAT THIS AND OMINOUS BIRD OF NEVER NEVERMORE)
(WHAT THIS I SAT DIVINING WITH MY HEAD AT EASE RECLINING)
(ON THE FOWL WHOSE FIERY EYES NOW BURNED INTO SMILING)
(OF NEVER NEVERMORE)
==============
(BUT WHOSE FOOT-FALLS TINKLED ON THE LAMP-LIGHT GLOATED O ER)
(THIS I BETOOK MYSELF TO THE FOWL WHOSE FOOT-FALLS TINKLED ON THE TUFTED FLOOR)
(THIS GRIM UNGAINLY GHASTLY GAUNT AND OMINOUS BIRD OF LENORE)
(WRETCH I BETOOK MYSELF TO THE LAMP-LIGHT GLOATING O ER)
(ON THE CUSHIONS VELVET SINKING I CRIED THY MEMORIES OF YORE)
(BUT NO SYLLABLE EXPRESSING)
==============
(WRETCH I SAT DIVINING WITH THE LAMP-LIGHT GLOATING O ER)
(QUOTH THE FOWL WHOSE FIERY EYES NOW BURNED INTO MY BOSOMS CORE)
(RESPITE AND MORE I SAT ENGAGED IN GUESSING BUT NO SYLLABLE EXPRESSING)
(RESPITE RESPITE RESPITE RESPITE RESPITE AND MORE I THING OF LENORE)
(WRETCH I SAT ENGAGED IN GUESSING BUT NO SYLLABLE EXPRESSING)
(SHE SHALL PRESS AH NEVERMORE)
==============
(WRETCH I CRIED THY MEMORIES OF EVIL PROPHET SAID I IMPLORE)
(CLASP A RARE AND RADIANT MAIDEN WHOM THE RAVEN NEVERMORE)
(PROPHET SAID I CRIED THY MEMORIES OF EVIL PROPHET STILL IF WITHIN THE RAVEN NEVERMORE)
(RESPITE RESPITE AND RADIANT MAIDEN WHOM THE RAVEN NEVERMORE)
(QUAFF OH QUAFF OH QUAFF OH QUAFF THIS DESERT LAND ENCHANTED)
(QUOTH THE RAVEN NEVERMORE)
==============
(IS THERE IS THERE BALM IN GILEAD TELL THIS DESERT LAND ENCHANTED)
(PROPHET SAID I THING OF EVIL PROPHET SAID I IMPLORE)
(CLASP A SAINTED MAIDEN WHOM THE NIGHTS PLUTONIAN SHORE)
(QUOTH THE TEMPEST TOSSED THEE BACK INTO THE ANGELS NAME LENORE)
(TELL ME TELL THIS SOUL WITH SORROW LADEN IF WITHIN THE RAVEN NEVERMORE)
(QUOTH THE DISTANT AIDENN)
==============
(AND MY HEART AND TAKE THY FORM FROM OFF MY CHAMBER DOOR)
(TAKE THY SOUL WITH SORROW LADEN IF BIRD OR FIEND I SHRIEKED UPSTARTING)
(TELL THIS SOUL FROM OFF MY SOUL FROM OFF MY DOOR)
(PROPHET SAID I THING OF EVIL PROPHET SAID I SHRIEKED UPSTARTING)
(SHALL CLASP A DEMONS THAT HEAVEN THAT GOD WE BOTH ADORE)
(AND MY CHAMBER DOOR)
==============
(LEAVE NO BLACK PLUME AS A DEMONS THAT SHADOW ON THE RAVEN NEVERMORE)
(AND HIS SHADOW ON THE RAVEN NEVER FLITTING STILL IS DREAMING)
(AND THE LAMP-LIGHT O ER HIM STREAMING THROWS HIS SHADOW ON THE RAVEN NEVERMORE)
(BE THAT LIE THY BEAK FROM OFF MY CHAMBER DOOR)
(AND THE LAMP-LIGHT O ER HIM STREAMING THROWS HIS SHADOW ON THE NIGHTS PLUTONIAN SHORE)
(AND THE RAVEN NEVERMORE)
==============
(ON THE PALLID BUST OF PALLAS JUST ABOVE MY CHAMBER DOOR)
(AND THE RAVEN NEVER FLITTING STILL IS SITTING STILL IS SITTING)
(AND HIS SHADOW ON THE SEEMING OF PALLAS JUST ABOVE MY CHAMBER DOOR)
(AND HIS EYES HAVE ALL THE SEEMING OF A DEMONS THAT IS DREAMING)
(AND THE PALLID BUST OF A DEMONS THAT LIES FLOATING ON THE FLOOR)
(SHALL BE LIFTED NEVERMORE)


 

 

 

 

 

 

 

NP Complete 3rd Grade Math Problems

Tags

, , ,

Leo’s third grade class got to try a Noyce Foundation math worksheet [1] the other day. They didn’t fare so well, but I gotta tell you, some of the problems are REALLY hard! In fact, one of them is NP-Hard! Now, I’m sure that there must be a trick to this problem, but I wasn’t able to see it in the couple of minutes that I thought about it. In fact, Leo even recognized that it’s NP-Hard; He told me the day of the quiz that they had given out an NP-Complete problem! (In fact, if you look closely at the page, you’ll see that he wrote “NP Compleite” (Sic 🙂 ) diagonally across the picture:

OrigProblem

One of the things I’ve told my students over the years, only half jokingly, is that computer scientists are fundamentally lazy; Why should we work when we can get a computer to work for us?! Since I couldn’t figure out off the top of my head how to solve this problem without trying all possible combinations (and god help you if you allow repeats!), Leo and I set about writing a program to solve it for us.

Without going into great detail, here’s the code:

Screen Shot 2018-03-25 at 9.56.26 AM

*Items* is the list of items as pairs, as: (name . price):

Screen Shot 2018-03-27 at 10.40.07 AM

 

The only interesting function here is the combs function, and that’s the only one that I bothered to work through in detail with Leo. We first set out the recurrence on the board (bottom to top, excluding the top line, which is the input):

Combos

Leo got the recurrence pattern right away, although I, of course, had to help him put it into Lisp. (Compare with his Snuffycode version, below.)

Of course, first making a huge list of all possible combinations, and then scoring each one, is extremely space-inefficient. A depth first search would be better, but making all the combinations first is conceptually simpler.

Anyway, space-wasting aside, calling it (via seek$) results in 279 non-redundant solutions.

Screen Shot 2018-03-27 at 10.40.56 AM

Here are the first few:

Screen Shot 2018-03-26 at 6.09.51 PM

We also found the shortest and longest solutions (shortest was 7 — the reduce…mapcar got cropped out of the screencap):

Screen Shot 2018-03-26 at 6.09.21 PMScreen Shot 2018-03-26 at 6.10.42 PM

After all this was done, Leo wanted to write the program in “Snuffycode”, his own private programming language (for which, thank goodness, neither a compiler or interpreter exists):

SnuffyCode2

Note that this code uses a different search method, counting up to 2^20, and using binary expansion to select the item list. Snuffycode, being a bit like APL, has implicit type conversion (L=N), operators that select a subset of an array when the array index is represented in binary (A[L]), and an operator that sums up arrays (/ \). 🙂

By the way, Leo says that some kids actually solved the problem exactly, so there may be a trick that wasn’t obvious to Leo or me, or maybe they just got lucky. It seems to me that there must be a trick, because if you’re only looking for 1 solution in 279 out of 2^20, that’s about a 1 in 3000+ chance of finding it by luck. (The problem might be easier is you allow redundant solutions. Although that makes for many more possible solutions if you were brute-forcing it (technically, an infinite number! … although you could apply a sensible limit), you maybe could do some sort of stacking up to a target that you can then fill in….or some such algorithm.

Like I said at the outset, it’s not worth thinking deeply about such a small problem; That’s why we invented computers!


By the way, the problems in the Noyce set were supposedly in difficulty order, and this was only the second of five problems! I solved the third one using straightforward algebra (although apparently some of Leo’s classmates solved it by brute force — remember, these are THIRD GRADERS!). The fourth required slightly more complex algebra.

The fifth problem was extremely easy, if you know anything about probability.

Go figure…


[1] Unfortunately, I think that the Noyce Foundation has ceased operations.



The Dragon Box Algebra Teaching Game

Tags

, , , ,

Over the past couple of weeks, Leo and I have worked through the entire Dragon Box Algebra 12+ app. Dragon Box builds a series of gamified math apps. I can’t speak to any of the others, but Algebra 12+ (hereafter, DBA12+) is about as fun as I could imagine making Algebra, unless, like me, you think that Algebra is just inherently fun on its own! Unfortunately, DBA12+ has, to my mind, some significant flaws.

Note that Leo is only 8 (closer to 9), and I’m not sure what the “12+” means — probably target age — so I hadn’t expected the thing to be self-usable by an 8/9 year old. So Leo and I worked every problem together, although I tried to do my best hands-off scaffolding by only intervening when he was absolutely stuck — although sometimes I was absolutely stuck as well! Another thing that I did was to provide running commentary, giving names, and sometimes explanations, to back up the algebraic concepts being demonstrated, or those he was employing in play. In  my parent-child interaction research we called this “active language”, and we hypothesized that this matters…a lot! I’ll back to this below.

First some of the great things about the game. The central conceit and motivation is well designed and fun: You are feeding a creature in a box to make it grow from an egg into a big scary (in a fun-scary sense) creature. (The box is your algebraic unknown — generally “X”, as will be eventually revealed.) The artwork is great, and the goal is motivating (at least to an 8/9 year old). The moldularization and “leveling up” of the algebra content is well done too. There are around 10 major levels, each with 20 problems. New capabilities, like factoring, are introduced usually at the major level breaks, and new equation-level structural complexities are introduced within levels. This works extremely well, and the problems are extremely well designed to very rapidly bring together and reinforce previously learned capabilities into more and more complex problems without being either boringly redundant, nor taking too large steps. Leo (sometimes with my help around the edges) was able to “solve” pretty much every problem, although the latter problems sometimes took a lot of exploration — sometimes blind trial-and-error.

One thing that DBA12+ does that is, one the one hand very clever, but on the other hand somewhat annoying, is to begin with entirely non-mathematical symbols, specifically, pictures of funny creatures, and then as you level up, it introduces more and more mathematical notation. Sometimes this works, and sometimes it doesn’t. I think that the creatures are supposed to represent symbols that you might see in an algebraic expression, like A, B, M, N, and Y, and the box is always definitely X. But soon enough numbers are introduced (as dice-sides, initially, as with dots, and eventually as numbers), but there are operations that work on numbers that don’t work on symbols, like factoring, so you sort of have to figure this out by trial and error, because the animals could just as easily have been representing numbers!

There are some unfortunate quirks imposed by a combination of the gamification and the requirements of the leveling-up educational sequencing. For example, until very late in the game you are only allowed to add/subtract/multiply/divide through by “reified” terms that it offers you at the bottom of the screen. This blocks some paths that would make sense (to me at least), and which would potentially provide simpler solutions. In the next-to-last level of the whole game you are given an operator that will make (almost) any term in the current equation into a “reified” term, and at that point you can do what I we were reaching for throughout the game to that point!

Another pretty painful aspect of DBA12+ is that although there is a “help” button, it only gives you the complete solution, not hints nor steps that you might consider. So if you’re in the middle of a solution, it’s not smart enough to give you a hint from where you are; You just have to follow it back to its one-and-only-one “correct” solution. (Their solutions are actually often more complex than necessary. In about a quarter of the cases we were able to find solutions that are shorter than theirs!)

One significant problem is that what DBA12+ counts as a “correct” solution is sometimes a bit hard to fathom. A target number of steps is given for solving the problem, and if you go over those, you don’t get “full credit” (three stars). This has the positive effect of tending against “random” solutions where you just keep moving things around until you get something, but it also tends against a very useful strategy, which is to simply move things around until you get a solution, then you’ll know what the solution is, and can start over and work on a more efficient path. Like many games, once you “try”, where you are correct or not, the solution vanishes into the next problem, so you don’t really get a chance to think about your solution. There’s actually no way to think about your solution, because there’s no way to review it. This would be a nice addition: A way to look at the steps you took to get to wherever you find yourself, whether right, wrong, or in the middle of the solution.

Another aspect of DBA12+’s obscurity with regard to “correct” solutions is there there are certain forms that it is expecting as “the correct answer”, and others that are formally correct (because, of course, you’re only allowed to correctly apply algebraic rules), but which are somehow, to DBA12+’s mind, not simplified enough … or something. Because there are no words in the thing, except for the work “Yuk”, when it doesn’t like your solution, it can’t explain to you why it doesn’t like certain solutions. So you are sometimes — quite often, in fact — left guessing as to what it didn’t like about your solution, and just trying different things randomly to try to get to a solution it likes. In a similar vein, when there just a singleton box left on either side of the equation, it considered you to have completed the problem, and tries to “eat” everything on the other side, like it or not! I would have preferred, for all of the above, a button called “Try” (or somesuch name or appropriate icon) which, when pressed, the dragon comes out of the box and tries your solution, and if it doesn’t like it, you get to continue working, or back out, etc. And it would be great if, when it didn’t like something you left it, it told you why.

This leads me to my main criticism of DBA12+, which is that there are no explanations at all at any time, no explanations of why it doesn’t like you solution, and no naming of operations. To my mind, this significantly diminishes the educational utility of the product. If I was designing this app, as new operations were introduced, I would provide “active language”, giving names to the operations, as I was over Leo’s shoulder, like factoring, dividing or multiplying through, and so forth. And I would explain the constraints on when you can and can’t do these in terms that made sense to him in the context, using the vocabulary we had built up. Unless you have someone who knows Algebra pretty well sitting over your shoulder, there’s just no way you can make sense of some of the constraints that are either inherent in algebra itself (like that you can’t add fractions that don’t have a common denominator), or those imposed by DBA12+, like you can only do integer arithmetic, and can only factor certain things and not others, or those leading it to disliking certain solutions that it simply thinks are “Yuk”y. If, when new capabilities are introduced it would give them names, like factoring or distribution, and then these were maybe flashed on the screen whenever you used them, it would enable so much more depth of understanding of what’s going on. For example, you might be able to tell that factoring a common term out of a parenthesized expression is closely related to factoring a number, or that the “through” operations (dividing through, etc.) are related in terms of their application across all the terms. It could also use these terms in hints (e.g., “Maybe consider factoring?”), and in explanations for Yukky (Yuky?) results (e.g., “This isn’t in its simplest form!”)

After we went through the whole game, I had the opportunity to test Leo’s understanding of algebra in a natural experiment that happened to arise when we were talking about the earth’s polar regions. He asked why “they chose” -40 to be the same in Fahrenheit and Centigrade” (His hypothesis was that the folks who invented temperature, or perhaps just centigrade, lived in a polar region! 🙂 ) Aha! A perfect opportunity for some algebra! (The benighted reader can easily work this out for him or herself by taking the equation: C=5/9(F-32), or whatever version of that you like, asserting the fixed point: C=5/9(C-32), and then solving for C!) I used the DBA12+ conceit by making the C into a box, and asking him to solve the equation, just like in DBA12+. There are, of course, many paths to get to C=-40, but the DBA12+ way, where you can only do integer arithmetic, and can’t distribute composite terms (like 5/9) is to start from C=(5(C-32))/9, multiply through by 9, yielding 9C=5(C-32), distribute the 5 to get 9C=5C-(5*32), isolate: 9C-5C=-(5*32), do the math (on both sides): 4C=-(160), simplify out the minus sign (could be done earlier, or by distribution, or just drop the parens): 4C=-160, and then divide through by 4 to get just C=-40.

Notice how nice it is to express this solution path in a combination of words and symbols, and how if we were going to have a conversation about it, we’d be diminished to grunting and pointing if we didn’t have names for things! Active Language provides these names and ways of speaking about activity, and through this process forms the foundation for reasoning.Human language is possibly our only unique feature, and it is probably the most ennobling and enabling!  Unfortunately, by trying to force absolutely everything into gestures, DBA12+, and similar “educational” games, diminishes their topic, algebra in this case, to mere grunting and pointing.



Portal Physics

Tags

, , , ,

Elsewhere I’ve briefly written about Leo’s obsession with Portal, a clever, (mostly) non-violent, Steam game. As always, I try to turn his obsessions into lessons (I should trademark that!) and so it is with Portal. In another post I talked about the game’s clever “AIs” (scare-quoted because, of course, they are merely scripted, not real AIs!) Here I talk about a cool little physics lesson that we recently did using Portal.

One of the really fun and clever things that you can do with portals is to put an In-Portal in a floor, and an Out-Portal in a wall, and then drop something into the In-Portal and it’ll come out of the wall. If you drop it from a distance into the In, it’ll blow out the Out with what we shall hypothesize is the same horizontal velocity at which is hit the In in the floor.(Watch this happen quite dramatically at about 4:40 in this video.)

This can be quickly turned into an interesting physics question: How high do I have to jump from such that I go a specified distance across the room? Here’s the setup (I’ve redrawn all this because we initially did it on a white board, and between erasures and scribbling, the white board is entirely incomprehensible!)

20180223-PortalPhysics1

A box is dropped (or a person jumps!) from the tube at the top left at a height of Hf, and accelerates (presumably at 9.8m/s^2), hitting the In portal (the circle at the bottom left) with Vf. It instantaneously blows out of the Out portal (the circle on the wall in the middle left of the picture, at a height of Hp) with the same velocity, Vf and immediately begins to fall, eventually hitting the floor and stopping at distance D. (We neglect a lots of the usual things like rolling along the floor, air resistance, and that the box isn’t a point mass.)

The question is: How high to I need to put the Out portal (Hp), if the drop point (Hf) is, say, 20 meters high, and I want the box to land (D) at, say, 20meters from the left wall?

Notice that there are three equations involved here [all equations from this wikipedia page, or any of the other zillion pages that have the same info]: For the drop we can compute Vf from Hf (20m) (given g=9.8m/s^2). But in order to figure out how far it’s going to go to the right after coming out of the wall need to compute for how LONG (i.e., t in secs) we want it to travel in order to hit the ground in D (20m), and then back-compute the high (Hp) given how long we want it to be in the air before hitting the ground.

Okay so V_f=V_0+{\sqrt{2gH_f}} [Since the drop is static, V_0=0.] We’ll round 9.8 to 10m/s^2, so V_f={\sqrt{20*10*20}}={\sqrt{20^2}}, which, coincidentally, is really easy to calculate: Vf=20m/s.

Okay, now at 20m/s going 20m upon exit from the Out portal, leads to the sort of trivial use of t=D/V_f=20/20, which is exactly 1 sec. (I actually didn’t make these numbers up to come out so nicely!)

Finally, we need to figure out how far something will fall in 1 second, which is just 1/2*g*t^2, where t=1, and g=10, as above, so H_p=1/2*10*1 = 5 meters. So, we have to put the (center of the) portal 5 meters up the left wall.

By a little algebra we can reduce these three equations:

V_f={\sqrt{2gH_f}}
t=D/V_f
H_p=1/2*g*t^2

into one:

H_p={gD}/({2\sqrt{2gH_f}})

I’ll update this post with a screen cap from Leo’s actually implementing this so check it out (spoiler alter: it worked out pretty well!)

[By the way, there are many quite clever videos where people work out aspects of the physics of Portal, as well as many funny thought experiments about what could happen if portals were real!]

 



 

8-year-old Kid v. 45-year-old Pseudo AI

Tags

, , , ,

I’ve variously been on again off again regarding computer/video games. Early on I had this fantasy concept that Leo would only be allowed to play computer games that he programmed himself, and that held for a little while, during which time we created some interesting, although laughably poor, games on the HopScotch platform. Since then we’ve engaged in several rounds of brief run-ins with puzzle games such as Where’s My Water and Monument Valley, and a couple others. We finally came to a mutual landing on Minecraft, which is at least slightly creative, and has a lot of programming and math_ed potential. Still, his media (including games) time is quite limited.

Another game that Leo has become enamored with (within the tight content and time controls that we put on him) is Portal, which is an extremely clever puzzle game with amazing graphics. (It has a tiny bit of robot violence, but is generally just a clever puzzle.) One of the best parts of Portal is that your adventure through the “lab” is narrated by an AI companion, named Glados (in Portal 2 it’s Wheatley). There some kind of complex back story, where Glados was a person uploaded into a computer, but Wheatley is a fully self-conscious AI. Of course, what these “AI”s say is completely canned, but it’s also (sometimes) clever and (often) funny.

Somewhat to my surprise, Leo’s interest in the games, combined with the (sometimes/often) clever/funny commentaries from the companion (pseudo) “AI”s has gotten Leo interested in AI more generally. Yesterday, Leo was monkeying with the Chegg flashcard app on my phone (for no reason other than wasting time on a long car ride), and, unbidden, he created some AI flashcards:

I have a bit of personal history with this sort of AI, having been the author (many many year ago — like, 1973!) of a BASIC version of Eliza that ran in very early PCs, and so became extremely popular. Indeed, I’ll bet that my Eliza is about the most knocked-off (as in copied/modified) program on the planet!

I happen to have a copy of Peter Schorn’s iAltair on my iPhone that coincidentally comes with a close knock-off of my actual old BASIC Eliza! So, since Leo is interested, having done the AI flash cards, I put him on my Eliza, now, um, 2018-1973=45 years later!

Here’s their conversation:

LeoandEliza1LeoandEliza2
LeoandEliza3LeoandEliza4LeoandEliza5
LeoandEliza6

A while back we did a little toe-in-the-water experiment, using Lisp to write (bad) poetry. So, next week we’re going to start writing our own AI!



 

Car Physics Revisted

Tags

, , , ,

Long long time ago (actually, only back in 2015) we tracked a short road trip and manually computed and plotted the Time/Distance/Velocity/Acceleration. I’ve been wanting to revisit that fun little experiment, and this past weekend we had the opportunity on a 60-mile trip. Leo recorded our distance from start every five miles. This time, instead of manually plotting (which he does a lot of in school), I started him on Excel, which is certainly how he’ll be doing this once he gets beyond 3rd…or maybe 5th grade!

Here’re the results (you can see the master by clicking the pic):

20171230_CarExperment_STEMHacks_Workbook

The valley in the middle of the trip is where we stopped for lunch and turned around. And, yes, we really did travel exactly 60 miles, although that wasn’t planned!



 

Calculus Craft

Tags

, , ,

Okay, so I’m a little slow! I’ve been working my way toward calculus with Leo for a long time. We’ve explored a great deal among the preliminaries, such as algebra, geometry, and trig, done a little “real life calculus” using cars and rockets, and I’ve even left various fun “calculus coloring books” around, which he’s picked up and variously paged through. We’ve even done some Minecraft-math before that verges on calculus. But until today I hadn’t really broached any real calculus.

Today it hit me that Minecraft provides a perfect setting to discuss integration via Riemann Sums (which most of you will remember as the method of rectangles). The reason is obvious: In Minecraft you (generally) only have rectangles, so if you want to know the area under something — say the roof of semi-circular building — you don’t have any choice but to build the thing out of blocks. Therefore, the actual area is actually most conveniently measured in terms of piles of blocks, i.e., rectangles, i.e., the basis of the Reimann Sums!

Once I realized this it took only a couple of minutes to come up with some easy examples. To you and me, this just looks like simple intro calculus, but the “patter” — the story I was telling all the way through — is all about Minecraft!

IMG_0737

Next I explored the idea that if the blocks were smaller, the approximation would get better and better. Conveniently, the Minecraft blocks are 16-units wide, so you can divide them in half four times and still be working with integers, making it easy to actually work the detailed math.

What’s most interesting about this is that because of Leo’s facility with Minecraft, once he had his Minecraft thinking cap on (which, once on, is extremely hard to get off!), he was able to see right away how the simple version of the rectangle-based integration worked, and was also able to easily think through (approximately) how things would go if the blocks were divided in half, and then half again and again and again!

In the last example (second half of the page) Leo worked the Integral[X^2] by rectangles while I worked it by the usual (X^(N+1))/(N+1) method. (I had to help him a little with his.) And we both got about 42, which is about right! (Actually, it’s 125/3 = 41.666…)

I think that this (somewhat “duh”) realization of the relationship between Minecraft and Calculus has opened up our whole next level of math fun!



 

Magic v. The Machines: Septimus Heap, Hyper-Literal AI, and Public Key Encryption

Tags

, , , ,

For a long time, now, Leo and I have been listening to audio books of long Fantasy and Steam Punk series, and at some point I’ll write a post — or probably several — about our responses to these, as there’s a lot to say. But occasionally we are able to make a contained and useful lesson out of some tidbit in these series. For example, the wonderful Leviathan series by Scott Westerfeld offers many opportunities ranging from discussion of evolutionary theory to the inventions of Nikola Tesla.

One of the ongoing issues that Leo and I discuss around these various series is the difference between fantasy and science fiction (or steam punk, which is what we tend toward). This is, of course, not a simple question, and the answer is probably as philosophical as it is problematic, so I’m not going to offer any deep theory of it here. But only of the things that is more-or-less clear is that in fantasy you can just make things up, that have no bearing at all to possible physical reality, whereas in SciFi/steam punk, there is generally some plausible way in which at least most of the things that play a role in the story could have some plausible reality in our real universe. So, in fantasy you find magic, whereas in SciFi you get machines. Whether the machines are really plausible is debatable — sometimes they’re time machines, for example! But at least there’s no explicit magic in SciFi. SciFi sort of has to follow the rules, whereas fantasy came just make up magic. In fact, this is one of the problems with fantasy: If you can make up random magic, why can’t you just make up magic that solves whatever problem you have. Fantasy writers end up creating endless random constraints on their magic in order to keep the story interesting. (“You can only use the magical Time Turner twice on Tuesdays between the hours of 3 and 4 pm when the moon is blue.” … or whatever …)

The opposite direction is less constrained; You often find steam-punky-quasi-machines in fantasy: Doors with special complex locks seem to be a favorite, with special keys scattered all about. The series that we’re listening to at the moment is the extremely long, but wonderfully written Septimus Heap series, by Annie Sage (hereafter SH).

There are many interesting things about this series (and about all of the series that we’ve been reading and/or hearing), but I just want to draw out two small details in SH that struck me as particularly interesting and funny, in a somewhat STEM-educational sense.

Hyper-Literal AI Self-Driving Sled Gone Wrong

The climax of the 5th book in the SH series, Syren, turns on a bunch of under-sea tunnels, called “ice tunnels”. It’s not giving away too much to tell you that in order for our heroes to get through these tunnels fast, they utilize a magical sled, which they can call remotely, and which is some sort of AI that they can tell where to go within the ice tunnels. At one point our heroes call the sled, which shows up (just in time, of course!) and upon climbing aboard, they tell the sled to “Head for the nearest hatch!” The sled takes off at a shot, but in the wrong direction! Too late they realize that what they should have said is: “Head for the nearest hatch in the castle!” The literally nearest hatch is in the opposite direction!

Public Key Encryption Saves (actually nearly loses) the Kingdom to the Dark Domain

The resolution 6th book of the SH series, Darke, turns on the decoding of a spell that will save everyone from some sort of magical evil, called the “Dark Domain”. The spell is protected by a complicated split key book cipher, with a few interesting properties. First, interesting property of the cipher is that each part lives on a circular disc — something akin to a DVD, but where you can read the “bits” off it with a strong magnifying glass. The circularity of the discs introduces an interesting problem, which they make a bit of in the story, which is that you don’t know where to start on a circular cipher! You could use the grammar of the language, or try all 49 (in this case) starting points, but Sage pulls out plausible escape clause that these are many hundred year old spells, and also that if you get it wrong you could do more harm than good. Hilarity ensues, and, of course, good triumphs over evil at the last possible moment.

(Another slightly funny aspect of this situation — if you’re 8 years old! — is that one of the halves of the split key had been eaten by one of the bad guys. The heroes had to get him to throw it up, and then utilize the disgust-covered disc! I guess it could have been worse! 💩 )

All this is very interesting (or perhaps not), but the point for the present is that Leo and I were able to use this imaginary cipher as a jumping off point for discussion of public key encryption, which is also a split key cipher, the details of which basically followed this excellent Numberphile video. (Numberphile, by the way, is a terrific video series on math … or as the Brits call it, “Maths”.)


 

Bayes Rule for 8-year-olds

Tags

, , ,

Leo has been fascinated for some time by the probabilities of things. He’s telling us all the time about the probability that, for example, the light will turn red before we get to it, or a meteor will destroy the earth tomorrow. Of course, he’s totally making up the numbers, although he does know that a probability lies between 0 and 1 (inclusive), and that when something can’t possibly happen, it’s p=0.0, and when it either is sure to  happen, or has already happened, it’s p=1.0 He also knows the general principle that p of n equally-likely events is 1/n, and he sort of gets the p of complex things generally in the right range. (For example, he puts the probability of the meteor at 0.0000…lots of zeros…and then a 1.)

Given that he’s fascinated by probabilities, my main principle of teaching, “Catch ’em while they’re interested!”, suggests taking this to the next level, so today we started into Bayesian probability updating. In order to do this, I had to devise a particularly simple example. Biomedical tests (a typical example) aren’t really gonna work for him. So I invented a little card game, that goes like this:

Take N ordered cards … I’ll start with 3 for these examples … so, say J Q K of the same suit. Could be 1 2 3, but I don’t want to get all confused with the numbers, so actually, I’m just gonna call them A B C. Shuffle them and lay them face down. Now, the question (hypothesis, in Bayesian terminology) is whether they have been laid out in order: ABC.  p(H) at this point is obviously 1/6 (could be any of ABC ACB BAC BCA CAB CBA) — this is our prior.

Okay, so we turn over the first card. In the easy case, it’s not an A. Intuitively, p(ABC|first<>A) should be zero, and indeed, if we use Bayes’ rule to compute p(first<>A|ABC) = 0, so the whole equation just obviously becomes zero, regardless of the other terms.

What? Oh, you’ve forgotten Bayes’ rule….Here you go:

p(H|D) = (p(H)*p(D|H))/p(D)

So, one more time, p(D|H) = p(ABC|first<>A) = 0, so regardless of the other numbers in the equation, the result is 0. (Assuming p(D) isn’t zero, which it never is in any real problem.)

Okay, now suppose first = A. What’s the “posterior”, that is the new p(ABC|first=A)? Now we have to ask about p(D) and p(D|H). p(D|H) = p(first=A|ABC) = 1 because it had to be an A if the hypothesis was true. Okay, so what’s p(D). Well, that’s just 1/3rd since there are three letters (ABC).

(You might be lured into thinking that P(D) is 1/2, since you’ve used up one of the letters (A), but that would be P(D|first=A), but at this stage we have all three letters. It’s common to confuse the order of explanation with the order of term evaluation in the equation! Just p(D) is unconditional at this stage, and is just the probability of the data given just the structural properties of the situation. At this stage that is all three letters, so 1/3, whereas at the next stage, it’ll be only two letters.)

Recall that p(H) was 1/6th (six possible sequences, as above).

So you end up with:

p(ABC|first=A) = (1/6 * 1)/(1/3) = 3/6 = 1/2

(Remember how to divide fractions? Invert and multiply!)

So there’s now a 1/2 = 0.5 = 50:50 chance that it’s the right sequence, i.e., ABC given that the first card is an A. That is: p(ABC|first=A)=0.5. This accords with intuition since there are now only two possible orders for the B and C cards.

Now, when we turn over the next card, and see that it’s B. At this stage, p(D) = 1/2 (only two possible letters!), and p(D|H) = 1, and the p(H) = 1/2 from the previous stage (that stage’s posterior is this stage’s prior!) = 1/2. (This could also be written p(D|first=A)). So we have p(ABC|first=A & second=B) = (1/2)/(1/2) = 2/2 = 1. Tada!

And, of course, if we’d turned over C here, again p(D|H) would be 0 and the whole thing would come to a crashing zero again, which, again, correctly accords with intuition!

It’s fun to go to very large numbers, which Leo also likes. That’s easy to do using cards by just asking exactly the same question as above, but using all 52 cards, that is, p(ABCDEF…). We know that, given a fair shuffle, this is very very very very small. (Here’s a terrific video about how very very very very small a given ordering from a shuffle really is!) I’ll call this “epsilon” (a number very very very very very close to zero!)

So in this case p(H) = epsilon (~=0), and p(D) = 1/52 the first time through.So although getting an Ace of Spades (assuming that’s what you are counting as the first ordered card) multiplies the probability 52 times, it’s still very very very very small, and will continue to be so for a very very very long time!

So, now I have to start engaging Leo when he generates random probabilities, for example of meteorites hitting the earth tomorrow, to reenforce his Bayesian thinking.

Postscript: Just a couple days after I posted this, the medical case actually came up in conversation. Leo was reading a book about a little girl who became deaf due to meningitis, and he became worried about whether he had meningitis, and how he would know. So we talked about how very unlikely it is in the first place (p(H) [prior] is very small), and how if he just had a headache, that made it more likely, but not a whole lot more likely (Although p(D|H) is high, p(D) for a headache is also pretty high, so they more-or-less cancel.) But that if there were two symptoms, like a stiff neck AND a headache … etc … and we sort of verbally worked through the equation, at least intuitively. (This was a car conversation, so I wasn’t about to whip out a pencil and calculator, much less real incidence data about headaches and meningitis.) He ended up being a lot less worried about having meningitis, so I guess that Bayes’ rule is actually good for kids to understand, at least intuitively.