Homework 09 METU CENG310

Homework 09
METU CENG310 
Data Structures and Algorithms with Python

1 Hash Tables
The ten most common words in English, along with their hash codes according are as in Table 1.
Order Word Hash Code
1 the 114801
2 of 3543
3 to 3707
4 and 96727
5 a 97
6 in 3365
7 is 3370
8 it 3371
9 you 119839
10 that 3558823
Table 1: The ten most common words in English, along with their hash codes.
Task-1: Suppose these strings are inserted into a 14-bucket hash table in the order shown above. Each string’s
bucket is its hash code modulo 14. If collisions occur, each bucket is implemented as a simple unsorted map,
with new items added to the end of the list. Show the contents of all buckets after these strings are inserted.
Give each bucket as a bucket number followed by a list of strings, with the head of the list at the left.
Task-2: Suppose these strings are inserted into a 14-bucket hash table in the order shown. Each string’s initial
bucket is its hash code modulo 14. If collisions occur, use linear probing with a step size of 1. Show the
contents of all buckets after these strings are inserted. Give each bucket as a bucket number followed by the
string in that bucket, if any.
2 Instructions
Pertaining to the answers of this homework, correct typing of superscripts (e.g., n
2
) and subscripts (e.g., n0)
matters. Due to this reason, this homework may be done on paper and returned as a PDF file containing
the answer sheet captures (photos, scanned files). If you would like you can use MS Word or Latex, but your
deliverable has to be a single PDF file. PDF file should be created so that the answers appears in the same
order as the questions shown in the homework assignment document.
A Homework-09 page will be generated soon after the start date of this homework. All deliveries should
be done over ODTUClass. Please also be aware of the late penalties (Please check the Announcements –
Homework and Assignment Policy in ODTUClass if you have not already done so.). Should you have any
questions pertaining to homework tasks, please ask them in advance (not on the due date) for your own
convenience.
1