Week 7. Maps and Hash tables
Projects and Exercises
8.2 Projects and Exercises
8.2.1 Warm-up Exercises
Problem 8.1 (Textbook R-10.3) Which of the hash table collision-handling schemes could tolerate a load factor above 1 and which could not?
Problem 8.2 (Textbook R-10.29 adapted) What abstraction would you use to manage a database of friends’ birthdays in order to support efficient queries such as «find all friends whose birthday is today» and «find the friend who will be the next to celebrate a birthday»?
8.2.2 Compulsory Assignment
In the compulsory exercises, please use diagrams as well as pseudo-code to clarify your design. I have observed that many students have good problem solving skills, but need to improve the presentation of their designs. Therefore, only one compulsory problem is given this week. Please take the time to make a really good, clear, and readable presentation of your solution. Use diagrams as well as pseudo-code, and it is often a good idea to show intermediate steps of development (see Solution ?? for an example).
Problem 8.3 (Textbook C-10.38 adapted) The LinkedHashMap class in the Java API maintains the same data both in a Hash table and in a doubly linked list. Thus it is possible to iterate over the elements in the map, in a predictable order (FIFO - first in is first out), and at the same time, the map operations retain O(1) time. The key that has been in the map the longest is reported first. The order does not change if an existing key gets a new value.
Design the necessary algorithms (pseudo-code) to achieve this performance. Whether you want to mimic the existing Java API is up to you. You need to specify the insert and remove operations, get from the Map API, as well as methods to traverse the list in FIFO order.
8.2.3 Exercises
Problem 8.4 Textbook C-10.35
Problem 8.5 Design a solution for Textbook Problem P-10.56, but do not implement it.
Problem 8.6 Textbook C-10.51