Exam 1 Review Information

Exam 1 will be a take-home exam. You may use the textbook, your own notes and problem solutions, the materials posted on the course website, and external websites directly linked from the course website. You may not use other resources, including web resources linked from things the course website links to. You may not get notes or other materials from or share notes or other materials with other students once the exam has been handed out, even if those notes/materials aren't directly related to the exam.

The only person you may discuss the exam with is me - I will answer clarification questions, but the exam is meant to be a demonstration of what you can do so I will not provide help on how to solve the problems.

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

Kinds of questions include (but are not limited to) the kinds of questions that have been on the homeworks (homeworks 1-2) and warmups.