Held: Monday, 26 October 2015

Back to Outline 22 - No Class. On to Outline 24 - Graph ADTs.

Summary

We begin our study of graphs.

Related Pages

Overview

• Tries, Revisited.
• Graphs.
• A Graph ADT.
• Graph Traversal.

Administrivia

• Welcome back from break!
• No, I don't have your grading done yet. I'm very sorry. Soon!
• Congrats to NBB!

Upcoming Work

• Read 5.1, 5.5-5.10. (Do not read 5.2-5.4.)

Extra Credit

Academic

• Any visit to the current show in the Faulconer gallery.
• Any of the Grinnell Prize Week Activities this week.
• CS Table Tuesday: Hear about the Grace Hopper Celebration of Women in Computing.
• Grinnell Town Hall Wednesday at noon: Self-Gov.
• Conversation about Study Abroad at AIT in Hungary: Wednesday at 4:15 in 3821.
• Convocation Thursday at 11: Contesting Muhammad: Contermporary Controversies in Historical Perspective
• CS Extras Thursday at 4:15pm in 3821: Algorithms for Assembling the Tree of Life. (Plus grad school at UIowa!)
• What's the Deal with the Digital Liberal Arts? Thursday at 4:15 in the D-Lab. With Autumnal snacks!
• Sexual Misconduct at Grinnell College: Results from the 2013 and 2015 Sexual Conduct Surveys. 1-3 pm, November 8, JRC 101.
• R.L. Stephens II events Thursday and Friday.

Peer Support

• Women's Soccer, Wednesday, 4 p.m. vs. UW-Platteville
• Men's Soccer, Thursday, 4 p.m. vs. Coe
• Women's Soccer, Saturday, 11 a.m. vs. Beloit (Senior day!)
• Men's Soccer, Saturday, 1:30 p.m. vs. Beloit (Senior day!)

Leftover Topics: Tries

• What ADT does the trie implement?
• What are the relative advanges of tries vs. hash tables?

Graphs: Conceptual

• The world is connected.
• You will find it useful to model many kinds of problems in terms of sets of connections.
• We call the things that are connected nodes or vertices.
• We call the things that connect nodes edges.
• Sometimes folks call graphs networks.
• We can ask all sorts of questions about graphs and networks.
  • Can we get from a vertex to another vertex?
  • Can we get from a vertex to every other vertex?
  • Can we get from every vertex to every other vertex?
  • What's the shortest route from one vertex to another vertex?
  • ...
• We can also look at different characteristics
  • Simple vs. Non-Simple
  • Sparse vs. Dense vs. Complete
  • Cyclic vs. Acyclic
  • Connected vs. Non-connected
  • Embedded vs. Topological
  • Labeled vs. Unlabled

Traversing Graphs

• Goal: Visit all the vertices (and, often, edges) in a graph
• Typically keep track of three states for each vertex:
  • undiscovered: we have not looked at the vertex
  • discovered: we've looked at the vertex, but have not dealt with all of its edges
  • processed: we've looked at all of the edges

Graphs: ADT

We'll work together to generate an ADT.