Computer Science 501
Data Structures and Algorithm Analysis

Fall 2014, The College of Saint Rose

Home     Syllabus     Schedule     Style Guide

Agenda

• Announcements
  • we'll meet one last time next Tuesday for our final exam
• Maps and Hashing
  • Map structures
  • Hashing
    • hash codes
    • handling collisions
• Course evaluations and break
• Lab 11: Dijkstra's Road Trip [HTML] [PDF] non-programming recap
• Lab 11: Dijkstra's Road Trip [HTML] [PDF] programming Q&A
  • this part will be accepted without penalty through Sunday
• Final exam discussion and Q&A

Lecture 13 Assignment

Due at the start of class, Tuesday, December 9.

The questions below are not for submission for credit, but are good to look at before the exam.

• Bailey Problem 15.2, p. 399.
• Bailey Problem 15.6, p. 399.
• Bailey Problem 15.8, p. 399.
• Bailey Problem 15.12, p. 400.
• Bailey Problem 15.16, p. 400.

Terminology

• 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