**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

- How to partition an array in linear time, no additional space
- 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)

- Know how to identify, execute, and the runtime properties of
- 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