Homework #3 –
I am sorry about the delay in posting this. As a result, I have made it shorter than I had planned.
1. Read about hashing at
pages 163-164 of our text
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/hash_tables.html - on hashing with definitions and an animation:
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/hash_func.html - on hash functions:
http://en.wikipedia.org/wiki/Hash_function - from wikipedia
2. Run the animation at
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/hash_tables.html
3. Do the following problem
A parking lot has 31 visitor spaces, numbered from 0 to 30. Visitors are assigned parking spaces using the hashing function h(k) = k mod 31, where k is the number formed from the first three digits on a visitor’s license plate. Which spaces are assigned by the hashing function to cars that have these first three digits on their license plates?
317,918,007,100,111,310
4. Books are identified by an International Standard Book Number (ISBN), a 10-digit code x1x2...x10, assigned by the publisher. These 10 digits consist of block identifying the language, the publisher, the number assigned to the book by its publishing company, and finally, a 1-digit check digit that is either a digit or the letter X (used to represent 10). This check digit is selected so that the sum of the product of each of the 10 digits by its position is congruent to 0 (mod 11) and is used to detect errors in individual digits and transposition of digits. The ISBN of Elementary Number Theory and Its Applications, 3rd edition is 0-201-57q89-1, where Q is a digit. Find the value of Q. the 10 digits Do problem 56 on page 168 of our text. Be sure to read the paragraph following problem 54 which explains how to do it.
5. Do the following problem:
The police have three suspects for the murder of Mr. Cooper: Mr. Smith, Mr. Jones, and Mr. Williams. Smith, Jones and Williams each declare that they did not kill Cooper. Smith also states that Cooper was a friend of Jones and that Williams disliked him. Jones also states that he did not know Cooper and that he was out of town the day Cooper was killed. Williams also states that he saw both Smith and Jones with Cooper the day of the killing and that either Smith or Jones must have killed him. Can you determine who the murderer was if
a) one of the three men is guilty, the two innocent men are telling the truth, but the statements of the guilty man may or may not be true?
b) innocent men do not lie?