CS251 Homework 2

Final Exam Review


Answer the following questions in preparation of the final exam. Write the questions and the answers neatly and turn them in during the final exam. I will post the solutions one day before the final exam but I encourage you to try to solve the review yourself first.

1. Starting with an empty tree, perform the following operations in the AVL tree. Indicate the resulting tree after each step. Also show intermediate steps if any.

insert(5);
insert(6)
insert(7);
insert(8);
insert(9);
insert(10);
insert(11);
insert(12);
insert(13);
insert(14);
insert(15);
insert(16);
insert(1);
insert(2);
insert(3);
insert(4)
remove(10);
remove(11);
remove(12)
remove(13);
remove(14);
remove(15);
remove(9);


2. Given the sequence { 10, 6, 9, 2, 3, 11, 8, 15, 1, 4} sort the numbers using Merge Sort. Write the intermediate steps.

3. Sort the same numbers using Quick Sort. Write the intermediate steps.

4. Sort the same numbers using Radix Sort. Use 4 bits. Write the intermediate steps.

5. Using bucket sort sort the numbers { 1,2,2,6,6,6,6,6,6,3,3,3,2,2,1,1,9,9,2,2,}

6. Write the complexities (O(?))  of Merge Sort, Quick Sort, Radix Sort, and Bucket Sort.

7. Find an optimal Huffman encoding trie for the sentence: "sara cynthia sylvia stout". How many bits  are needed in the compressed and in  the original sentence  in ascii (assume Ascii encoding neds 8 bits/character)?

8. Given the following graph, find the Depth First Search Tree of the following graph starting at node L. The DFS tree includes only the discovery edges and the vertices. Assume that the vertices appear in alphabetical order in the adjacency list used in the traversal.

Graph 1
9. Using the graph in question 8, find the Breadth First Search Tree of the graph in 9. starting at node L. The BFS tree includes only the discovery edges and the vertices.

10. Using Dijkstra's algorithm find the shortest path tree of the graph in question 9 starting at vertex L.

11. Using the Prim-Jarnick algorithm, fiind the minimum spanning of the graph in 9. starting at vertex L.

12. Implement in "C" the method 
     #define MaxVertices 50
     void shortest_path(int v, int n, 
                        int weight[MaxVertices][MaxVertices], 
                        int aDistance[MaxVertices], 
                        int parent[MaxVertices] )
that returns in aDistance[i] the shortest distance from vertex v to vertex i and in parent[i] the previous vertex in the shortest path from v to i. n is the number of vertices and weight[i][j] is the weight in the edge (i,j). If edge (i,j) does not exist,. then weight[i][j] is -1.

 13. Write the implementation of the remove(int key) method of the AVL tree that removes the node with that key. You may base your implementation with the one given in class. Also include the implementation of any auxiliar procedures you use.
typedef int KeyType;
typedef char * ValueType;
struct AVLNode {
  int _heigt;
  KeyType _key;
  ValueType _value;
  AVLNode  * _left;
  AVLNode * _right;
  AVLNode * _parent;
};

class AVLTree {
  AVLNode * _root;
public:
  ... Other methods ...
  bool remove( KeyType key ); // Remove a key. It returns OK or false if key is not found.
};

bool
AVLTree::remove( KeyType key )
{
   //Implementation
}
14. Write the code for quicksort that sorts a sequence of n integers stored in array a. Include the code of any auxiliar functions.

void quicksort(int *a, int n ) {



}

15. Write the code for mergesort that sorts a sequence of n integers stored in array a. Include the code of any auxiliar functions.

void mergesort(int *a, int n ) {



}