Week 9 - Hash Tables

Learning objectives

  • Implement a hash table
  • Represent a graph with an adjacency matrix or adjacency list
  • Execute basic search-based algorithms in a graph

Day 1

  • Holiday

Day 2

  • Hash Tables

Day 3

  • Hash Tables - Collision strategies
  • Std Unordered Set/Map

Day 4

  • Graphs & Searches

Topics

Hash Tables

  • Read Ch 24.4-24.7

  • Watch these videos:

Other Hash Table Collision Strategies

  • Linear probing is not the only way to resolve collisions. Watch this video to learn about other strategies. It also covers the standard data types that are built with Hash Tables: std::unordered_map and std::unordered_set:
  • Do the HashTable CPPLab

Graphs & Basic Searches

  • Graphs are the generalized idea of nodes (or vertexes) connected by edges. The linked lists and trees we have learned about are just specific forms of graphs. Watch this video to learn about the general concept of graphs:

  • Read Ch 26.1-26.3

  • Do the Graph WS