CS 201: Data Structures

Takehome Exam, due 12:30PM on 12 Mar 2014. Submit via Moodle in PDF form.

Include your source code for #6 in your PDF file. You don't need to submit your source code separately.

This is an open-notes, open-Internet, open-book exam. The only thing you aren't allowed to do is consult with other people about the exam (except for Jeff Ondich, with whom you may discuss the exam as much as you like). Just to be clear: posting questions on online forums counts as consulting with other people, and is thus prohibited. If you use information obtained online or from a book, cite your sources.

(6 points) Let's pretend you have a queue implemented as a circular array of 4 String references (it's a small queue, admittedly), with indices called front and back to keep track of the state of the queue. front always points to the first item in the queue, and back points to the last item in the queue.
1. How should you initialize front and back to indicate an empty queue?
2. Show the state of the queue (including the contents of the array and the values of front and back) after you have initialized to empty and then performed Add("goat"), Add("newt"), Add("kudu"), Delete(), Add("coatimundi"), Delete(), Add("vole").
3. During the goat/newt/kudu/etc process, was the queue ever full?
4. In general, how can you tell whether the queue is full?
(6 points) Imagine starting with an empty binary search tree whose nodes have characters for keys, and adding the letters F A C E T I O U S L Y to the tree in that order. Show the resulting tree if:
1. The tree is an ordinary binary search tree.
2. The tree is an AVL tree. Here, show all the intermediate trees as well as the final tree. (You'll need to read Section 9.2 of the textbook for this part.)
(4 points) Consider the following binary search tree, whose nodes' keys are letters of the alphabet:

J E N C I K P B D G - - M O Q A - - - F H - - - - L - - - - R

(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 J is the root, the children of N are K and P, and Q has a right child R but no left child.)

Show the tree that results when you delete the root (J) from the tree using the BST node deletion algorithm in your textbook (p. 323 in section 6.4).
(6 points) Start with an array of characters containing the letters A R T I C H O K E S at indices 0 through 9.
1. Apply the heap formation algorithm that forms the first stage of Heapsort (using a max-heap). Show the resulting array.
2. Delete the largest (i.e. closed to the end of the alphabet) item from the heap. Show the resulting array.
(12 points) For each of the following scenarios, recommend a data structure. Briefly justify your recommendation, using complexity arguments and big-oh notation where appropriate.
1. 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.
2. 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, though it is sufficient to hold all the items. (Note that this scenarios can actually happen on low-memory handheld devices, on chips embedded in cars and appliances, etc.)
3. You're writing a system that processes credit card validation requests. The requests often come in faster than you can process them, so they need to be stored in some sort of data structure while the processor handles other requests. Furthermore, some of your company's clients have paid a big fee to be "Preferred Customers." When a credit card validation request comes in from a Preferred Customer, it needs to be processed before the ordinary non-preferred customer requests.
4. You have a database of a few hundred city names. You want to do frequent additions and searches, and you also want to be able to print out the items in sorted order.
(6 points) Suppose you have a binary tree node class, like this:

class BTNode { public int data; public BTNode left; public BTNode right; }

Write a method to compute the maximum data value in a binary tree:

/** * Returns the largest data value in the specified binary tree, * or Integer.MIN_VALUE if root is null. Assumes the * data values of nodes are non-negative integers. * * @param root -- the root of the tree */ static int max(BTNode root)

Don't forget: (1) this is a binary tree, not necessarily a binary search tree, and (2) recursion is your friend.
(6 points) Elmo, Zoe, and Grover are planning to implement a hash table that will have 1024 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. Criticize (positively or negatively) each of these proposals.
1. Elmo advocates adding the letter numbers of the letters in the word together (e.g. ada = 1 + 4 + 1).
2. Zoe wants to use a 32x32 2-dimensional array of slots, and take the ASCII values of the first two letters of the word, mod 32, as the indices of the slot into which the word will go.
3. Grover wants to consider the character string as a string of bits, break the bit string into 10-bit chunks, and XOR these chunks together to get the hash value.
(2 points) Please direct me to a web site that you think I should see. Maybe it's amusing or enlightening or stupidly entertaining or just weird or disturbing or whatever.
(9 points) Consider a graph G with 9 nodes numbered 0 through 8, whose edge set is {(0,3), (0,1), (0,7), (3,6), (3,4), (1,4), (4,5), (4,2), (7,5), (6,2), (8,2)}.
1. Draw the graph.
2. Using this breadth-first search algorithm, list the nodes in the order in which they will be visited in a search starting at node 0. Draw the resulting spanning tree.
3. Using this depth-first search algorithm, list the nodes in the order in which they will be visited in a search starting at node 0. Draw the resulting spanning tree.
(6 points) Suppose I have an array in which I'm storing integers as my program generates them. I don't know at compile time how much space I will need, so I decide to start with an array of 1024 integers, and reallocate the space if I need to.

Whenever I generate a new integer, I put it in the first available slot in the array. If the array is full when the new integer arrives, I (1) allocate a new array, bigger than the first, (2) copy all of the old array's contents to the new array, and (3) add the new integer to the end of the new array.

Your job is to analyze the running time of this plan by counting integer assignment statements. Thus, every time we add an integer to an existing array, you should count 1. Also, whenever we copy the old array to the new array, count 1 for each element of the old array.

Assume that we start with an array containing 1024 elements, and that the program generates 10,000 elements. Compute the number of integer assignments for each of the following reallocation strategies. Then, assume the program generates N elements, and give a big-oh/theta/omega analysis of each strategy.
1. When you reallocate, add an extra 1024 integers. The arrays will thus be 1024, 2048, 3072, 4096, etc. integers long.
2. When you reallocate, double the size of the array. The arrays in this case will be 1024, 2048, 4096, 8192, etc. integers long.