Computer Science 501
Data Stuctures and Algorithm Analysis
Fall 2013, The College of Saint Rose
Lecture 12: Graph Algorithms; Search Trees
Date: Wednesday, November 20, 2013
Agenda
- Announcements
- Lab 8: Tree Problems [HTML] [PDF] continues; due 12/4
- Programming Project 3: Dijkstra's Road Trip [HTML] [PDF] continues;
due 12/9
- You will know everything you need for these by the end of
class today
- Lecture 11 assignment recap
- Quick recap of Lab 7: P.S. It's Just A Stack [HTML] [PDF]
- Graph algorithms
- reachability
- transitive closure
- all-pairs shortest paths
- single-source shortest paths
- Binary Search Trees (read about these)
- Tree Sort (read about this)
- Comparison of Advanced Sorts (read about this)
- BST implementations (read about these, but don't worry too much about implementation details)
Lecture 12 Assignment
Due at the start of class, Wednesday, December 4.
Please submit answers to these questions
in Submission
Box under "LA12" by the start of our next
class. We will discuss these questions at the start of class, so no
late submissions are accepted. Please be sure that your name is
clearly indicated in all submissions.
- Using the graph from Bailey Problem 16.7, p. 436, use
Dijkstra's Algorithm to compute the shortest distance from Dover to
Phoenix. Show the map that results from this and the priority queue
as done in the example from the graph notes. (10 points)
- SKIP THIS ONE - it was part of lab 8 (sorry about that!) Bailey Problem 14.2, p. 365. (3 points)
- Bailey Problem 14.14, p. 365. (3 points)
Examples