Study Guide for CS 302 Examination April 12, 2005

Revised April 8, under construction

There will be some true/false questions.

There will be some fill-in-blanks questions.

Be prepared to write a small C++ program in its entirety.  It will be very
small.

Be prepared to rewrite a few lines of the code that you turned in on some
programming assignment.

I will ask you to find the asymptotic time complexity of some small portion
of code.

I will ask you to illustrate heapsort, just as with the last test.

I will ask some other questions about some of the following topics:

	sorting, including quicksort, mergesort, and polyphase mergesort
	search structures, including binary search trees, hash tables,
		ordered lists, and unordered lists
	priority queues, including stacks, queues, and heaps
	various implementations of various ADTs, including treaps
	Kruskal's algorithm
	balancing binary trees
	hashing, including open addressing and separate chaining
	traversal of structures, e.g., preorder, postorder, inorder
	sparse arrays (although we have done very little in that area)
	loop invariants
	recursion, memoization, divide & conquer, greedy, dynamic programming

(More later)