Computer Science 113
Sample Final Questions

True or False. Give reasoning.
1. There are comparison based sorting methods like heapsort which can sort n items in O(n) time.
2. The above tree is a binary search tree.
3. The above tree is a heap.
4. The above tree is a balanced tree.
Consider the following graph:
```
                  6  7
     		1--2--3
	       4|  |  |5 	
		| 8|  |
		5--6--4
                  1  8
```
1. Give its adjacency matrix and find a minimum weight spanning tree for it.
2. Give a high level description of an algorithm that takes a graph G and a vertex v and visits each node in the graph in depth 1st order
1. Show how the following keys 5,4,7,12,13,2,9 would hash to a table of size 7 using the hash function x%7 and using linear probing to resolve collisions.
2. Give a sufficient condition for the probe sequence in double hashing to cover all entries of a table of size M.
3. Show how the list in the first part would be hashed if we resolved collisions using double hashing with probe function p(k):= max(1,(k/2)%7).
1. Describe step by step how selection sort would sort the following array:
```
		A:={6,5,4,7,3,9}
```
2. Do the same for mergesort.


5. Consider the following binary tree. 

                          a
                         / \
                        b   c
                       / \   \
                      d   e   f
                         / \
                        g   h

Which of the following might be the output of a postorder traversal 
of this tree ?

a. dghebafc
b. dgehbfca
c. dghebfca
d. dbgehafc
e. dbgehfca

6. Give the function header for each of the following.

   a) Function hypotenuse that takes two double-precision floating point 
      arguments side1 and side2, and returns double-precision floating 
      point value.

   b) Function IntToFloat that takes an integer argument Number and returns 
      a floating point value.

7. Here is the adjacency matrix A of a weighted undirected graph. Assume
the vertices are $v sub 1, v sub 2, v sub 3, v sub 4, and  v sub 5$ and that
position (i,j) in the matrix corresponds to edge ($v sub i, v sub j$).

       0 3 6 2 4
       3 0 3 0 4
A =    6 3 0 0 5
       2 0 0 0 7
       4 4 5 7 0

a. Draw a picture of this graph.

b. Give a breadth first search of the graph starting at vertex $V sub 2$.

8. For any tree depth-first search (dfs) and breadth-first search
(bfs) take about the same number of steps. 
However, the space required by the two algorithms may differ greatly.
assume we use a stack to implement the DFS and a queue to do the BFS. 

a. Give an example of a tree with n vertices where a stack of size n-1 is 
needed to do dfs whereas the queue of the bfs of the same tree will never 
have more than two vertices on it at a time. Both searches start from the same vertex.

b. Give an example of an n vertex tree for which the queue used in bfs 
will have n-1 vertices on it at some time while the stack used
for dfs has at most one vertex on it at any time. Both searches
start from the same vertex.

Computer Science 113 Sample Final Questions

Computer Science 113
Sample Final Questions