## CPSC 225, Spring 2010 Information About the First Test

The first test will be given in class on Wednesday, February 24. The test will cover everything that we have done from the beginning of the term through class on Friday, February 19. This includes exceptions and the try..catch..finally statement; the analysis of algorithms; recursion; linked lists; the concept of abstract data types; stacks and queues; binary trees, binary sort trees, and expression trees. The reading for this material is Sections 8.3, 8.6, 9.1, 9.2, 9.3, and 9.4. We have talked about a few things that are not in the textbook, notably Merge Sort and doubly-linked lists.

You can expect a variety of questions on the test. There will be some definitions and essay-type questions. There will be one or two questions that ask you to analyze the run time of some code. Some questions will ask you to write code segments or methods or possibly even complete classes. There might also be some questions that ask you to read some code and figure out what it does.

Here are some terms and ideas that you should be familiar with:

```
exceptions
how exception handling compares to other ways of dealing with errors
handling exceptions: the try..catch statement
the finally clause in a try statement, and why it might be used

questions of efficiency of a program
run-time analysis of algorithms
worst-case analysis and average case analysis
log2(n) and how it arises in analysis of some algorithms
"Big Theta" and "Big Oh" notation ( Θ(f(n)) and O(f(n)) )
comparing Θ(n) to Θ(log(n)), or Θ(n2) to Θ(n*log(n))
disregarding "constant multiples" and "lower order terms"
Linear Search and Binary Search
Selection Sort and Insertion Sort have run time Θ(n2)
Merge Sort (including how to do it by hand)
Merge Sort has run time Θ(n*log(n))
Exponential run time, such as Θ(2n)
a program with exponential run time is infeasible except for very small inputs

recursion
recursive methods
direct recursion and indirect recursion
recursive definition of the factorial function
base case of a recursion
maze-solving and similar recursions
infinite recursion, and why "marking" locations as already visited is important
recursive geometric objects such as the Koch Curve and Sierpinski Triangle
the QuickSort recursive algorithm
the idea of QuickSortStep (but not the detailed code)
the general idea of why QuickSort has average case run time Θ(n*log(n))
the worst case run time of QuickSort
the recursive nature of grammar rules for Java and for English

activation records and how they are used to implement subroutine calls
How recursion is implemented using the stack of activation records

understanding names such as "employee.boss.name" and "node.next.next"
the head of a list; why you always need to keep a pointer to the head
traversing a linked list; using a "runner" to move down the list
basic linked list processing, such as searching, or adding up items in a list
the meaning of "while (runner != null)" and "runner = runner.next"
why working at the head of a list is often a special case
inserting and deleting nodes in a list
using a "tail" pointer in a list; adding a node a the end of a list

relation of ADTs to interfaces and abstract classes
queue operations: enqueue, dequeue, isEmpty
how to implement a queue as a linked list with tail pointer
stack operations: push, pop, isEmpty
how to implement a stack as an array
how to implement a stack as a linked list
postfix expressions
how to use a stack to evaluate a postfix expression

binary trees
recursive traversal of a tree
inorder, preorder, and postorder traversals
binary sort tree
inserting items into a binary sort tree
searching for an item in a binary sort tree
balanced binary tree
inserting/searching in a balanced binary sort tree has run time Θ(log(n))

expression trees to represent binary expressions
finding the value represented by a an expression tree
```