The readings for Monday, October 31 are:
Data Structures and Other Objects Using C++:
If you do not have the primary textbook, you can use the following free alternative texts instead:
Data Structures & Algorithm Analysis
The focus of the reading is hash tables, specifically the open addressing implementation strategy.
Once you have completed the readings, answer the following questions in the
reading08/README.md file in your assignments repository:
Generally, how are collisions handled in a hash table that uses open addressing? In particular, briefly explain how linear probing works when there is a collision.
In the context of hash tables, what is the load factor and how does this statistic impact performance and memory usage?
Starting with an empty hash table using open addressing (and linear
probleing with an interval of 1), and using the hash function h(x) = x %
10, show the result of inserting the following values into the table:
7, 3, 2, 78, 56, 72, 79, 68, 13, 14
| Bucket | Value |
|---|---|
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | |
| 9 |
For a hash table using open addressing, identify the average and worst case time complexities in terms of Big O for the following set operations:
Search
Insert
Remove
If the average and worst case time complexities are different, then explain the reason for the difference.
To submit your solution, you must initiate a Merge Request in your private assignments repository and assign it to the appropriate TA from the Reading 08 - TA assignment list.
To facility the Merge Request workflow, you must do your development in its own branch:
$ cd path/to/repo # Go to your repository $ git checkout master # Make sure we are on master branch first $ git pull # Make sure we have changes from GitLab $ git checkout -b reading08 # Create reading08 branch ... # Do your work $ git commit # Commit your work (can do this multiple times) $ git push -u origin reading08 # Push branch to GitLab