CPSC 225, Spring 2009
Information About the Second Test

The second test will be given in class on Friday, April 3. The test is not cumulative (except to the extent that newer material depends on old material). It will cover everything that we have done since the first test. The previous test covered up to the first part of Section 9.3. For this test, the reading includes Section 9.3.3 (postfix expressions), 9.4 (binary trees), 9.5 (BNF and parsing), 10.1 (generic programming and the JCF), and selections from 10.2 to 10.4 (Lists, Sets, Maps, and hash tables, but not list iterators, EnumSet, SubSets or SubMaps). You should also know something about Genetic Programming, the ideas behind it and how it works.

The format of the test will be similar to that of the first test, with both programming problems and essay-type questions.

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

    expression trees
    using an abstract ExpressionNode class to implement expression trees
    binary trees
    using recursion to process binary trees (base case: empty tree)
    traversing a binary tree
    preorder traversal, inorder traversal, and postorder traversal

    binary search tree (BST)
    searching for an item in a BST
    adding an item to a BST
    inorder traversal of a BST visits the nodes in sorted order
    run-time analysis of BST algorithms

    postfix expressions
    using a stack of numbers to evaluate a postfix expression
    how postfix expressions correspond to postorder traversals of expression trees

    generic programming
    what problem does generic programming solve?
    parameterized types
    the Java Collection Framework (JFC)
    the Collection<T>, List<T>, Set<T> and Map<K,V> interfaces
    differences between lists and sets
    important Collection methods:
        c.size()         c.isEmpty()           c.clear()
        c.add(item)      c.remove(item)        c.contains(item)

    iterators; using an iterator to traverse a Collection
    iterator methods:  iter.hasNext(),  iter.next(),  iter.remove()
    how iterators provide a common way to traverse many different data structures
    for-each loops ("for (Type item : collection)")
    LinkedList<T> and ArrayList<T>
    important extra List methods:  list.get(i),  list.set(i,item)
    efficiency comparison of LinkedList and ArrayList
    HashSets<T> and TreeSet<T>
    difference between "hash" and "tree" for sets and maps
    keys and values in a map
    map methods:   map.put(key,value)    map.get(key)
                   map.keySet()          map.values()
    using map.keySet() or map.values() to traverse a map
    the Comparable<T> interface 
         and what it has to to with TreeSet, TreeMap, and Collections.sort(list)
    how to write a class that implements the Comparable interface
    hash tables and hash codes; how the hash code of an object is used
    the hashCode() method
    basic ideas of genetic programming:  
        population, fitness, reproduction, 
        selection, mutation, crossover