Midterm 1 Study Guide

This midterm covers chapters 1 through 4. Here is a list of the main ideas:

1. What constitutes an algorithm?
2. What questions might the analysis of an algorithm entail?
3. Be able to explain what stable and in-place sorting is, and which of the sorting algorithms we have seen have those properties.
4. Describe the two different ways of representing graphs.
5. Be able to compare the following functions in terms of their order of growth: \(\log_2n\), \(\log_{10}n\), \(n\), \(n^2\), \(2n\), \(n\log n\), \(1000n\), \(2^n\), \(10^n\), \(n!\)
6. Explain the main ideas behind \(O\), \(\Theta\) and \(\Omega\).
7. Be able to determine the time efficiency for non-recursive algorithms by setting up a sum formula and then computing it.
8. Be able to determine the time efficiency for recursive algorithms by setting up a recursive relation and then solving it.
9. For each of the following algorithms be able to write pseudocode, identify the basic operation and input size, determine best-case and worst-case complexity, and completely carry out a small-size example:
   • Counting sort
   • Selection sort
   • Bubble sort
   • Insertion sort
   • Brute-force traveling salesman
   • Depth-first search
   • Breadth-first search
   • Topological sort
   • Binary search