Good Reads

It seems like I read more than the usual share of negative news stories this summer about the dysfunctional state of our politics and our political system. In the midst of much noise and misinformation I found three excellent reads that can be directly tied to topics covered in Excursions. In all three cases the articles were written for an educated but general audience and should be accessible and of interest to most college students.

In the July 26 issue of The New Yorker there was an article by Anthony Gottlieb about the mathematics of elections. The article is actually a book review of the recent book “Numbers Rule: The Vexing Mathematics of Democracy from Plato to the Present,” by George Szpiro. Gottlieb’s review focuses mostly on historical anecdotes about voting methods and elections, and makes for a nice complement to the material in Chapter 1 of Excursions. To read Gottlieb’s article click here.

Szpiro’s book, on the other hand, is organized by individual stories—there is a chapter on Plato, a chapter on Borda, a chapter on Condorcet, etc. I’m only halfway through the book, but it so far it looks like an easy and entertaining read. For the book’s page on Amazon, click here.

In the July-August issue of American Scientist there was an article by Barry Cipra about the mathematics of apportionment. The article covers many of the issues and ideas discussed in Chapter 4 of Excursions. Cipra is an excellent writer and your students should enjoy reading a validation of what they learned in their textbook. To read Cipra’s article, click here.

Finally, the Sept. 19 issue of the New York Times Sunday Book Review has a review by Steven Strogartz of the book “Proofiness: The Dark Arts of Mathematical Deception,” by Charles Seife. To read Strogartz’ review, click here.

To quote directly from the review, “[Seife] examines the many ways that people fudge with numbers, sometimes just to sell more moisturizer but also to ruin our economy, rig our elections, convict the innocent and undercount the needy.” I highly recommend this book as a complement to the material in Chapter 13 of Excursions. Seife is a terrific storyteller, and the stories are both illuminating and scary. (Note: The Kindle edition is already out; the hardcopy edition is being released this week.) For the book’s page on Amazon, click here.

Applets for Excursions

I have received several queries over the summer about the applets for Excursions that stealthily came online sometime last spring, so my first post for the 2010-11 academic year is a plug for the applets. The applets were developed as a resource for instructors as well as a pedagogical tool for students. You can see what’s available (for now) and try out any of the applets here.

These applets are not all cut from the same cloth, and some applets are better than others. Some serve simply as a black box for complicated computations (see for example the Finance Calculator applet or the Data Sets applet); others are true pedagogical tools that allow the student to learn “stuff” as they play.

My favorite applets (partly because my students found them so useful) are the graph theory applets covering the material in Chapters 5-8. For the purposes of illustration, for the rest of this post I will walk through the Traveling Salesman Problem applet for Chapter 6.

If you open the Traveling Salesman Problem applet and select the “Create Graph” tab you get a blank canvas. With the “Add Vertices and Edges” button selected, you can click and drag to create vertices and edges. The vertices are automatically labeled A, B, C, sequentially, and every edge starts with a default weight of 1.

Here I created a complete graph with 5 vertices. This was quick and easy as I don’t much care at this point about the placement and labels of the vertices— this is just the skeleton for my example.

At this point you can change the labels of the vertices at will. Say you want to change the name of vertex A to Atlanta—double-click on vertex A and you get this window:

Enter the new name for the vertex and confirm. This is what the graph looks like now:

It’s now time to change the weights of the edges, and this takes a little practice. The applet allows for non-negative integer weights only (for decimal weights just scale all the weights by a power of 10 so that you end up with integer weights). Selecting the “Change Weights” button lets you run a fast counter (click and hold to the right of center to count up, to the left of center to count down). Note: The counter is so fast that it is sometimes hard to stop exactly where you want. By deselecting the “Change Weights” button you can slow it down (each click then changes the weight by 1). In any case, it takes a little practice, but once you get the hang of it you can create reasonably complex weighted graphs quickly.

This is my weighted graph (I am using the numbers straight out of Example 6.4, p. 210 in the 7^th edition, and I changed Atlanta back to A to keep things straight). It took me about three minutes to enter all the weights.

You can see that the graph is a bit crowded (the applet gives you no control as to the placement of the weight along each edge), but you can get around this by moving the vertices. I stretched out my graph (select the “Move Vertices” button first) and got a much cleaner graph.

Now that you have a nice looking graph to work with, you can demonstrate the inner workings of the various algorithms for tackling TSP’s. Let’s start with the Nearest-Neighbor algorithm.

Select the “Nearest-Neighbor” tab and click on the desired starting vertex. I’m starting the tour at vertex A.

From A, I correctly clicked on its nearest-neighbor C and from C went to E. So far, so good. The partial tour is shown on the graph (in red) and also as a list of vertices at the bottom of the screen (with a partial tally of the total weight).

Now suppose that I incorrectly try to go from vertex E to its nearest-neighbor A. I get the following error message

Follow with the correct move to D and then to B and we are done!

The Cheapest-Link algorithm works in a similar fashion, but instead of selecting vertices you need to select edges. To select an edge you click somewhere along the edge (you may have to try a couple of different spots to get it to work). Once again, the applet let the user know when they close a circuit too soon

or when they create three edges coming out of a vertex

When the cheapest-link tour is completed the applet shows its appreciation:

Last but not least, a few words about the implementation of the Brute-Force algorithm. The applet works well for complete graphs of up to 7 vertices—I wouldn’t push it past that. The drop down menu “Select circuit” at the bottom of the window lists all the possible Hamilton circuits for the graph (starting and ending with the very first vertex you created when you created the graph). You can choose any circuit in the list and the applet will show the circuit and give its total weight. Here are two randomly chosen circuits from the list of 24.