Computer Science 501
Data Structures and Algorithm Analysis

Fall 2014, The College of Saint Rose

Home     Syllabus     Schedule     Style Guide

Agenda

• Announcements
  • CSC 507 next semester
• Lab 10: Trees [HTML] [PDF] recap
• Lab 11: Dijkstra's Road Trip [HTML] [PDF]
  • the programming assignment portion will be accepted without late penalty through Sunday, December 7, but you are encouraged to finish sooner so you can focus on final exam preparations
  • discussion of an approach to building the graph structure, how the Mapping program works and how to extend it, how to implement Dijkstra's Algorithm
• More graph algorithms
  • transitive closure
  • all-pairs shortest paths
• Binary Search Trees
• Tree Sort
• Comparison of Advanced Sorts
• BST implementations
• Balanced Search Trees
  • AVL Trees

Readings and References

• Bailey Ch. 14, 15

Terminology

• breadth-first order
• depth-first order
• transitive closure
• Warshall's algorithm
• all-pairs minimum distance
• Floyd's algorithm
• binary search tree
• balanced tree/balance condition
• red-black trees
• AVL trees/AVL condition/single rotation/double rotation
• Splay trees

Examples

• MassFloyd