You may use your textbook, a computer, your brain, and, if available, divine guidance. Don't discuss this test with anyone other than Jeff Ondich. Do discuss it with him, if you wish.

1. (15 points) For each of the following scenarios, tell me what data structure I should use, and defend your choice. If implementation details matter (such as whether you'll use an array or a linked structure), include them in your discussion.
   1. I want to have a database into which I can quickly insert items, from which I can quickly delete items, and which I can access efficiently in sorted order. I must also be able to search for an item in this database, and it is essential that my worst-case search time be fast (linear search is not acceptable).

   2. I have to write a program this afternoon. The program needs to maintain a database, allowing insertions, deletions, and searches. The number of items will never be larger than 1000. The program is not computationally intensive, and it's going to be run exactly once. I want to be home in time to make dinner.

   3. I don't want to waste any memory. I want to maintain a database of items that will never change. I will be searching for items in the database often.

2. (16 points) Double-ended priority queues. A double-ended priority queue (DPQ) is a list of items with priorities, from which you can delete either the item with the highest priority or the item with the lowest priority. A good implementation of a DPQ will make the insertion operation and both deletion operations efficient.
   1. Describe in reasonable detail an application of a DPQ. I'm looking for applications that are plausible, and for which a DPQ is a natural way to organize the data.

   2. Read Section 9.2 in Horowitz, Sahni, and Anderson-Freed.

   3. If you start with an empty deap, and then perform the following operations in the given order, what will your deap look like? Insert 10, Insert 20, Insert 15, Insert 5, Insert 12, Insert 17, Delete Max, Delete Min, Insert 16, Insert 11, Insert 8, Insert 14, Delete Max, Insert 13

3. (8 points) Ada, Charles, and Don are planning to implement a hash table that will have 4096 slots. They have agreed to resolve collisions with chaining. The items the hash table will contain will be English words. They are arguing over what hash function to use.

   Ada advocates adding the ASCII representation of the letters in the word together (e.g. ada-> 97 + 100 + 97), squaring the result, and using the middle 10 bits of the 32-bit square as the hash value of the word.

   Like Ada, Charles wants to first add the letters up, but then he wants to take the sum S, and use (S^2 + 3*S + 2) mod 4096 as the hash value.

   Don wants to use a 64x64 2-dimensional array of slots, and take the ASCII values of the first two letters of the word, mod 64, as the indices of the slot into which the word will go.

   Criticize (positively or negatively) each of these proposals.

4. (4 points) The Macintoshes in CMC 301 have been named after McDonald's "food" items since we moved into the building. We would like to rename them, and we need ideas of categories from which we could draw about twenty 8-or-fewer-character names. We'd like something that is neither boring nor offensive. Make a suggestion.

5. (6 points) I have a graph G with weighted edges stored using an edge list. G has seven nodes numbered 1-7, and the edges are of the form (a,b;w), which means there is an edge with weight w connecting nodes a and b. Here are the edges:

   	(1,2;1), (2,3;5), (3,4;2), (1,7;3), (3,7;6),
   	(2,6;1), (4,5;2), (6,5;2), (7,6;2), (4,6;3)
   

   Suppose you use Dijkstra's algorithm to compute the shortest paths between node 1 and each of the other nodes. In this algorithm, you maintain a list P of nodes whose distances from and paths to node 1 have been "settled." In what order do the nodes of this graph get added to P? You can also maintain a list of settled edges--that is, edges that constitute the shortest paths from nodes in P to node 1. Which edges get added to this settled list, and in what order?