Abstract:

The lecture that I will cover is going to be on Hash Tables. The lecture is designed for an introductory CS course and/or a data structures course. We are in the last 3rd of the semester when this topic is covered. At this point, students are comfortable with programming (in Python). In addition, they have some experience with complexity analysis in the context of the topics we have already covered in the course, including iteration, recursion, various search and sort algorithms, arrays, and lists.

The lecture will discuss what hash tables are, their importance, and examples of their use in real life. We will then talk about what hashing is and how hash tables work. We will briefly discuss collisions, what they are, how to deal with them, and why they are problematic. Lastly, we will introduce dictionaries, the hash table implementation in Python. The lecture will involve multiple active learning exercises and live coding.