Final Study Guide

• Look over all previous study guides. Anything on a previous study guide is fair game and my not be listed below The final will include everything on the midterm study guide but I won't list those things again here.
• Look over previous homework solution and test/quiz solutions
• Final will consist of:
  • Multiple Choice
  • True/False
  • Short definitions. The following is a list of definitions you should know. The list may not be complete.
  • Tree - including all terms (parent, child, sibling, ancestors, descendents, height, depth, edges, leaves, internal/external nodes, etc)
  • Binary Search Tree
  • 2-node
  • 3-node
  • 2-3 Tree
  • Red-black tree - including black height
  • Heap
  • Priority Queue
  • Hash Table
  • Direct address hashing
  • Indirect address hashing
  • Primary and secondary clustering
  • Linear and quadratic probing and double hashing
  • Load Factor
  • Short answer
  • Work through an algorithm
  • Be able to show inserting and deleting from a BST, 2-3, heaps, lists, queues, and stacks.
  • Red-Black tree rotations
  • Trace through sorting algorithms: insertion sort, selection sort, bubble sort, quick sort, merge sort, radix sort, tree sort and/or heap sort
  • Short coding problems. By now you should not have to study how to write the code for operations. As long as you understand the ADT and the operation, you should be able to code this up
  • Linked lists - singly or doubly linked, circular or not, sentinels or none
  • Stack and queue operations
  • BST operations - anything is fair game except insert and remove
  • Heap operations - for both an array or a tree based heap
  • Hash operations - Just finding location in table because I would allow you to use STL
  • 2-3 Tree Operations - anything except insert and remove
  • Rotate about a node in a red-black tree (You may want to try coding this up before the final).
• Runtimes for operations on ADTs and all sorting algorithms we have discussed
• Given a situation, be able to determine the best ADT and support your answer
• Trace through hash table functionality given various collision resolution methods
• This is not an inclusive list but it touches most of the main points
• Make sure you have a good understanding of the ADTs studied. If you simply memorize information you will not do well on the open ended questions.
• You will have many more open ended questions and algorithm design questions on the final than on the other tests.
• For the sorting algorthms, make sure you know how the order of the items in the array can effect the running time of the algorthm. For example, for X sort, what characteristics or ordering of the input array will cause the array to run the fastest or the slowest
• Templates - you will be writing template classes and/or functions. Yes, syntax wil count for this
• Make sure you know the formulas for linear and quadratic probing and double hashing. For example, the formula for linear probing is hval(item) = (HF(item) + i)%size
• Know what makes a good hash function and what makes a bad hash function. Good and bad hash table sizes
• Sorting stability - giving a sorting algorithm, determine if it is stable or not