`|= `@=

Applied Algorithms Anna Karlin, 426C Sieg
CSE 589, Autumn 2000

Homework # 7
Due November 20

1.

Define a local search strategy for an NP-complete problem other than TSP.

2.

Find, by either searching the web, searching the literature, or talking to people a real-life important problem that is solved using simulated annealing. Explain how the simulated annealing is done e.g., what the solution space and neighborhood structure are, what the cooling schedule is, etc.

3.

When you buy a ticket in the State Lottery, you choose six different numbers between 1 and 36. The lottery officials keep a dictionary keyed on the set of six numbers chosen on each ticket. After the officials pick the winning numbers, they access this dictionary to identify the winning ticket or tickets, if any. Since millions of tickets are sold, the officials have decided to keep the dictionary in external storage with a directory in an internal hash table. Their computer consultant has recommended that they use the hash function

$$h(x_1, x_2,\ldots , x_6) = (x_1 + x_2 + \ldots + x_6) mod m$$

where m is the number of external buckets in which the records will be stored. Give a critique of this recommendation, and suggest a better alternative.

4.

How long could it take in the worst case to insert N keys into an initially empty table of size M, using separate chaining with (i) unordered lists and (ii) ordered lists?

5.

How long could it take in the worst case to insert N keys into an initially empty table of size M, using linear probing? How about in the average case?

6.

Extra Credit Suppose you create a Bloom filter using one random hash function. Suppose that the table has size M and that N keys have been inserted. (The table is initialized so that B(i) = 0 for all $0\le i < M$, and then, for each key, B(h(K)) is set to 1.) What is the probability that on an ``Exists'' query to a particular key K<sub>1</sub> which is in the set, the answer returned is false? What is the probability that on an ``Exists'' query to a particular key K₂ which is not in the set, the answer returned is false?