For this exam, you may use your textbook and a language reference, my sample code, your own programs and notes, and divine guidance should any be available to you. You may not use other books, web pages, or code. If you get stuck, talk to me, but please don't talk to anyone else (not even Jeremy Carr or the lab assistants) about the exam. You may discuss syntax and system problems with Jeremy or the lab assistants, but you must tell them that you are working on an exam.

1. (12 points) For each of the following scenarios, recommend a data structure. Briefly justify your recommendation.
   • You have a database of a few million items, and it's mostly static. That is, you are seldom going to add items to or delete items from the database. Each item in the database has a single search key, and you plan to do lots of searches. Memory is extremely limited.

   • You have a database of a few hundred items, each of which has a single search key. You plan to do lots of adding and deleting, and millions of searches. It is essential that you keep search times as short as possible. You can have as much memory as you want.

   • You are going to do a word-frequency program as in your homework that was due 2/19, and run it on the text version of the English translation of the Koran (1.7MB). Unfortunately, you don't seem to be able to find your old code, and you have to get this program running in 45 minutes or you'll miss your bus home. You can let the program run overnight.

2. (12 points) Suppose you have a file consisting of a list of names and their test scores, like so:

   
   	Norman       92
   	Felicity     84
   	Quentin      9
   	Alice        92
   
   	etc.
   

   You may assume that no two lines have the same name, but that scores may be duplicated.

   • Write a program using the standard template library map template to read this file and print out a list of names and scores in alphabetical order by name.

   • Describe a data structure that will enable you to search the name/score pairs by name in O(log N) time, search the name/score pairs by score in O(log N) time, print the pairs in alphabetical order in O(N) time, and print the pairs in numerical order in O(N) time. YOU NEED NOT IMPLEMENT THIS DATA STRUCTURE.

3. (8 points) Consider the following AVL tree, called T1, whose nodes contain letters of the alphabet:

   
   	Q
   	J U
   	D L S V
   	C H - M - T - X
   	A - E I - - - - - - - - - - - -
   

   (In this representation of a tree, I have written each row of the tree from left to right, with a "-" wherever there is no node. So Q is the root, the children of U are S and V, and V has a right child X but no left child.)

   • Draw the AVL tree T2 that results when you add G to T1.

   • Draw the AVL tree T3 that results when you add Z to T2.

4. (6 points) Start with the tree T1 from the previous problem, but this time treat it as an ordinary binary search tree (not an AVL tree). Show the tree that results when you delete the root from T1 using the algorithm in section 4.3.4 of your textbook.

5. (4 points) What is the largest number of edges in a graph with N nodes, given that at most one edge can connect any pair of nodes, and that no edge can connect a node to itself?

6. (12 points) Consider a graph G with 9 nodes numbered 0 through 8, whose edge set is {(0,8), (0,1), (0,2), (1,3), (2,3), (2,4), (6,8), (5,6), (5,7), (3,7)}.
   • Draw the graph.

   • Using the breadth-first search algorithm I handed out in class, list the nodes in the order in which they will be visited in a search starting at node 0. Draw the resulting spanning tree.

   • Using the depth-first search algorithm I handed out in class, list the nodes in the order in which they will be visited in a search starting at node 0. Draw the resulting spanning tree.

   • Suppose the edge weight on each edge is the sum of the numbers of the nodes it connects. Using Dijkstra's algorithm as described in section 9.3.2 of your textbook, starting with node 0, list the nodes in the order in which they become "known." Draw the shortest paths to 0 spanning tree.

7. (2 points) Please recommend a book for me to read.

8. (6 points) Consider the max heap H1:

   
   	9
   	4 7
   	3 0 6 5
   	2 - - - - - - -
   

   • Draw the heap H2 that results when you add 8 to H1.

   • Draw the heap that results when you remove the largest item from H2.

9. (6 points) What is the worst-case complexity (in big-oh notation) of:
   • adding an item to an N-item max heap?
   • deleting the largest item from an N-item max heap?
   • searching for an item in an N-item max heap?