davidbau.com

Tutorial: Root Finder

A basic similar triangle problem: solve for x₂.

Because the two triangles are similar we know that the ratios of the lengths are the same:

Multiplying through and solving for x₂, we get:

This formula is the core of an ancient idea for solving arbitrary equations.

Getting out of Algebra Homework

In an effort to make an algebra-homework-solver, Anthony recently built a simple root-finder on his own that probed values at constant 0.1-separated values of x, looking for sign changes.

After he worked on it for a long time, he came to me trying to explain the idea, and showing me that it did not work that well because it was too coarse.

So I showed him the secant method, and we coded it up as a javascript example here.

The Secant Method

Suppose we have already made two incorrect guesses while searching for a zero of a function, and at those two values, the function passes through the points (x₀, y₀) and (x₁, y₁). We could continue making more guesses by crawling along the number line, looking for a sign change or for a point with y values closer to zero.

But the secant method tries to jump straight to the answer by drawing a straight line between the two observations and calculating the point x₂ where that line crosses zero, as above.

If the initial guesses are close enough, the method converges very quickly and makes mincemeat out of polynomial root finding.

Hopefully Anthony will continue to work on his algebra homework by hand anyway.

History of the Regula Falsi

The secant method is similar to Newton's method but does not require knowledge of derivatives or other calculus. It is sometimes described as a finite-difference approximation to Newton's method. However, it actually predates Newton.

Joanna Papakonstantinou has unearthed evidence that the secant method was being used by Babylonians and Egyptians in 18th century BC to solve linear relationships and by Chinese scholars to approximate nonlinear relationships in the 2nd century BC. The idea of drawing a line between two incorrect answers to make a correct answer was called "the rule of too much and not enough;" "the method of double false positions;" "the method of scales;" or "Regula Falsi." It made appearances around the world in 9th century Arabic, 11th century European, 12th century Indian, and 13th century African mathematical texts.

Cardano documented the modern idea of iterating the method to increase precision arbitrarily. He used it to solve cubics in his 1545 Ars Magna, one hundred years before Newton was born.

Wiki Javascript at dabbler.org

I have spent a few days teaching kids (a handful of 5th-8th graders) to program in Javascript. Teaching is hard. My conclusions:

• Kids like graphics. Drawing simple paths in SVG is a big hit.
• You need to take a little time to learn basic HTML before Javascript.
• The most frustrating thing for kids is getting their junkware-infested laptops to behave.
• Getting set up with a plaintext editor to write code is a steep climb.

I am rethinking my little curriculum. We need a more gradual path that steps through very simple basics before jumping into more exciting things.

To let the kids program directly online I have posted a collaborative learning-to-program site at dabbler.org that is the simplest possible solution I could think of.

It is wiki in spirit: it is a self-editable website that hosts a syntax coloring programming editor and a bunch of Javascript examples. It is a single shared collaborative space, and it has no access controls to jump through. The kids had a terrific time sharing code with each other and stealing each others' ideas.

Try it if you like. Etiquette and explanation here.

What SAT Stands For

