Topics for Midterm Exam

The midterm is open book, open notes, calculators allowed, but no computers.  Schedule the exam through distance education services!

• Math Basics
  • Big-O vs Theta vs Omega and Little-O notations
  • You may need to solve summations (will be one you have seen before)
    
• Solving recurrence relations
  • Substitution  - not on exam
  • Iteration
  • Master Method
  • Using recursion trees
    
• Heaps
  • How heapify procedure works
  • Mapping an array to the tree, vice versa
  • Building a heap, runtime
  • How to use a heap as a priority queue, runtime properties
    
• Selection Problem
  • How to partition an array in linear time, no additional space
    • Good, bad cases for partitioning and impact on the algorithm runtime
    • Different methods for selecting the partition element
  • Using the partition routine to select the ith largest element in expected linear time
    
• Sorting Algorithms
  • Know how to identify, execute, and the runtime properties of
    • Mergesort
    • Heapsort
    • Quicksort
    • Insertion Sort
    • Selection Sort
    • Radix Sort
    • Bucket Sort
    • Count Sort
    • Postman Sort
  • Reason for the Omega(nlgn) comparison-based sorting algorithms
  • Why some sorting routines can run faster than O(nlgn)
• Algorithm analysis
  • Design an algorithm to solve a problem in O(f(n)) time
  • Given an algorithm or pseudocode, determine the Big-O or Theta runtime