Class 55: Graphs, Concluded

Held Wednesday, December 6, 2000

Summary

Today we conclude our consideration of graphs.

Notes

• Updated grading scheme
  • Exams 60%
  • Homework (A's for all) 30%
  • Class participation (grade each other) 20%
• How should you grade each other on class particiaption?
  • I want each of you to grade all of the rest.
  • For each person, give a grade, a short explanation, and a note as to something you think that person can improve in their participation.
• Are you planning to take the final?
  • If so, do you prefer in-class or take-home?
  • Recent evidence suggests that I can write reasonable-length in-class exams.
• I'm dealing with sick kids and wife, so I'm far behind on everything (and it looks like I'll continue to be so over the next week).

Overview

Shortest Path, Revisited

• Review algorithm
• How do you get the shortest path out of this algorithm?

Travelling Salescritter Problem

• Tour through all nodes
• Try each of our algorithm design techniques

Graphs as ADTs

• Operations?

Implementing Graphs

• With nodes and links
• As a list of edges
• As an adjacency matrix
• ...