Computer Science 501
Data Structures and Algorithm Analysis

Fall 2015, The College of Saint Rose

Home     Syllabus     Schedule     Style Guide

Agenda

• Announcements
  • Lab 11: More Trees, Graphs, and Dijkstra's Road Trip [HTML] [PDF] continues
    • no late submissions on lecture and lab questions so we can go over them next week
    • submissions for the programming portion will be accepted through Monday, December 14 without penalty
  • Next week: some review, course evals, "bonus" topics if time
• Binary Search Trees
• Tree Sort
• Comparison of Advanced Sorts
• BST implementations
• Balanced Search Trees
  • AVL Trees
• Maps and Hashing
  • Map structures
  • Hashing
    • hash codes
    • handling collisions

Readings and References

• Bailey Ch. 14, 15

Terminology

• binary search tree
• balanced tree/balance condition
• red-black trees
• AVL trees/AVL condition/single rotation/double rotation
• Splay trees
• map/dictionary
• perfect hashing function
• hash function
• home address
• hash collision
• open addressing/closed hashing
• external chaining/open hashing/separate chaining
• rehashing
• linear probing
• clustering, primary and secondary
• quadratic rehashing
• double hashing
• load factor

Examples

• HashCodes