# Sample final

Friday, April 25, 2003

The final covers sorting algorithms: selection sort, merge sort, quicksort, heapsort (all covered in Chapter 13), counting sort, radix sort, bucket sort (see sorting.html); hash tables (see Section 12.2); recursion (as used in Assignment 4); 2-D arrays (as used in Assignment 5); breadth-first search, including shortest path algorithms (Chapter 15) . Contrary to an earlier handout, parsing won't be on the final.

The exam is open textbook (but no other books), open notes. No use of computers. There are 5 problems, each worth 20 points.

1. The following function Graph::bfs was useful in Assignment 5 to carry out a breadth-first search.
```void Graph::bfs ()
{
if (n == 0)
return;

queue <int> Q;

int i;
int j;
int node;

// to keep track of which nodes have been seen
bool* visited = new bool [n];

// initializing arrays
for (i = 0; i < n; i++)
visited [i] = false;

// initialize array that kleeps track
// of which edges have been added to the
// spanning tree
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
treeEdges [i][j] = false;

// seed queue
Q.push (0);
visited [0] = true;

// loop that does the search
while (!Q.empty ())
{
// removed node from queue
node = Q.front ();
Q.pop ();

// add its not yet visited neighbors to the queue
for (i = 0; i < n; i++)
{
if (edges [node][i] && !visited [i])
{
Q.push (i);
visited [i] = true;

// and put into the tree the edges that connect
// the newly added nodes to the just deleted one
treeEdges [node][i] = true;
treeEdges [i][node] = true;
}
}
}

// show the result
drawTree ();

// no memory leak here
delete [] visited;

}

```
Edit the above function so that at the end it prints a message saying how far the farthest visited node was from node 0.

2. Which of the following statements are true? Assume we are sorting integers.

• CountingSort cannot be made to work on negative numbers.
• HeapSort runs in O(n log n) time no matter what the data looks like (except that the data is integers).
• HeapSort will run in O(n) time if the data is of a special kind.
• QuickSort will run in O(n) time if the data is of a special kind.
• MergeSort
• BucketSort always works (i.e., sorts the numbers) but its speed depends on the data.

3. In Assignment 5 we use a 2-D bool array ...
```bool * * edges;
```
with n rows and n columns to remember which edges were present in the graph. Complete the following function:
```void Graph::closure ()
{
// This function adds an edge from node i to node j
// whenever there is an edge from i to k and an
// edge from k to j, for some node k.  (I.e., if one can get
// from i to j in two steps, this function puts in a direct
// connection.)  It keeps doing that until no more edges

int i;

for (i = 0; i < n; i++)
for (j = 0; j < n; j++)

}
```

4. Consider hashing people's names into a hash table of size 1024.

Most (all?) of the following proposed hash functions have a serious flaw. Very briefly describe those flaws. (Assume that whatever number i gets computed, the subscript used is i%1024.)

1. Take the sum (of the ascii code) of the first two letters of the name.
```
___________________________________________________

```
2. Take the sum (of the ascii code) of all the letters of the name.
```
___________________________________________________

```
3. Take the product (of the ascii code) of all the letters of the name.
```
___________________________________________________

```
4. Take the product (of the ascii code) of the first two letters of the name.
```
___________________________________________________

```

5. Write a function Polynomial::brackets () that prints a polynomial of the kind used in Assignment 4 as a line of text, fully parenthesized, but with square brackets used for multiplication, parentheses for addition and subtraction, like this:
```      [ ( x - 1 ) * ( [ 2 * x ] - 3 ) ]
```