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) c.iterator() 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 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