Solutions to Review Questions for the Final Exam

CS211 - Fall 2000

Please let me know via email (chew@cs.cornell.edu) if you find mistakes in the solutions.  Past experience indicates that I may have made some.

The Final Exam will take place at noon on Monday, December 11 in Barton Hall on the east side.  Note that Econ 101 students will be taking an exam at the same time in Barton central and Barton west.

The use of extra material is not permitted during the exam (i.e., no textbook, no notes, no calculator, etc.).

The exam includes all material from the entire semester.  See the Materials Page for a list of topics covered in lecture and the corresponding readings. 

The exam will attempt to gauge your knowledge and understanding of course concepts. You should understand the terms and concepts used in the course, but you shouldn't need to memorize the specific code given in the text or in lecture.

The review questions given here are not meant to exhaust the possible topics for exam questions.  Check the online material and consider reviewing Prelims I and II, the lectures, the homework assignments, and the previous Review Questions (Review I, Review II, Extra Review Problems).

Review Questions

Problem 1

For this problem, you are to answer questions about the following graph. 
		       (e)             (f)
			|		|
			|		|
			|17		|15
			|		|
		3	|	10	|     1
       (A)-------------(c)-------------(g)---------(h)
	|		|		|	  /
	|		|		|	/
	|7		|9		|11   /5
	|		|		|   /
	|	12	|	14	| /
       (b)-------------(d)-------------(i)
  1. In what order are edges added to the Minimum Spanning Tree (MST) using Kruskal's Algorithm (merging subtrees)? List the edges by giving their endpoints.
    gh,Ac,hi,Ab,cd,cg,fg,ce
  2. In what order are edges added to the MST using Prim's Algorithm (growing a single tree) starting from vertex A?
    Ac,Ab,cd,cg,gh,hi,fg,ce
  3. In what order are vertices marked by Dijkstra's Shortest Path Algorithm starting from vertex A?
    A,c,b,d,g,h,i,e,f
  4. In what order are vertices processed by Breadth First Search starting from vertex A?  A vertex is processed when it is removed from the queue.  Use alphabetical order when there is a choice of vertices.
    A,b,c,d,e,g,i,f,h
  5. How long does it take to determine if an undirected graph contains a vertex that is connected to no other vertices?
    O(V2) for an adjacency matrix.  O(V) for adjacency list.

Problem 3

Consider a tree implementation for the union/find problem in which the smaller set is merged to the larger and the name of the set is taken to be the element stored at the root of the tree. Suppose we initialize our sets so that each integer between 1 and 8 (inclusive) is contained within its own set.
  1. Give a sequence of seven unions that produces a tree whose height is as large as possible. Your answer should be a sequence of procedure calls of the form union(a,b) where a and b are integers between 1 and 8. Draw the resulting tree.
    There are lots of possible sequences that would work here. One of them is: U(1,2), U(3,4), U(5,6), U(7,8), U(1,3), U(5,7), U(1,5).
  2. Give a sequence of seven unions, on the original eight sets, that produces a tree of minimum height. Draw the resulting tree.
    Again, there are many correct answers. Here's one: U(1,2), U(1,3), U(1,4), U(1,5), U(1,6), U(1,7), U(1,8).
  3. Explain why both the min- and max-height trees use seven unions.
    max height min height 
      1
 /|\
2 3 5
 /  | \
4   6  7
      /
     8
    		 
          1

 /| | | | |\
2 3 4 5 6 7 8

    We are building trees on 8 nodes and all such trees have 7 edges.  (You should be able to prove by induction that all n-node trees have n-1 edges.)  Each Union operation creates a single edge, so to build an 8-node tree, we always need at least 7 Union operations.

  4. What is path compression in the union/find algorithm?
    When doing the find operation, each node passed on the way to the root is made to point at the root.

Problem 4

We know that a sequence of n union/find operations using union-by-size and path compression takes time O(n alpha(n)) where alpha(n) grows extremely slowly.   What if all the union operations are done first?  Show that a sequence of n unions followed by m finds takes time O(n + m). [Hint: The time for a find operation is proportional to the number of links that it changes.  How many links are there?]

First recall that each Union operation takes time O(1); thus, all we have to show is that not too much time is spent on Finds. Observe that each edge of a tree has to be created by a Union operation; thus, the total number of tree edges is O(n). Suppose we want to count only edges that are deep in a tree, i.e., just those edges that are not edges from the root. There are O(n) such deep edges.

A Find operation on item i is slow only when i is deep in a tree; then it takes time proportional to the depth of i. The Find operation also converts a bunch of deep edges into root edges. As a matter of fact, the Find operation takes time proportional to a constant plus the number of deep edges converted to root edges. Since there aren't very many deep edges (just O(n) of them), the total time spent on Find operations is at most O((number of Find operations)+(number of edges converted from deep edges to root edges)) or O(m+n).

Problem 5

The departmental phone number is 2557316. Show how the order of the digits changes as the digits are sorted using Quick Sort. Insertion Sort. Merge Sort. Heap Sort.  For Quick Sort, assume that the first item is used as the pivot item (this is not a good choice).
Quick Sort Insertion Sort Merge Sort Heap Sort
start: 2557316
swap: 1557326
split: 1,557326
swap: 1,257356
swap: 1,237556
split: 1,23,7556
...
 2557316
2355716
1235576
1235567		 start: 2557316
split: 255,7316
split: 2,55,7316
split: 2,5,5,7316
merge: 2,55,7316
merge: 255,7316
split: 255,73,16
split: 255,7,3,16
merge: 255,37,16
split: 255,37,1,6
merge: 255,37,16
merge: 255,1367
merge: 1235567		 start: 2557316
build: 2567315
2765315
7265315
7562315
get: 556231,7
655231,7
get: 15523,67
55123,67
get: 3512,567
5312,567
get: 231,5567
321,5567
get: 12,35567
21,35567
get: 1,235567
get: 1235567

I've only shown part of the QuickSort; it goes on for a few more steps. For Merge Sort, I'm arbitrarily assuming that whenever we can't split evenly then the first half is smaller. For Heap Sort, I'm arbitrarily assuming that whenever there is a tie between two large children, we'll use the right child.

Problem 6

Suppose we wish to create a Priority Queue containing the keys D A T A S T R U C T U R E.
  1. Show the resulting min-heap if we build it using successive insert operations.
  2. Show the resulting min-heap if we build using the bottom-up technique discussed in lecture.
Using Insert Bottom Up 
           A
        /     \
     A           E
   /   \       /   \
  C     S     R     T
 / \   / \   / \
U   D T   U T   R

           A
        /     \
     A           E
   /   \       /   \
  C     S     R     R
 / \   / \   / \
U   D T   U T   T

Problem 7

Consider the following sorting methods: Insertion Sort, Merge Sort, Quick Sort, and Heap Sort. 

  1. What is the running time for each method when all the keys are equal? 
    IS: O(n); MS: O(n log n); QS: O(n log n); HS: O(n)
  2. When the keys are in order? 
    IS: O(n); MS: O(n log n); HS: O(n log n)
    For Quick Sort, the time depends on the scheme for choosing the pivot item.  If the first or the last item is used as the pivot then the time is O(n2).  If the middle item or median-of-three is used then the time is O(n log n).
  3. When the keys are in reverse order?
    IS: O(n2); MS: O(n log n); HS: O(n log n)
    For Quick Sort, the time depends on the scheme for choosing the pivot item.  See (b).