## Office Hours
## IM Hours
## SolutionsClick here for homework and exam solutions. ## Dates and LinksWednesday, February 7 Friday, February 9 Monday, February 19 Friday, February 23 Friday, March 2 Friday, March 9 Wednesday, March 14 Monday, March 19 Friday, March 23 March 26–30 Wednesday, April 18 Friday, May 11 Tuesday, May 15 Wednesday, May 16 Thursday, May 17 |
## May 14, 2007## Review sessions, office hoursThere 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 postedGo over to the solutions page for answers to the final exam review sheet. ## April 15, 2007## Solutions and answers postedGo over to the solutions page for upated homework solutions and for the answers to the Exam 2 review sheet. ## March 16, 2007## Assignment 6Click on the link to the left for Assignment 6, which is due on MONDAY, March 19. ## March 13, 2007## A skeptical viewHere's an article claiming that the current wave of social netowrking is just another round of hype about a (barely) new technology.## March 8, 2007## Review SheetHere's the Review Sheet for Exam 1.## March 2, 2007## Looking for patterns in call graphsBrian 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 SolutionsSolutions 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 lecturesHow 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 gameAmazingly addictive. (Don't say I didn't warn you.)## February 23, 2007## Bacterial communicationBiologists 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 extensionBecause of the snow day, the due date for Assignment 2 has been delayed to Monday, February 19. ## February 14, 2007## Too much information
A New York Magazine article on the generation gap in personal revelation online. ## Practice with graphsIn 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. |

Page maintained by Elizabeth Wilmer.