Midterm 2

1. Convert the following complete binary tree to a heap by applying the standard Siftdown procedure from the leaves up to the root. Write your solution in the blank tree provided. [5]



2. In Kruskal’s algorithm for finding a minimum spanning tree in a graph, a heap is used to store edge weights – why is this approach used instead of pre-sorting the list of edge-weights ? [5]

Because we need enough of the smallest edge weights until we cover all vertices – we don’t need the whole set

3. What are the minimum and maximum numbers of elements that can be stored in a heap of height h ? [4]

Min= 2^(h-1) Max=2^h-1

4. Draw a representation of a Binary Search Tree after inserting the following elements in the order given. Assume the tree is initially empty. [6]

120, 42, 43, 7, 2, 32, 37, 24, 40



5. Draw the following Binary Search Tree after the node 31 has been deleted. Assume that duplicate elements are usually stored in the right subtree. [3]



6. Write the code to output the nodes of a Binary Search Tree in ascending order. [7]

void BST::Sort ( Node *rt )
{
   if (rt==NULL) return;
   Sort (rt->Left);
   rt->Output ();
   Sort (rt->Right);
}

Assume the following definitions :

class Node {
public:
   int aValue;
   Node *Left, *Right;
   void Output ();
};
class BST {
public:
   Node *root;
   void BST::Sort ( Node *root );
   .
   .
};

Assume that the function is called externally using the statement Sort (root);
To output the contents of a node *p, use the statement p->Output ();

1. Using the weighted union rule and path compression, draw the general tree for a parent pointer implementation that results from the following set of equivalences on the set of integers from 0 to 7. Initially each element is in its own set. Resolve the problem of equally-sized trees by making the tree with the larger root a child of the tree with the smaller root. [7]

   (0, 1) (5, 6) (0, 6) (2, 3) (3, 4) (0, 2) (6, 7)

   

2. Convert the following general tree to a binary tree using a left-child/right-sibling structure to correspond to the left and right children respectively. [8]

   

1. Write an algorithm in pseudo-code to perform a Depth-First-Search traversal of a graph. [10]

   Mark all nodes unvisited.
   While nodes are unvisited, perform DFS on them.
   Function DFS (node aNode)
   ...Visit (aNode)
   ...Set aNode to be visited
   ...For each neighbor N of aNode that is unvisited, DFS(N)

2. What does Dijkstra’s algorithm compute, as compared to Floyd’s algorithm ? [5]

   Dijkstra: shortest distance from one vertex to all others
   Floyd: shortest distance between every pair of vertices

3. Suppose we have implementations of Prim’s and Kruskal’s algorithms with time complexities q (|V|²) and q (|E|Log|E|) respectively. Explain which algorithms perform better for sparse and dense graphs. [5]

   Dense: E is approximately V^2, hence Prim is better
   Sparse: E is less than V, hence Kruskal is better

4. State one possible technique to improve the time complexity of Prim’s algorithm. [5]

   Use a priority queue for edge weights

5. Prove by induction that a graph with n vertices has at most n(n-1)/2 edges. [5]

   Base case: n=0: 0=n(n-1)/2 edges
   n=1: 0=n(n-1)/2 edges
   Thus the formula holds for the base case
   Suppose the formula holds for k vertices.
   A new vertex will introduce k new edges.
   Therefore, edges(k+1) = edges(k) + k = k(k-1)2+k = (k+1)k/2 = (k+1)((k+1)-1)/2
   Hence, by induction, the result holds.

1. Name one advantage each of the Selection Sort and Insertion Sort procedures. [6]

   Selection: Swap is always order n.
   Insertion: Best case for comparisons is order n.

2. What is the time complexity of QuickSort in the best and worst cases ? [4]

   Best: O(n Log n)
   Worst: O(n^2)

3. Show the steps of a MergeSort procedure applied to the following list of integers. [8]

   22, 31, 42, 11, 12, 41, 23, 13, 21, 33

   22 31 42 11 12 41 23 13 21 33
   (22 31 42 11 12) (41 23 13 21 33)
   (22 31 42) (11 12) (41 23 13) (21 33)
   (22 31) (42) (11) (12) (41 23) (13) (21) (33)
   (22) (31) (42) (11) (12) (41) (23) (13) (21) (33)
   (22 31) (42) (11) (12) (23 41) (13) (21) (33)
   (22 31 42) (11 12) (13 23 41) (21 33)
   (11 12 22 31 42) (13 21 23 33 41)
   (11 12 13 21 22 23 31 33 41 42)

4. Show the steps of a Radix Sort procedure applied to the following list of integers. [7]

   22, 31, 42, 11, 12, 41, 23, 13, 21, 33

   1 – 31, 11, 41, 21
   2 – 22, 42, 12
   3 – 23, 13, 33

   31, 11, 41, 21, 22, 42, 12, 23, 13, 33

   1 – 11, 12, 13
   2 – 21, 22, 23
   3 – 31, 33
   4 – 41, 42

   11, 12, 13, 21, 22, 23, 31, 33, 41, 42