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
Answers 7, 19, 7, 7, 18, 0
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.
Answer: Q = 8
1*0 + 2*2 + 3*0+ 4*1 + 5*5 + 6*7 + 7*Q + 8*8
+ 9*9 + 10*1 = 230+7Q
Q can’’t be 0
because 230 mod 11 = 10
Q can’t be 1 because 230 + 7 = 237 and 237 mod 11 = 6
Q can’t be 2 because 230 + 14 = 244
and 244 mod 11 = 2
...
Q is 8 becausse 230 + 56 = 286 and
286 mod 11 = 0
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?
Answer: Here is a
way to solve the problem
a)
we look at the three possibilities of who the innocent men
might be.
·
If Smith and Jones are
innocent (and therefore telling the truth), we get an immediate contradiction,
since Smith said that Jones was a friend of Cooper, but Jones said that he did
not even know Cooper.
·
If Jones and Williams
are the innocent truth-tellers, then we again get a contradiction, since Jones
says that he did not know Cooper and was out of town, but Williams says he saw
Jones with Cooper (presumably in town, and presumably if he was with him, then
he knew him).
·
Therefore, it must be
the case that Smith and Williams are telling the truth. Their statements do not contradict each
other.
·
Based on Williams’
statement, we know that Jones is lying, since he said that he did not know
Cooper when in fact, he was with him.
·
Therefore Jones is the
murderer.
b)
This is just like part
(a), except that we are not told ahead of time that one of the men is guilty.
·
Can none of them be
guilty?
·
If so, then they are all
telling the truth, but this is impossible, because, as we saw, some of the
statements are contradictory.
·
Can more than one of
them be guilty?
·
If, for example, they
are all guilty, their their statements give us no information.
·
So that is certainly
possible.