Laboratory 10 Solutions
Solutions to programs:
Solution to hash functions (insert and retrieve)
Solution to neighbor_count function
Problem 2: Use radix sort to sort the following list:
Tim Dot Eva Roy Tom Kim Guy Amy Jon Ann Jim Kay Ron Jan
Trace the operation of each pass of radix sort:
First pass:
Eva Tim Tom Kim Jim Jon Ann Ron Jan Dot Roy Guy Amy Kay
Second pass:
Jan Kay Tim Kim Jim Amy Ann Tom Jon Ron Dot Roy Guy Eva
Third pass:
Amy Ann Dot Eva Guy Jan Jim Jon Kay Kim Ron Roy Tim Tom
Problem 3:
Suppose that a hash table has hash_size = 13 with entries
indexed from 0 to 12 and that the following entries are mapped to the table:
10 100 32 45 58 126 3 29 200 400 0
a) Determine the hash addresses and find how many collisions occur
when these keys are reduced by applying the operation %hash_size.
Answer:
Original number: 10 100 32 45 58 126 3 29 200 400 0
Hash location: 10 9 6 6 6 9 3 3 5 10 0
5 Collisions occur.
b) Determine the hash addresses and find how many collisions occur
when these keys are first folded by adding their digits together
(in ordinary decimal representation) and then applying %hash_size.
Answer:
Original number: 10 100 32 45 58 126 3 29 200 400 0
Hash location: 1 1 5 9 0 9 3 11 2 4 0
3 Collisions occur.
Home | | Syllabus | | Assignments | | Lecture Notes