Exam III Review Sheet

Here are the list of topics that you need to study for the exam.  Use the visualization web site to practice these algorithms.

  1. The Day/Stout/Warren (DSW) Algorithm.  Know the general algorithm and the type of rotation that this performed.  What type of tree is returned etc. Complexity.
  2. AVL trees.  Know the rotation types.  Be able to perform a rotation on a diagram. Be able to give code that will perform this rotation.  Complexity of operations on the tree.  Be able to give the balance factor for each node for a given tree, show where the rotation is applied etc.  Be able to insert a new item in the tree and re-balance.
  3. Heap.  Be able to define a heap (max or min) and perform an insert and an extract on the heap array by hand.  Simple swap up and down code.  Complexity of these operations.   Speed up methods ( bit shifting etc) Also be able to use the stl:priority_queue (empty(), size(), front(), push_back(), and pop_back()),  Also know how heap_sort works and its complexity.
  4. Know the quick sort algorithm(pseudo code). as well as the associated partition algorithm.  Complexity(worst,ave,best).  Recurrence relation and its solution.
  5. Know the counting sort and the radix sort and when you can use these.  In the counting sort what are you counting?  Complexity.
  6. Know the two graph storage structures(adj list and adj matrix) and their effect on the algorithms.
  7. BFS and DFS.  Be able to give pseudo code for these.  Complexty. What do these return?  What are the BFS and DFS trees?  Be able to perform these operations by hand on a given graph.  Make sure you understand the d[] and f[] arrays for the DFS and the d[] array for BFS and what they mean.
  8. Know the different type of edges that result when performing a DFS.  How do you know if a graph has a cycle?
  9. MST(Prim’s) Algorithm and complexity.  What is returned? Be able to define a MST.
  10. SSSP (Dijkstra’s) Algorithm and complexity. What is returned?

Comments are closed.