CS220 Exam 1 Time: 5:15pm to 7:15pm March 5th, 2008 Place: Faner Hall 2127

Review materials:

All lecture slides from chapter 1 to chapter 7. Go over all questions on your homework 1 to 4.

1. Textbook (Addison Wesley) reading assignments: Summary and cautions of Chapter 1: Review of Java fundamentals from page 60 to 63. Textbook ( Pearson/Prentice Hall) reading assignments: Summary and tips of Chapter 1: Java Classes from page 30 to 32. Also, Summary and tips of Chapter 2: Creating Classes from other Classes from page 68 to 69.

2. Familiar with the access modifier scope of public, protected and private; go over problem 2 of Homework 1 helps with this concept.

3. Familiar with class inheritance, method overloading, overwriting, polymorphism, dynamic binding, and interface etc. Try to think of some examples in the real life. You should be able to design classes using these OOP conceptsgiven a real life application.

4. Textbook (Addison Wesley) reading assignments: Summary and cautions of Chapter 3:Recursion: the Mirrors from pages 162 to 163. Also go through the exercises from 1 to 12, 16 and 17from page 164 to 167.Textbook ( Pearson/Prentice Hall) reading assignments: Chapter 10 Recursion: on page 279, figure 10-5 shows an example of how to trace a recursive method by using a stack and activation record; Read pages from 279 to 283.

5. You should know how to write a recursive method and also know how to draw the stack to trace a certain recursive function by drawing all activation records. Understand the recursive version for binary search. How to divide an array into two halves; Chapter 10 summary and programming tips from page 297 to 298.

6. Know the details of howadd and remove methods work for ArrayList and LinkedList. You should be able to count the number of operations such as element shifting and reference updates for complexity analysis. Textbook (Addison Wesley) reading assignments: Summary and cautions of Chapter 5 Linked list from pages 278 to 280. You can ignore circular linked list and dummy head nodes contents which were not covered in our lectures. Textbook ( Pearson/Prentice Hall) reading assignments: Chapter 5, 6 and 7 gave some useful code examples for List. In addition, the lecture slides on all list related chapters are very helpful.

7. Textbook (Addison Wesley) reading assignments: Chapter 10 Algorithm Efficiency and Sorting: on page 468, the definition of the order of an algorithm, find constants k and n0. Our lecture slides used denotation of C and N for formal definition of Big O. On page 469 and 471, the order of magnitude of some common growth-rate functions is given. On page 472, some tips to follow in order to simplify the analysis of an algorithm given a growth-rate function. Textbook ( Pearson/Prentice Hall) reading assignments: on page 250, Figure 9-4, typical growth-rate functions are given in anascending order of magnitude. On page 252, the formal definition of Big O notation is described. Summary and tips on page 264. Also, you should go over the exercises from 1 to 7 to get a better understanding.