Today was an MCAS day for my kids (Massachusetts's standardized testing at school). A little discussion of such tests lead to one of the conversations that my kids hate to have with me:

Anthony: "What does SAT stand for?"

Me: "SAT Aptitude Test."

Anthony: "Hm, but then what does SAT stand for?"

Me: "SAT Aptitude Test.... S.A.T. S - SAT, A - Aptitude, T - Test."

Anthony: "But why SAT?"

Me: "It tests your aptitude for taking the SAT."

Anthony: "I'm just going to look it up on the Internet."

(By the way, Anthony, it's true. Here it is on the Internet, right here.)

Computer Club

I have started teaching a computer club for middle-schoolers as a test run. Five kids, grades 5-8, all with some experience programming in Lego or Scratch or something else, now learning Javascript. I want to teach them jQuery and graphics, and it is going to be pretty challenging stuff.

Thanks to the ideas from readers of this blog, I am collecting together materials for them that might turn into a book someday. Here it is: Learning to Program in Javascript.

The guinea pigs this time around are all boys. The next time around I will teach Piper and her group of girl friends.

Tutorial: Cannon Game

The canonical cannon game in 80 lines of javascript: cannon-game.html (view source). Move the mouse to aim, and click to fire the cannonball. If you hit the target, it gets moved and you can test your artillery skills again.

The code uses a bit of trigonometry to aim the cannon and a bit of physics to provide gravity. It introduces the idea of using timers for animation and hit-testing for collisions. The gameplay is governed by a three-state state machine with an explicit state variable.

I am still looking for more ideas. Let me know if you think of any good beginner-programmer exercises that might be able to distilled down to about 80 lines of HTML.

Tutorial: Pascal's Triangle

Arrays can be mysterious if you have never used them before. Here is a simple introduction: pascals-triangle.html (view source).

Click on the button to compute and display the next row of Pascal's triangle. Useful for figuring out how many ways to you can divide up kids into teams or for expanding powers of a binomial.

Tutorial: Custom Poem

A good candidate "first program."

The kids love custom-poem.html (view source), which uses document.write to produce a one-of-a-kind custom poem just for you. Refresh to get a new poem.

The bits of wisdom are generated madlibs-style, by inserting a random choice out of of a list of words for each of several spots. A simple idea, but the resulting poems are incredibly entertaining to the 3rd-6th grader set.

I chatted with one of the kids who will be in my trial "programming class," and I was floored to hear this sixth-grader say - without me mentioning jQuery at all - that he "wants to learn jQuery." When I pointed him to Douglas Crockford's talks about the good parts of Javascript, he said, "oh yeah, I've watched that."

So we will definitely follow up with the more-advanced (but conceptually the same) dynamic-poem.html (view source) that uses jQuery instead of document.write. That gives the poem the ability to change itself over time.

Tutorial: Concentration

Another 80-line javascript tutorial: concentration.html (view source) lets you test your memory by trying to find pairs of symbols. When you miss a pair, it flips them back to black after a second. How well can you do?

The program is an example of a very simple state machine with three states: none chosen, a first item is chosen, and a second item is chosen.

For symbols the game uses a bunch of cute and cryptic Unicode glyphs. This works fine on Windows with its Unicode Times New Roman font. Let me know if this is problematic on other platforms.

Tutorial: Histogram

Another javascript tutorial: histogram.html (view source) is a program to let you play with the probability distribution of rolling five dice. Its code is a brief demonstration of how to call Math.random() and how to organize basic coordinate geometry on the screen.

Tutorial: Maze Maker

The tutorial maze-maker.html (view source) is an introduction to functions.

It breaks down the work for drawing a random maze into five functions:

• fillsquares sets up a global array with a grid of SVG squares.
• setcolor sets the color of a single square at position (x, y).
• getcolor returns the color of a single square at position (x, y).
• shuffled returns a shuffled copy of an array.
• makemaze draws a random maze in the grid using recursion.

The program is begging to be extended by adding a maze solver.

Maze-making and maze-solving is a good excuse for explaining recursion. Any ideas for a gentler (but interesting) introduction to functions?

Tutorial: Tic Tac Toe

Continuing with the javascript tutorials - tic-tac-toe.html (view source) is an example of a bare-bones board game AI.

It uses recursion to fully explore the tic-tac-toe tree and play a perfect game against you. The code is short, but I am concerned it is probably too difficult for kids to understand. The other problem is that (at least on my laptop) IE is too slow to run the AI on move #1 without a "script appears hung" warning.

Nevertheless, "how to program Tic-Tac-Toe" is an extremely common request from the kids, so it goes into the pile of examples.

Let me know if you come up with a way of simplifying the code.

Tutorial: Mastermind

Terran implemented a nice 80-line Mastermind implementation in javascript here.

It is a pretty interesting example, and I like it a lot. In an attempt to simplify it, I made a jquery version of it here: mastermind.html (view source). The jquery version has a slightly different flavor - less string-hacking and more conceptual stuff.

Unfortunately, I do not think the jquery conversion makes the code easier to understand for a beginner. It uses too many idioms and so it is probably harder.

But maybe it is useful as an advanced example some jquery and javascript tricks. What do you think? Is there a simpler way?

Tutorial: Polygon Drawing

Continuing the Javascript tutorial series, based on MWinser's observation that 'drawing simple graphs' was a launching off point for him.

Here is a simpler variant: polygon-drawing.html is a 50-line program (view source) that lets you experiment with drawing polygons on the screen. The user can click or enter SVG path syntax directly.

It is an introduction to using mouse events with jQuery, SVG paths, and Raphael.

Tutorial: Caesar Cipher

Another javascript tutorial for middle-schoolers, based on Shakeel's idea. The short file caesar-cipher.html implements a simple Caesar Cipher in javascript, rotating letters of cleartext into ciphertext by shifting them by a fixed number.

The idea of this tutorial is to be a gentle introduction to event-based programming. The encryption code runs every time a keyup event is received on any of the input boxes. (view source)

I decided to use indexOf/charAt instead of charCodeAt/fromCharCode do do the conversion between letters and numbers, because there are fewer edge cases in the code, and it means there's one fewer concept to worry about.

Tutorial: Guess My Number

Continuing the Javascript tutorial series. The guess-my-number.html program is truly a straightforward example of 1978 programming style, with an interactive prompt that blocks the program flow to have the user guess a secret number. (view source)

Not very modern, but a classic first program. Javascript certainly permits this style.

Any other ideas? What other "good first programs" are there?

I feel like I'm looking for some intersection between "what is understandable" to a sixth grader and "what is cool" to the same set.

Tutorial: Ten Followers

OK, based on comments from Cezar and MichaelW and DavidMay and my kids at home, here is another idea for a javascript tutorial for middle-school kids, with a bit more cowbell.

The program ten-followers.html is another 60-line program that does a simple animation on the screen following the mouse. (view-source)

It uses the excellent Raphael library to simplify use of SVG.

$('body').mousemove(function(event) {
  for (var j = 0; j < circles.length; ++j) {
    var c = circles[j];
    var d = distance(c.attr('cx'), c.attr('cy'),
                     event.pageX, event.pageY);
    c.animate({cx: event.pageX, cy: event.pageY}, d * j * 2);
  }
});

Tutorial: Fifteen Puzzle

I am trying to come up with elementary yet modern javascript examples for teaching middle-schoolers. Here is one idea:

The 68-line html file fifteen-puzzle.html contains 12 lines of javascript to implement the classic puzzle. By looking at and editing the source code I am hoping kids can learn several things all at once:

• The nested structure of HTML tags, and tables.
• CSS and CSS selectors.
• Jquery selectors and jquery event handlers.
• Javascript itself.

Also, hopefully it's enough of a program that it is actually fun to fiddle with. The program isn't really done - you'd want to add a "you win!" feature and other things. Or make a 3x3 version or whatever you like.

Too steep for first exposure to programming? My idea here is "plumbing first." When I learned to program on the Atari 800, I learned all about joystick movement and flashing colors before I learned about nested loops.

Ideas for any simpler examples to start with first?

Handheld Glasses-Free 3D

Alan Kay, famously:

People who are really serious about software should make their own hardware.

Yesterday Nintendo announced a clever new version of the DS, rumored to use Sharp 3d Parallax LCD display technology for glasses-free 3D. This type of 3D is only effective if you are looking at the screen from a particular spot. Just perfect for the handheld DS, isn't it.

The neat thing about Sharp's display is that it can flip from 3d mode to 2d mode by electronically removing the parallax screen layer. So users don't have to fight with the fiddly 3d display when they're just reading text on the device: software can switch on 3d mode when it's appropriate. The innovation comes from Sharp's European lab in Oxford, which published the work in this 1999 paper, this 2000 paper, and this 2003 whitepaper.

Sharp tried to sell their own laptop with their 3d display in 2003. It was a commercial flop. For software Sharp bundled the snoozer "Sharp Smart Stereo Photo Editor," and a third-party "TriDef Movie Player."

This suggests an ancillary principle to Kay's law:

People who are really serious about hardware should not make their own software.

Sharp's display will be awesome with Mario. Go Nintendo.

About David Bau - List of All Articles