This takehome is open book, open notes, and open computer. Do not consult with people other than yourself and Jeff Ondich.

1. (12 points) For each of the following scenarios, tell me what data structure I should use, and defend your recommendation. If implementation details matter (such as whether you'll use an array or a linked structure), include them in your discussion.
   • I have a database whose size and contents will not change during the run of my program. The items in my database have integer keys. I want to be able to do a large number of fast searches for items in my database, and it is very important that I conserve memory and keep my code simple.
   • 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 too slow).
   • I have a database of items corresponding to people. Each item has a name field (character string) and a salary field (an integer), among other things. I want to be able to print out this database sorted either by name or by salary. The trick is, I need the printing process to take O(N) time in either case, where N is the number of people.
   
   
   
2. (12 points) Consider a "double-ended priority queue" (DEPQ) that supports the operations AddToDEPQ, DeleteMax, and DeleteMin. For each of the following DEPQ implementations, give Omega/Theta/Big-Oh descriptions of the worst-case performance of AddToDEPQ, DeleteMax, and DeleteMin.
   • An unsorted array.
   • An array sorted in increasing order, so that the smallest item in the DEPQ is always stored at index 0.
   • A linked list sorted in increasing order, with a pointer to the head (smallest item) in the list and another pointer to the tail (largest item) in the list.
   
   
   
3. (12 points) The following is an adjacency table for a 10-node weighted graph, with nodes numbered 0 through 9.

   
       0 1 2 3 4 5 6 7 8 9
      ---------------------
   0 | 0 1 0 0 2 0 0 5 0 0
   1 | 1 0 1 0 0 0 0 0 0 0
   2 | 0 1 0 2 0 2 0 0 0 0
   3 | 0 0 2 0 0 0 1 0 0 1
   4 | 2 0 0 0 0 1 0 0 0 0
   5 | 0 0 2 0 1 0 3 0 0 0
   6 | 0 0 0 1 0 3 0 2 1 0
   7 | 5 0 0 0 0 0 2 0 0 0
   8 | 0 0 0 0 0 0 1 0 0 2
   9 | 0 0 0 1 0 0 0 0 2 0
   

   Using the graph represented by this table, do the following.

   • Draw the graph. Don't forget that the nodes are numbered starting with 0.
   • List the nodes in the order in which they would be visited if you did a depth-first search starting at node 0. Assume that whenever DFS gives you a choice of which node to visit first, you will choose the smallest numbered node available.
   • List the nodes in the order in which they would be visited if you did a breadth-first search starting at node 0. Assume that whenever BFS gives you a choice of which node to visit first, you will choose the smallest numbered node available.
   • Show the shortest-path spanning tree that is generated by Dijkstra's algorithm starting at node 0. Also list the vertices in the order in which they are added to the tree.
   
   
   
4. (3 points) It occurred to me recently that for the last ten or fifteen years, I have been completely out of touch with popular culture (except, of course, for that portion of popular culture whose audience is 2- to 8-year-olds). For example, I don't think I could name a chart-topping song from the nineties, an MTV host, or a cast member from Melrose Place. So help me out here. Tell me something I should read or watch or listen to if I hope to get caught up before my children start rolling their eyes at me.
   
   
5. (9 points) Suppose you start with an empty BST, or AVL tree, or Max Heap whose keys are integers. If you add items with the keys 14, 18, 9, 11, 4, 2, 13, 10, and 12, to the data structure in that order, what does the final data structure look like if:
   • you're using a BST?
   • you're using an AVL tree?
   • you're using a max heap?
   Circle and line drawings are fine in all three cases.
   
   
