CPSC 225, Spring 2009
Information About the First Test

The first test will be given in class on Friday, February 20. The test will cover everything that we have done from the beginning of the term through class on Monday, February 16. This includes exceptions and the try..catch..finally statement; the analysis of algorithms; recursion; linked lists; the concept of abstract data types; and -- possibly -- stacks. The reading for this material is Sections 8.3, 8.6, 9.1, 9.2, and the beginning of 9.3 in the textbook. We also talked about a few things that were not in this reading: Javadoc, interfaces, 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:

    Javadoc comments
    using an interface to express common features of several classes
    implementing an interface
    how exception handling compared to other ways of dealing with errors
    the basic exception classes, Exception and RuntimeException
    common exceptions such as NullPointerException
    checked exceptions and mandatory exception handling
    specific checked exceptions such as IOException and FileNotFoundException
    throwing an exception
    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
    "big Theta" and "big Oh" notation ( Θ(f(n)) and O(f(n)) )
    big Theta and big Oh "ignore constant multiples and lower order terms"
    log2(n) and how it arises in analysis of some algorithms
    comparing Θ(n) to Θ(log(n)), or Θ(n2) to Θ(n*log(n))
    selection sort and insertion sort have run time &Theta(n2)
    QuickSort has average case run time &Theta(n*log(n))
    stable sorting algorithms, and why stability is desirable

    recursion; recursive methods; direct recursion and indirect recursion
    base case of a recursion
    maze-solving and similar recursions (including MineSweeper)
    infinite recursion, and why "marking" locations as already visited is important
    the QuickSort recursive algorithm
    the basic 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
    linked data structures
    understand names such as "employee.boss.name" and "node.next.next"
    simple linked lists
    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
    the meaning of "while (runner != null)" and "runner = runner.next"
    adding a node to the head of a list
    why working at the head of a list is often a special case
    inserting a node into the middle of the list
    deleting a node from a list
    using a "prev" pointer in addition to "runner", such as when deleting a node

    doubly-linked lists
    Abstract Data Types (ADTs)
    alternative implementations of ADTs
    relation of ADTs to interfaces and abstract classes
    the "Stack" ADT and how it can be implemented as an array or as a linked list
    the push and pop operations on a stack