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

EXAM #2 REVIEW OUTLINE:

TOPICS:	1) Know basics of Stacks, Queues, Graphs, and Trees
		-- what are they?
		-- what do they look like?
		-- what role do they play in computer science?
		-- what are their basic ADT operations?

	   Note:  There will be a few questions on ADT ops for
		  each of these structures, so know them well.

	2) Remember the differences between Stacks and Queues,
	   especially when implemented in terms of arrays or
	   lists.

		-- For example, I might ask you to compare the 
		   complexity of stack and queue ADT operations
		   implemented using an array versus a list.

	3) Know your graph representations and traversal algorithms

		-- what is the difference between adjacency matrix,
		     edge list, and adjacency list representations?

		-- what is the complexity of various graph oper-
		     ations using adjacency matrix, edge list, or
		     adjacency list representation?

		-- given a graph vertex set and edge set, be able
		     to draw the adjacency matrix, edge list, or
		     adjacency list representation

		-- what is the algorithm and complexity for
		     BFS and DFS?

		-- be able to apply BFS or DFS to graphs that
		     are not tree-structured, and be able to
		     list the vertices as encountered during
		     graph traversal

	4) Know your binary search trees (BSTs) and AVL trees

		-- know what the properties of BSTs and AVL
		     trees are, and how to maintain those
		     properties during insertion and deletion
		     for LL, LR, RR, and RL imbalances

		-- be able to discuss the complexity of BST and
		     AVL tree ADT operations, for example, INSERT 
	    	     and DELETE for LL, LR, RR, and RL imbalances

		-- be able to discuss, in one or two *clear*
		     sentences, the advantages and disadvantages
		     of BSTs and AVL trees

		-- given a sequence of numbers, be able to build
		     a binary tree, heap, or AVL tree from those
		     numbers

        5) Spanning trees and minimum spanning trees (MSTs)

		-- know the definition of a graph, subgraph, and
		     spanning tree

		-- be able to construct a connected subgraph of a
		     graph, and to manually construct a spanning tree of
		     a graph, given the graph's vertex and edge sets

		-- know the differences (functionality and complexity)
		     between Prim's and Kruskal's algorithms for
		     constructing an MST

		-- be able to construct a complexity budget for 
		     building an MST using either Prim's or Kruskal's
		     algorithm

		-- be able to construct an MST using either Prim's 
		     or Kruskal's algorithm

	6) Shortest-path problems (SPPs)

		-- know the definition of a path and a shortest path
		     in a graph

		-- be able to manually construct a shortest path of
		     a small graph, given the graph's vertex and edge sets

		-- know the differences (functionality and complexity)
		     between Dijkstra's and Floyd's algorithms for
		     solving an instance of the SPP

		-- be able to construct a complexity budget for 
		     solving an instance of the SPP using either Dijkstra's 
		     or Floyd's algorithm

		-- be able to find a min-cost path using either Dijkstra's 
		     or Floyd's algorithm, given a graph's vertex and edge 
		     sets, or a diagram of the graph

	We covered most of these topics in the Review in class today.

    Best wishes for good luck on the exam!!!  Start studying NOW.

- EOF -