Algorithm Design and Analysis Solution



HW 3 (Given November 3, 2017; Due November 17, 2017)

This HW is worth 50 points

1. Implement a hash table with lists chaining. You are given the number of buckets m and hash function.


h(S) = ( X


S[i]xi mod p) mod m (1)

where S[i] is the ASCII code of the i-th symbol of S, p = 1 000 000 007 and x = 263. Your program should support the following kinds of queries:

add string insert string into the table. If there is already such string in the hash table, then ignore the query.

del string remove string from the table. If there is no such string in the hash table, then ignore the query.

find string output yes or no depending on whether the table contains the string or not.

check i output the content of i-th list in the table. Use spaces to separate the elements of the list. If the i-th list is empty, print a blank line.

When inserting a new string into a hash chain, you must insert in the beginning of the chain.

Input Format: First line contains m the number of buckets. The next line contains the number of queries N. It’s followed by N lines, each of them contains one query in the format described above.

Output Format: For each find and check query, print one result per line, in the same order as these queries are inputted.