# Dots, Lines, and Coin Flips—Spring 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.

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

#### April 15, 2007

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

#### Assignment 6

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

#### A skeptical view

Here's an article claiming that the current wave of social netowrking is just another round of hype about a (barely) new technology.

#### Review Sheet

Here's the Review Sheet for Exam 1.

#### 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.

#### 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?

Eulerian circuits and trails

Hamiltonian cycles

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

Amazingly addictive. (Don't say I didn't warn you.)

#### 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.)

#### A new political metric?

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

#### Assignment 2 extension

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

#### 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.

#### 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.