Computer Science 136 Data Structures and Advanced Programming Williams College Fall 2005

Announcements

• Congratulations to this year's Darwin contest winners:
  1. Zachary for his creature "Dolly"
  2. Rhaad for his creature "DumbBit"
  3. Kyle for his creature "Brainless"

Agenda

• Lab 10 questions
• Dijkstra'a Algorithm
  • The outline from last time:

    T is the empty graph;
    PQ is an empty priority queue;
    All vertices in V are marked unvisited;
    Add s to T; mark s as visited in G;
    Add each edge (s,v) of G to PQ with appropriate value
    while (T.size() < G.size() and PQ not empty)
           do
               nextEdge = PQ.remove();
           until(one vertex of nextEdge is visited and the other is unvisited)
              or until there are no more edges in PQ
    
           // assume nextEdge = (v,u) where v is visited (in T) and u is
              unvisited (not in T)
    
           Add u to T; mark u as visited in G;
           Add (u,v) to T;
           for each unvisited neighbor w of u
              add (u,w) to PQ with appropriate weight
    

  • Application to Massachusetts distances example.
• Maps and Dictionaries
  • Maps
  • Hash Tables

Examples

• Spells