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