《作业问题3》由会员分享，可在线阅读，更多相关《作业问题3（3页珍藏版）》请在金锄头文库上搜索。
1、Introduction to Algorithms October 3, 2005 Massachusetts Institute of Technology 6.046J/18.410J Professors Erik D. Demaine and Charles E. Leiserson Handout 9 Problem Set 3 MIT students: This problem set is due in recitation on Friday, October 7, 2005. The homework lab for this problem set will be he
2、ld 79 P.M. on Wednesday, October 5, 2005. SMA students: Reading: Sections 11.111.3 and Section 11.5. Both exercises and problems should be solved, but only the problems should be turned in. Exercises are intended to help you master the course material. Even though you should not turn in the exercise
3、 solutions, you are responsible for material covered in the exercises. Mark the top of each sheet with your name, the course number, the problem number, your recitation section, the date and the names of any students with whom you collaborated. You will often be called upon to “give an algorithm” to
4、 solve a certain problem. Your writeup should take the form of a short essay. A topic paragraph should summarize the problem you are solving and what your results are. The body of the essay should provide the following: 1. A description of the algorithm in English and, if helpful, pseudocode. 2. At
5、least one worked example or diagram to show more precisely how your algorithm works. 3. A proof (or indication) of the correctness of the algorithm. 4. An analysis of the running time of the algorithm. Remember, your goal is to communicate. Full credit will be given only to correct solutions which a
6、re described clearly. Convoluted and obtuse descriptions will receive low marks. Exercise 31. Do Exercise 11.11 on page 222 in CLRS. Exercise 32. Do Exercise 11.23 on page 229 in CLRS. Exercise 33. Do Exercise 11.33 on page 236 in CLRS. Exercise 34. Do Problem 112 on page 250 in CLRS. 2 Handout 9: P
7、roblem Set 3 Problem 31. Pattern Matching Principal Skinner has a problem: he is absolutely sure that Bart Simpson has plagiarized some text on a recent book report. One of Barts sentences sounds oddly familiar, but Skinner cant quite fi gure out where it came from. Skinner decides to see if some sm
8、artalec MIT student can help him out. Skinner gives you a DVD containing the full text of the Springfi eld public library. The data is stored in a binary string T1,T2,.,Tn, which we view as an array T1 n, where each Ti is either 0 or 1. Skinner also gives you the quote from Bart Simpsons book report
9、, a shorter binary string P1 m, again where each Pi is either 0 or 1, and where m 0: hp(x) = x (mod p) . Assume that p is chosen uniformly at random among all prime numbers in the range 2,cn4. Fix some i with 1 i n m + 1, and let x = Ti(i + m 1). Show that, for an appropriate choice of c, and if x =
10、 P, then 1 Pr hp(x) = hp(P) . p n Hint: Recall the following two numbertheoretic facts: (1) an integer x has at most lg x prime factors; (2) the Prime Number Theorem: there are (x/lg x) prime numbers in the range 2,x. (c) How long does it take to calculate hp (x), as defi ned in part (b)? Hint: Noti
11、ce that x is an mbit integer, and hence cannot be manipulated in constant time. 3 Handout 9: Problem Set 3 (d) For 1 i n m, show how to calculate hp(A(i + 1) (i + m) in constant time if you already know the value of hp (Ai(i + m 1), as defi ned in part (b)? (e) Using the family of hash functions fro
12、m part (b), devise an algorithm to determine whether P is a substring of T in O(n) expected time. Problem 32. 2Universal Hashing Let H be a class of hash functions in which each h H maps the universe U of keys to 0,1,.,m 1. We say that H is 2universal if, for every fi xed pair x,y of keys where x =
13、y, and for any h 2 chosen uniformly at random from H, the pair h(x),h(y) is equally likely to be any of the m pairs of elements from 0,1,.,m 1. (The probability is taken only over the random choice of the hash function.) (a) Show that, if H is 2universal, then it is universal. (b) Construct a specif
14、i c family H that is universal, but not 2universal, and justify your answer. Write down the family as a table, with one column per key, and one row per function. Try to make m, |H , and U as small as possible. | | Hint: There is an example with m, |H , and U all less than 4. | | (c) Suppose that an
15、adversary knows the hash family H and controls the keys we hash, and the adversary wants to force a collision. In this problem part, suppose that H is universal. The following scenario takes place: we choose a hash function h randomly from H, keeping it secret from the adversary, and then the advers
16、ary chooses a key x and learns the value h(x). Can the adversary now force a collision? In other words, can it fi nd a y = x such that h(x) = h(y) with probability greater than 1/m? If so, write down a particular universal hash family in the same format as in part (b), and describe how an adversary can force a collision in this scenario. If not, prove that the adversary cannot force a collision with
