Exam 1 Review Information

Exam 1 will be in class. Take care of any necessary business before class so that you do not need to leave the room during the exam.

The exam will cover analysis of algorithms. ADTs and data structures will not be on this exam. Specific topics include:

• analysis of algorithms

  • the meaning of input size
  • the meaning of growth rate
  • major classes of growth rates (1, log n, n, n log n, n², 2ⁿ, n!), how they relate to each other, and what kinds of tasks give rise to each
  • the meaning of big-Oh, big-Theta, and big-Omega
  • determining the big-Oh/big-Theta/big-Omega of a function, sum, or recurrence relation
  • determining the big-Oh/big-Theta/big-Omega of an algorithm described by pseudocode
  • the meaning of best case, worst case, average/typical case

Expect questions similar to homework 1 — giving a big-Theta for (plain) functions, functions involving sums, and recurrence relations along with a justification, ordering functions by growth rate, and determining running times from code by writing sums for loops and recurrence relations for recursion. There may also be short answer questions about concepts and terms.

The sums and recurrence relation tables and the log/exponent rules sheet will be provided — you should know how to use them, but you do not need to memorize them. You should know the major classes of growth rates listed above and their order from slowest-growing to fastest-growing; that won't be provided.