Name_________________
                     CIS 350 Final Exam
                         Winter '97
(2 points)

 1. Use order arithmetic to evaluate:

      O(3n * [(n - 1) + (n * log n) + n!])


(3 points)
 
 2. In the context of object oriented programming describe the 
    role of a "method"?


 
 
 
 
 



 3. Describe a programming situation in which a digraph would 
    be preferred to a binary search tree as a data structure.
 
 
 
 
 
 
 
 

 
 4. What are the economic benefits of using object-oriented 
    programming methodologies?
 
 
 
 
 
 
 


 
 5. Why would it ever be necessary to remove recursion from an 
    algorithm once it has compiled and executed correctly?




                                        Name_________________
 
 6. How are parallel algorithms different from distributed 
    algorithms?










 7. What is the principle of divide and conquer as applied to 
    parallel algorithm design?










 8. With no prior knowledge of order, and for a large number of 
    array elements (n > 300), order these sorting algorithms from    
    greatest (1) to least (4) efficiency:


         bubble    ________           heap      ________



         shell     ________           selection ________


 9. Describe the critical portion of the quicksort algorithm 
    which determines whether or not quicksort exhibits its 
    worst case behavior.









10. Explain why Kruskal's algorithm is an example of a greedy 
    algorithm?


                                          Name_________________

11. Perform the AVL rotation required to rebalance this tree.

             A
          /     \
         B        C
                /   \
               D     E
              /
             F



12. Given the following heap, move the root node to its final 
    resting place and readjust the heap according to the text 
    rules for the heap sort.
 
                17 
             /      \
          10         12
         /  \       /  \
        8    6    11    5 
       / \  
      7   4  


(4 points)

13. Using h(x) = x % 5 and chaining to resolve collisions, draw a
    diagram which shows the results of hashing the numbers:

      13  4  14  15  8  5  6  16  9










14. Use Dijkstra's algorithm to find the shortest path from 
    vertex 2 to each other vertex in the digraph shown below.

            tail
         | 1  2  3  4
       --------------
    h  1 | 0  5  2  
    e  2 | 2  0  3  1
    a  3 |   2  0  
    d  4 |       0 
                                           Name_________________

15. Consider a doubly linked list stored in the array structure
    below (I is the subscript value). Show the contents of the 
    structure after deleting the node pointed to by P.
 
       I INFO LEFT RIGHT 

       1  12    0    3
       2   1    4    5    P = 2         
       3  -6    1    4
       4  10    3    2 
       5  17    2    0



16. Create a Huffman code for the characters: b, l, u, e with the 
    corresponding the relative frequencies:  .2, .4, .25, .15  












17. Use the digraph adjacency matrix below and topologically sort     
    vertices 1 to 5.

        | 1  2  3  4  5
      -----------------
      1 | 0  0  1  0  0
      2 | 0  0  1  1  0
      3 | 0  0  0  0  1
      4 | 0  0  0  0  1 
      5 | 0  0  0  0  0




18. Solve the recurrence relation shown below.

      T(n) = 1                   for n = 1       
           = 2 * T(n - 1)        for n > 1






                                         Name_________________
(5 points)

19. Redraw this order 3 B-tree after deleting E and L in that
    order.
                      M-Q
               /       |       \
           E-K         O          W
         /  |  \      / \       /   \
      A-B  I-J  L    N   P   T-U     Z








20. Determine the worst case running time for the algorithm 
    below. Express your answer in big-Oh notation and explain how 
    it was determined (this means show me all your work).

      cin >> N;
      for (I = 0 ; I <= N; I++)
        for (J = 0; J <= N; J++)
           cin >> A[I,J] >> B[I,J];

      for (I = 0; I <= N; I++)
         for (J = 0; J <= N; J++) 
         {
           C[I,J] = 0;
             for (K = 1; K <= N; K++)
               if (I > J)
                 C[I,J] 0 = C[I,J] + A[I,K] * B[K,J];
         } 







(6 points)
 
21. Write a recursive procedure (or function) which has as 
    input parameters a pointer to a binary tree and a numeric key 
    sought for and returns a "pointer" to the node containing the 
    key if found or NULL otherwise.
 
 
 
 
 
 
                                             Name_________________
(8 points) 
 
22. Write a procedure, which receives graph and a vertex as input         
    parameters. Your procedure should delete the vertex from the         
    graph, along with all edges incident on the vertex. Include 
    all declarations needed to implement the graph type in your 
    solution.