Review Questions for the Final Exam

CS211 - Fall 2000

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)

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.
In what order are edges added to the MST using Prim's Algorithm (growing a single tree) starting from vertex A?
In what order are vertices marked by Dijkstra's Shortest Path Algorithm starting from vertex A?
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.
How long does it take to determine if an undirected graph contains a vertex that is connected to no other vertices?

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.

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.
Give a sequence of seven unions, on the original eight sets, that produces a tree of minimum height. Draw the resulting tree.
Explain why both the min- and max-height trees use seven unions.
What is path compression in the union/find algorithm?

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?]

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).

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.

Show the resulting min-heap if we build it using successive insert operations.
Show the resulting min-heap if we build using the bottom-up technique discussed in lecture.

Problem 7

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

What is the running time for each method when all the keys are equal?
When the keys are in order?
When the keys are in reverse order?