Dots, Lines, and Coin Flips—Spring 2007

May 14, 2007

Review sessions, office hours

There will be two review sessions, Tuesday at 1:30 p.m. and Wednesday at 4:30 p.m. Come to our usual classroom, King 237; if that's busy, we'll find another room.

Office hours will be Tuesday, 10–12, and Wednesday, 1–3.

Review answers posted

Go over to the solutions page for answers to the final exam review sheet.

April 15, 2007

Solutions and answers posted

Go over to the solutions page for upated homework solutions and for the answers to the Exam 2 review sheet.

March 16, 2007

Assignment 6

Click on the link to the left for Assignment 6, which is due on MONDAY, March 19.

March 13, 2007

A skeptical view

March 8, 2007

Review Sheet

March 2, 2007

Looking for patterns in call graphs

Brian Hayes considers the types of information that might be found in telephone call graphs, or other social networks—and why governments might be interested.

February 27, 2007

Handouts, Homework Solutions

Solutions to Assignments 2 and 3 are now posted on the solutions page. (See my recent e-mail for the username and password.)

Here's the in-class worksheet on graph theory, IV (Euler's formula), in case you missed it.

Many links following up on lectures

How hard are graph problems?

• The Clay Institute's page on the Millenium problems, and P vs. NP in particular.
• A deadpan page listing many papers whose authors believe, incorrectly, that they have answered the question. (I love that there's such as even split as to what the answer is supposed to be!)
• Determining whether two graphs are isomorphic is suspected be harder than problems in P, but easier than the hardest problems in NP. If this were proved, it would demonstrate that P is not equal to NP.
• Determining whether a graph has a Hamiltonian cycle is known to be one of the hardest problems in NP. Hence, if someone found an efficient algorithm to do so, it would show that every problem in NP has a solution.

Eulerian circuits and trails

• Snce this is the tercentennial of Euler's birth, there are many pages celebrating his life and work.
• Bridges of Konigsberg: Wikipedia gives diagrams and variations (which are good practice problems!), along with a little history. Here's Euler's own account, in Latin; scroll down to the second page to see the original diagrams.
• Doug Ensley has an applet for practicing finding Eulerian circuits and trails.

Hamiltonian cycles

• The Puzzle Museum has all sorts of fascinating objects on display, including Hamilton's own version of the Icosian Game.
• Doug Ensley has applets to let you practice determining whether a graph has a Hamiltonian path or cycle, too.

Euler's formula

• Here are 19 proofs of Euler's Formula—the one we'll do in class is number 4. (Note: this page also has a lovely discussion of how to get a planar graph from a polyhedron.)
• Euler himself did not give a complete proof of Euler's formula. This article discusses the history—along the way, it also gives nice illustrations of the connection between polyhedra and planar graphs.
• And yes, there are an awful lot of things named after Euler.

A planarity game

February 23, 2007

Bacterial communication

Biologists are trying to understand how bacteria assemble themselves into communities; the hope is that new antibiotics might be developed that work by stopping the necessary communication.

(If you're not worried about antibiotic resistance, you probobably should be. It's the real reason that we need new antibiotics, preferably ones with radically different mechanisms.)

February 19, 2007

A new political metric?

techpresident.com is tracking how many MySpace friends each of the major presidential candidates has.

February 15, 2007

Assignment 2 extension

Because of the snow day, the due date for Assignment 2 has been delayed to Monday, February 19.

February 14, 2007

Too much information

One night at Two Boots pizza, I meet some tourists visiting from Kansas City: Kent Gasaway, his daughter Hannah, and two of her friends. The girls are 15. They have identical shiny hair and Ugg boots, and they answer my questions in a tangle of upspeak. Everyone has a Facebook, they tell me. Everyone used to have a Xanga ("So seventh grade!"). They got computers in third grade. Yes, they post party pictures. Yes, they use away messages. When I ask them why they'd like to appear on a reality show, they explain, "It's the fame and the—well, not the fame, just the whole, `Oh, my God, weren't you on TV'"?

After a few minutes of this, I turn to Gasaway and ask if he has a Web page. He seems baffled by the question. "I don't know why I would," he says, speaking slowly. "I like my privacy." He's never seen Hannahs Facebook profile. "I haven't gone on it. I dont know how to get into it!" I ask him if he takes pictures when he attends parties, and he looks at me like I have three heads. There are a lot of weirdos out there, he emphasizes. There are a lot of strangers out there.

A New York Magazine article on the generation gap in personal revelation online.

Practice with graphs

In class, we covered Working with Graphs I (the Handshake Lemma) and Working with Graphs II (isomorphism).

You might also find some applets written by Doug Ensley useful; these are little interactive web pages on isomorphism and planarity.

February 5, 2007

Welcome to Dots, Lines, and Coin Flips!

We will meet on Mondays, Wednesdays, and Fridays, from 1:30 to 2:20 p.m., in King 237.

See the syllabus for more information.

This website will run a bit like a blog. Important dates will be listed in the column to the left, along with links to assignments (and solutions, when relevant). Announcements and interesting links will appear in the main body, right here.

If you have any questions, or if there's anything broken on this page, please let me know.