CPSC 225, Spring 2011
Information About the First Test

The first test will be given in class on Wednesday, February 23. The test will cover everything that we have done from the beginning of the term through class on Friday, February 18. 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.5, 9.1, 9.2, 9.3, and 9.4. You are also responsible for what we've done in lab, including the basics of BufferedImage.

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
    throwing exceptions
    checked exceptions and mandatory exception handling
    
    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)
    Exponential run time, such as Θ(2n)
    a program with exponential run time is infeasible except for very small inputs
    
    recursion
    recursive methods
    recursive definition of the factorial function
    the recursive version of binary search
    base case of a recursion
    maze-solving, blob-counting, and similar recursions
    infinite recursion, and why "marking" locations as already visited is important
    recursive geometric objects such as the Sierpinski Carpet
    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
    
    activation records and how they are used to implement subroutine calls
    How recursion is implemented using the stack of activation records
    
    linked data structures
    understanding 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
    basic linked list processing, such as searching, or adding up items in a 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 and deleting nodes in a list
    using a "tail" pointer in a list; adding a node at the end of a list

    Abstract Data Types (ADTs)
    alternative implementations of ADTs
    relation of ADTs to interfaces and abstract classes
    the "Queue" ADT
    queue operations: enqueue, dequeue, isEmpty
    how to implement a queue as a linked list with tail pointer
    the "Stack" ADT
    stack operations: push, pop, isEmpty
    how to implement a stack as an array
    how to implement a stack as a linked list
    stacks are "LIFO"; queues are "FIFO"
    using a stack or queue as an alternative to recursion
    postfix expressions
    algorithm for using a stack to evaluate a postfix expression
    
    binary trees
    recursive processing of a binary tree
    recursive traversal of a tree
    inorder, preorder, and postorder traversals
    using a queue to process nodes in "breadth-first" order (aka "level order)
    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
    using different classes to represent different kinds of node in an expression tree
    
    Integrated Development Environment (IDE)
    Eclipse
    javadoc, JavaDoc style comments, and why they are used
    BufferedImage: image.getRGB, image.setRGB, g.drawImage(image,0,0,null)
    using anonymous inner classes as event listeners
    the idea of "resource files" in a program
    version control system
    CVS
    sharing, importing, committing, and updating projects in CVS

Here are a few practice questions about pointers and linked data structures. These questions use the following classes:

         class ListNode {               class TreeNode {
            String item;                    int item;
            ListNode next;                  TreeNode left, right;
         }                              }

1. Draw the data structure that is created by the following code segment:

          ListNode n1, n2;
          n1 = new ListNode();
          n1.item = "Joe";
          n1.next = new ListNode();
          n1.item = "Jane";
          n2 = new ListNode();
          n2.item = "Jill";
          n2.next = n1;
          n2.next.next.next=n1;

2. Write a code segment that will find and print the longest string in the list. (If there are several strings with the same maximal length, output the one that comes first in the list.)


3. Write a method with one parameter of type ListNode and a return type of boolean. The method should test whether the items in the list are already sorted into increasing order.


4. Write a recursive method with one parameter of type TreeNode that finds the sum of all the numbers in the tree.


5. The height of a binary tree is defined to be the number of nodes on the longest path from the root to any leaf. The height of an empty tree is zero. Figure out how to compute the height of a non-empty tree from the heights of its left and right subtree, and write a recursive method, with a parameter of type TreeNode, to find the height of a binary tree.


6. Draw a binary tree containing at least 12 items, and list the items in the order that they would be visited by a pre-order, by an in-order, and by a post-order traversal.