Review Sheet for Final Exam

It is suggested that you review your previous exams and projets. In addition, use the topics below as a GUIDE in studying for the exam.

• Sorting:
  • How each sort (bubble, selection, merge, quicksort) works conceptually
  • The Big-Oh for each of the four sorts
  • How to code the bubble and selection sorts
  • How to code the recursive functions for the merge and quick sorts
  • Why one might select one sort over another
• Asymptotic Analysis
  • The concept of Big-Oh
  • The most common functions encountered in Big-Oh analysis, from slowest to most rapid growth
  • The effect of constants and factors in Big-Oh functions
  • How to choose which algorithm to use based on its Big-Oh
• Trees
  • General concept of a tree and tree terminology
  • Concept of a binary tree and a binary search tree
  • The concepts and code for preorder, inorder, and postorder tree traversals
  • How to write the code for searching for a node, inserting a node, and deleting a node from a binary search tree
• Stacks and Queues
  • The concepts of stacks, queues, and lists
  • Ways in which stacks, queues, and lists can be implemented
  • How to write class definitions for stacks and queues
  • How to write the code for methods that would commonly be included in stack and queue classes (e.g., clear, push, pop, check for empty, enqueue, dequeue)

• node, path/edge, root, internal node, leaf, subtree, parent, child, sibling, ancester, descendant, depth of a node, depth of a tree, LIFO, FIFO, push, pop, head, tail, enqueue, dequeue