##
CPSC 289 Sec 502: Review for Exam 1

Spring 2007

**You may bring one 8.5 by 11 inch sheet of paper to the exam with
your notes on it. You may write on both sides of it.
You must turn your review sheet in with your exam.**
Review the following:

- Lectures through Feb 20

- Readings:
pp. xx - xxii;
Ch 1;
Ch 2;
Ch 3 sec 1-3 (skip material on greedy algorithms, halting problem,
tractability and NP-completeness).

- Quizzes 1-4 and their solutions (given in class)

- Homework assignments 1-3 and their solutions
(given in class)

The format of the exam will be some short answers (like the quizzes) and some
"work-out" problems (like the homeworks).

The textbook has an excellent review of key terms and results
at the end of each chapter. I recommend you know the terms and results
and work the questions.

- Ch 1: pp. 104-106
- Ch 2: pp. 163-164
- Ch 3: pp. 257-258 (key terms through average-case time complexity;
key results through the one about the complexity of a polynomial;
review questions through #8)