6. (15 points) The code below is a simplified and de-commented version of a class that I use a lot in my own programs. Answer the following questions about my SymbolTable class.
   • Does my hash table use open hashing (a.k.a. "chaining") or closed hashing (a.k.a. "open addressing") for collision resolution?
   • The hash function I use is one we discussed in class--the Exclusive OR of the ASCII values of all the characters in the string. We agreed that this was a lousy hash function. Why? If I tell you that I usually use a small prime number as my hash table size (47, 61, something like that), is it still a bad hash function? Why or why not?
   • Suppose my program contains the following code.

     
     SymbolTable		myTable(5);
     
     myTable["emu"] = 7;
     myTable["ox"] = 9;
     

     Draw a picture of myTable after this code has executed.

   • Why is the member "hashTable" a pointer to a pointer? Why didn't I just make it an array of pointers?
   • Why do I have two versions of the member function "IsIn"?
   • Why does operator[] return an int& instead of just an int? (Hint: think about the chunk of code above, when I set myTable["emu"] equal to 7.)

   
   
   
   
   #include	
   #include	
   
   const int kMaxKeyLength = 20;
   
   struct STHashNode
   {
   	char            key[kMaxKeyLength];
   	int             value;
   	STHashNode      *next;
   
   	virtual         ~STHashNode( void );
   };
   
   
   class SymbolTable
   {
   	int             nBuckets;
   	STHashNode      **hashTable;
   
   	int             HashFunction( char *key );
   
   public:
   	                SymbolTable( int size );
   	virtual         ~SymbolTable( void );
   
   	int&            operator[]( char *key );
   	int             IsIn( char *key );
   	int             IsIn( char *key, int& );
   };
   
   
   static void LowerCaseCopy( char *destination, char *source )
   {
   	int	i;
   
   	for( i=0; source[i] != '\0'; i++ )
   		destination[i] = tolower( source[i] );
   
   	destination[i] = '\0';
   }
   
   ///////////////////////////////////////////////////////////////
   //	STHashNode::~STHashNode
   ///////////////////////////////////////////////////////////////
   
   STHashNode::~STHashNode( void )
   {
   	if( next )
   		delete next;
   }
   
   ///////////////////////////////////////////////////////////////
   //	SymbolTable::HashFunction
   ///////////////////////////////////////////////////////////////
   
   int SymbolTable::HashFunction( char *key )
   {
   	char result = 0;
   	for( int i=0; key[i] != '\0'; i++ )
   		result = result ^ key[i];
   	
   	return( (int)(result) % nBuckets );
   }
   
   ///////////////////////////////////////////////////////////////
   //	SymbolTable::SymbolTable
   ///////////////////////////////////////////////////////////////
   
   SymbolTable::SymbolTable( int size )
   {
   	nBuckets = size;
   	hashTable = new STHashNode* [size];
   	for( int i=0; i < nBuckets; i++ )
   		hashTable[i] = 0;
   }
   
   
   ///////////////////////////////////////////////////////////////
   //	SymbolTable::~SymbolTable
   ///////////////////////////////////////////////////////////////
   
   SymbolTable::~SymbolTable( void )
   {
   	for( int i=0; i < nBuckets; i++ )
   		if( hashTable[i] )
   			delete hashTable[i];
   
   	delete [] hashTable;
   }
   
   
   ///////////////////////////////////////////////////////////////
   //	SymbolTable::operator[]
   ///////////////////////////////////////////////////////////////
   
   int& SymbolTable::operator[]( char *key )
   {
   	char lowerCaseKey[kMaxKeyLength];
   
   	LowerCaseCopy( lowerCaseKey, key );
   	
   	int index = HashFunction( lowerCaseKey );
   	STHashNode *current = hashTable[index];
   
   	while( current )
   	{
   		if( strcmp( lowerCaseKey, current->key ) == 0 )
   			return( current->value );
   		current = current->next;
   	}
   	
   	current = new STHashNode;
   	current->next = hashTable[index];
   	hashTable[index] = current;
   	strncpy( current->key, lowerCaseKey, kMaxKeyLength );
   	return( current->value );
   }
   
   
   ///////////////////////////////////////////////////////////////
   //	SymbolTable::IsIn
   ///////////////////////////////////////////////////////////////
   
   int SymbolTable::IsIn( char *key )
   {
   	char lowerCaseKey[kMaxKeyLength];
   
   	LowerCaseCopy( lowerCaseKey, key );
   	
   	int index = HashFunction( lowerCaseKey );
   	STHashNode *current = hashTable[index];
   
   	while( current )
   	{
   		if( strcmp( lowerCaseKey, current->key ) == 0 )
   			return( 1 );
   		current = current->next;
   	}
   
   	return( 0 );
   }
   
   
   ///////////////////////////////////////////////////////////////
   //	SymbolTable::IsIn
   ///////////////////////////////////////////////////////////////
   
   int SymbolTable::IsIn( char *key, int& value )
   {
   	char lowerCaseKey[kMaxKeyLength];
   
   	LowerCaseCopy( lowerCaseKey, key );
   	
   	int index = HashFunction( lowerCaseKey );
   	STHashNode *current = hashTable[index];
   
   	while( current )
   	{
   		if( strcmp( lowerCaseKey, current->key ) == 0 )
   		{
   			value = current->value;
   			return( 1 );
   		}
   		current = current->next;
   	}
   
   	return( 0 );
   }