Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Tries, Revisited.
• Graphs.
• A Graph ADT.
• Graph Traversal.

Preliminaries

Admin

• 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 for Wednesday. (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
• Halloweenfest on Saturday by the Soccer field, 10:30-4.
• Women's Soccer, Saturday, 11 a.m. vs. Beloit (Senior day!)
• Men's Soccer, Saturday, 1:30 p.m. vs. Beloit (Senior day!)
• Harry Potter and the Methods of Rationality discussion group Saturday at some rational time. Food!

Questions

Leftover Topics: Tries

"If at first you don't succeed, trie, trie again."

What ADT does the trie implement?

• Kinda like a Dictionary; keys have to be strings

What ADT does the hash table implement?

• Dictionary - Something that maps keys to values

Other notes

• Tries are trees (and not just badly spelled trees)
• Kinda like decision trees
• Tries can be used for other applications, such as word completion.

Tries and hash tables seem to have some similar goals. are the relative advantages/disadvantages of tries vs. hash tables?

• Tries can do better than hash tables if you don't know the full key.
• Tries likely require more memory than hash tables
  • Hash tables: Approximately 2#keys(keylength+valuelength+pointerlength)
  • Trie: #nodes * (1 + |alphabet|) * pointerlength + (#keysvaluelength)
  • #nodes <= sum of individual key lengths <= #keyskeylength
  • Probably about 10-20 times as much space; depends on overlap
• Speed
  • Trie keylength insert and find
  • Hash table: keylength steps to hash; at least keylength to see if it matches the value at that cell
  • Complicating factor: Locality

Graphs: Conceptual

What is a graph?

A collection of vertices, V, and a collection of edges between those vertices, E. E is a subset of VxV. (or VxVxN, for weighted graphs)

What do the following terms represent? (It's okay to say that you don't know.)

• Simple vs. Non-Simple ???
  • Simple: No edges from a vertex to itself; at most one edge from one vertex to another.
• Sparse vs. Dense ???
  • Number of edges vs. number of vertices
• Complete ???
  • Every vertex has an edge to every other vertex
• Cyclic vs. Acyclic ???
  • Cyclic: There is a path from one vertex back to itself
• Connected vs. Non-connected ???
  • Connected: Can get from any vertex to any other vertex
• Embedded vs. Topological ???
  • Embedded: Physical locations need to be accounted for
• Labeled vs. Unlabeled ???
  • Do we have a way to refer to the individual vertices
• Directed vs. Undirected
  • Directed: Edges lead from vertex to vertex
  • Undirected: Edges are bidirectional
• Weighted vs. Unweighted
  • Weighted: Edges have an associated (real/integer) value

Graphs: ADT

What are the key operations for a graph?

Traversing Graphs