Briefly discuss the approach you would take to the following programming scenarios. Make any assumptions you need to. There are no “right” answers for any of these questions.

1. You are the manager of a collection of data that keeps track of the current graduate students in the department. David Notkin wants the data sorted in alphabetical order. Each night, you receive a list of new grad students that have been admitted, as well as a list of students who perished while stoking the furnace of the steam-powered Turing machine. David is monitoring your computer usage, so your code better handle this batch insertion and deletion as efficiently as possible. How will you keep David happy?

Ideas Presented:

Give David a foot massage
Balanced Tree (AVL)

- Inserts and Removes will take O(log n) time

- An inorder traversal easily returns the input in sorted order.

Hashtable:

- Make an array of 26 linked lists (one for each letter)

- Place names into the array based on the first letter of their last name

- Keep the individual lists sorted

- Cuts down on the amount of searching needed for inserts and deletes

- Returning the sorted input is also fairly easy

- Some lists might be longer than others (such as the S list), so further breakdowns might be needed (i.e. A list S – Sm, Sn-Sz).

A sorted linked list:

- When you receive a list of inserts and deletes to do, sort these jobs by the names involved.

- Starting from the beginning of the list, traverse across the list till you can do the first job in the list. Do it, then starting from that spot, move forward till you can do the next. Repeat.

- If b is the number of jobs in the batch, the total time for doing all these operations will be O(b log b + n). If b << n, then this is O(n).

Tries:

- Specialized tree structure for storing words.

- Inserting and deleting would be proportional to the length of the word involved

- Returning the sorted data would be a challenge

2. You are working with a large set of data, say a listing of nodes on a network and the traffic they experience, that is originally in random order. On semi-regular occasions, the values of particular items could change. For example, item X could have its value change from 3 to 70. You need to be able to find these items and update these values rapidly. How would you do this?

Ideas Presented:

Assumption made: The values change without you knowing it. You want to keep the list ordered. These changes also occur infrequently.

- Initially sort the data using QuickSort.

- Each time you need to do a lookup, run InsertionSort first. Ideally, the list should be mostly sorted already, so this sort will run fast (i.e. linear time).

AVL Tree (sorted on the amount of traffic):

- To change a value, you have to find the node, remove it, then reinsert it with its new traffic amount. This is because the binary search tree property might get violated.

- Each find, insert, remove will take O(log n) time.

- Each change will require 2 finds, an insert, and a remove.

AVL Tree (sorted on the name of the node):

- To change a node, one has to find the node and then change its traffic value. As the name does not change, the BST property will still hold.

- Each change will require only 1 find.

Splay Tree (sorted on the name of the node)

- Assumption: some routers will change more often than others.

- Splay trees will keep the most frequently changed nodes near the top of the tree.

- Changing the traffic value will require only 1 find as in the AVL-on-name example above.

- Finds will be more likely to take only O(1) time.

Splay Tree (sorted on the traffic values)

- Same assumption as before.

- Changing a value will require a remove and an insert.

- Nodes that change frequently will still be high in the tree, and less accessed routers will be more at the bottom.

3. The data structure grabbag is similar to a stack or a queue, but instead of the first or last element being removed on a pop or dequeue, a random element is removed on a grab. Grabbags are very useful for simulating random draws without repetition, like drawing cards from a deck or numbers in a bingo game. Consider the following ADT:

Grabbag:

Insert(item e): e is inserted into the grabbag

Grab(): if the grabbag is not empty, return a random element from the grabbag

Size(): return how many items are in the grabbag

List(): return a list of all items in the grabbag

Describe how you would implement a grabbag. Discuss the time complexities of each of the operations.

Ideas Presented:

To be discussed next week.