------------------------------------------------------------
COP 3530 Data Structures and Algorithms   M. Schmalz  990526
------------------------------------------------------------

EXAM #1 REVIEW OUTLINE:

TOPICS:	1) Remember the basics of set operations, maps, and
	   functions that we discussed in the review of 
	   discrete math.  

		-- For example, I might ask you to identify
		   various set operations -- what does card(S)
		   tell you?  choice(S)? etc...

	2) Study the class notes on selection, in particular:

		-- why are most non-tree-structured selection
		     algorithms costly (i.e., O(n) complexity)?

		-- why are sorted sequences required for 
		     binary search?

		-- be able to reproduce two selection algorithms
		     in p-code with a simple sketch as to how
		     they work

	3) Know your selection algorithms:

		-- know how each selection algorithm discussed in
		     class works, being able to sketch its operation
	  	     using p-code

		-- be able to draw up a work budget for each selection
		     algorithm, as we did in the homework assignment

		-- know the advantages and disadvantages of each 
		     selection algorithm discussed in class

	4) Know your sorting algorithms:

		-- know how each sorting algorithm discussed in
		     class works, to the extent that you can give
		     a sketch of its operation (including p-code)

		-- be able to diagram the application of each 
		     algorithm to an eight-element vector that 
		     contains both positive and negative numbers

		-- be able to compare the complexity of any
		     two or more sorting algorithms, and tell
		     (in 1-2 sentences) what causes this
		     complexity to occur in *each* algorithm

		-- be able to discuss, in one or two *clear*
		     sentences, the advantages and disadvantages
		     of each sorting algorithm

		-- finally, know (for each algorithm) the best-
		     and worst-case input configuration, and why
		     it is the best or worst case.

	5) Know your data structures covered thus far:

		-- what is the difference between singly- and doubly-
		     linked lists, heaps, stacks, queues, and priority
		     queues, also arrays?

		-- which operations are appropriate for each data
		     structure (e.g., "push" for stack versus "enqueue"
		     for queues

		-- what are the advantages and disadvantages of each 
	    	     data structure, in terms of work requirement for
		     doing each of the following algorithms:

			(a) linear search
			(b) bin sort
			(c) quick sort (use only applicable data structures)
			(d) merge sort ( "   "        "       "       "    )
		 	(e) heap sort  ( "   "        "       "       "    )

Take one of these topics per day, read through the appropriate material
in the book, and work the homework problems to which Dr. Sahni has
answers on his Web page. 

Also, there will be no questions about Java on the exam.

- EOF -