CS 108 (Life in the Age of Networks),
Fall 2013, Carleton College

Basic Information

• Instructor: David Liben-Nowell
• Lecture: 2/3c, Olin 141.
• Office Hours: see my homepage. Always feel free to email for an appointment if the scheduled times aren't good for you.

• This webpage was originally stored in Moodle, which does not have an easy capacity to publish a version of an old webpage for a course. Major thanks to Dave Musicant, whose Moodle-scraping tool I used to generated this page, which is a rough approximation of the original.

Course Materials:

Week 1:

Tuesday:  intro to networks; logistics.

1. Reading:  EK Chapter 1, §2.1; §3.1.
2. Complete ps01 before class on Thursday.

Thursday:  basic graph definitions, triangles and homophily, your movie data.

1. Reading: EK §2.1, §2.4, and §4.1–4.2.
2. Complete ps02 before class on Tuesday.

Week 2:

Tuesday:  definition review; ps02 debrief; paths, connectivity, and a pop quiz.

1. Reading:  Leonhard Euler, Solutio Problematis ad Geometriam Situs Pertinentis, 1736. (Or the English translation below.)
2. Complete ps03 before class on Thursday.

Thursday:  Eulerian paths and the history of graph theory; Greg Marfleet on networks of states.

1. Reading:  EK, §5.1–5.4; Wikipedia entry on the seven bridges of Königsberg.
2. Complete ps04 before class on Tuesday.

Week 3:

Tuesday:  Eulerian paths wrapup; structural balance; storing and searching graphs.

1. Reading:  EK §2.3; notes on graph representation and search.
2. More reading/reference:  Greg Marfleet's Prezi from his class visit is available 
3. Complete ps05 before class on Thursday.

Thursday:  Nathan Grawe on network externalities and cascades; diffusion of innovation; graph representations; BFS.

1. Reading:  EK §17.0–17.3.
2. Complete ps06 before class on Tuesday.

Week 4:

Tuesday:  lingering questions [exam coverage ends here]; directed graphs and connectivity.

1. Reading:  Vannevar Bush, As We May Think, Atlantic Monthly, July 1945.
2. Complete ps07 for Tuesday.

Thursday:  Prelim #1

Week 5:

Tuesday:  directed graphs; the web as a graph; the structure of the web.
You can feel good about your guessing ability here and watch a giant component forming here.

1. Reading: EK Chapter 13 and §18.1–18.2.
2. Complete ps08 before class on Thursday.

Thursday:  structure of the web, midterm course evals, how the internet works.

1. Reading:  EK §18.3–18.6; Gina Kolata, The Myth, The Math, the Sex, The New York Times, 12 August 2007.
2. Complete ps09 before class on Tuesday.

Week 6:

Tuesday:  sexual contact networks; degree distributions; the "wisdom" of crowds.

1. Reading:  Review EK Chapter 18.
2. Completely optional reading: the British study (Johnson et al, 2001) and the Swedish study (Liljeros, 2001) of sexual contacts.  See also NATSAL 2010.
3. Complete ps10 before class on Thursday.

Thursday:  power laws, preferential attachment, and the wisdom of crowds.

1. Reading:  EK §16.1, §16.2, §16.6, §16.7, §22.0, §22.1, §22.4.
2. More reading:  Salganik/Dodds/Watts, "Experimental Study of Inequality and Unpredictability in an Artificial Culture Market", Science, 2006.
3. Complete ps11 before class on Tuesday.

code.org video

Week 7:

Tuesday:  the "wisdom" of crowds.

1. Reading:  notes on Dijkstra's algorithm (below); start EK Chapter 20.
2. Complete ps12 before class on Thursday.
3. The project proposal (announcement below) is due via email to DLN (plain text or PDF only) before class next Tuesday (11/5).  

Thursday:  weighted graphs, Dijkstra's algorithm, and the small-world phenomenon.

1. Reading:  EK Chapter 20.
2. Reminder:  project proposals are due Tuesday.
3. Reminder #2:  the second exam is scheduled for next Thursday.

Week 8:

Tuesday:  the Beatles; review of the second half of the course, Minneapolis mayoral voting systems; and the small-world phenomenon.

1. Prelim #2 is on Thursday.
2. Reading:  nothing new.
3. Complete ps13 before class next Tuesday.
4. Think about your projects!

Thursday:  Prelim #2

Week 9:

Tuesday:  small worlds wrapup; power in networks; random walks.

1. Reading:  EK §3.2–3.5, §14.1–14.15; random walks handout below.
2. Reminder:  Our Thursday meeting will be start in Olin 149 for a joint session with Lauren Feiler's ECON 265.
3. Our final exam will be in our regular classroom on Saturday, 11/23, 3:30–6:00p.

Thursday:  joint meeting with ECON 265 (network exchange); random walks.

1. Reading:  EK §12.1–12.3; EK §14.1–14.5.
2. Reminder:  projects are due on Tuesday!  No-penalty extension until 5:00p Wednesday.

Week 10:

Tuesday:  random walk/PageRank wrapup; course evals/what's CS; physics / network routing; ask me anything.