CSC301.01 2015F, Class 23: Graphs
=================================

_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 + (#keys*valuelength)
     * #nodes <= sum of individual key lengths <= #keys*keylength
     * 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
-----------------