Outline

exam review

format similar to last exam
material from lecture notes (including in-class exercises), book, assignments, quizzes
for the book, all the material in Chapters 2.11, 3.1-3.4, 4-4.5, 5-5.5, 6-6.5 (gold and blue book), or Chapters 2.5, 5.1-5.4, 6-6.4, 7-7.5, 8-8.5 (green book),
must still be familiar with the material presented before exam 1, i.e. review the material (and maybe the exam)

Last-In First-Out data structures
two main implementations:
1. fixed-size (or variable-size) array: instance variables include array, index to top element
2. regular linked list: pointers to first and last node in queue
be able to implement push, pop, and size for any of these
main operations are constant time -- the only linear time operation is to increase the array size when pushing new data
with the array size doubling when needed, main operations require amortized constant time

First-In First-Out data structures
three main implementations:
1. regular linked list: pointers to first and last node in queue
2. circular linked list: pointer to last node in queue
3. fixed-size circular array: start index, end index. Arithmetic is done modulo the array size
be able to implement offer and poll for any of these
the main operations are constant time
double-ended queues have the operations of both stacks and queues

infix: operator is between operands, needs precedence, parentheses
prefix: operator is before operands
postfix: operator is before operands
implementing infix and prefix expressions requires an operand stack and an operator stack
implementing postfix expressions only requires an operand stack: whenever an operator is encountered, pop the operands off the stack, execute the operation, and push the result
remember that integer operations round down

truly random numbers require an unpredictable physical process
pseudo random numbers are unpredictable rather than random
for example, n' = (n * 45913 + 4137) % 65536 generates 16-bit random numbers: starting from 1, we get 50050, 61019, 36556, 22805, 46966, 23087, 18304, ...

searching in a sorted array
guaranteed logarithmic time
look in the middle,
select left or right half,
and repeat until found or guaranteed not found
recursive or iterative implementation: same performance, about same level of difficulty

recursion is natural when the data structure definition is recursive, e.g. with linked lists and trees
with recursion, always pay attention to the parameters to the method and to the return type of the method
as long as the base case(s) is/are reached eventually (and are correct), can assume that the recursive invocations will produce the correct results
this allows us to prove the correctness of recursive methods
recursion is very powerful when the problem is recursive, e.g. for tree traversal or towers of Hanoi (if you haven't already, try running and understanding Towers.java)
otherwise, recursion is simply a replacement for iteration

tree nomenclature: root, parent, child, subtree, ancestor, descendant, level, height, etc
each node has zero, one, or two children/subtrees
balanced trees: height of each subtree differs by no more than one, recursively
in a balanced tree, height is O(log nodes)
complete binary trees: all nodes on last level are at the left, all other leaves are on the previous level
perfect binary trees: 2^h-1 nodes for tree height h
most operations are O(height), but traversal is O(nodes)

binary trees where all values in left subtree are less than value in root, all values in right subtree are greater than value in root
finding value is easy
adding values (that are not already in the tree) is easy: find the correct leaf, and add to the left or right
removing values at a leaf is easy
removing values at an interior node requires replacing that node (value) by a value lower in the tree: for a tree with both subtrees, but the leftmost node of the right subtree or the rightmost node of the left subtree
implementation can be recursive or iterative
arbitrary classes that extend Comparable provide the compareTo method
x.compareTo(y) returns:
- a negative number if x < y
- zero if x.equals(y) (more or less)
- a positive number if x > y

depth-first:
- pre-order: node, left subtree, right subtree
- in-order: left subtree, node, right subtree
- post-order: left subtree, right subtree, node
in each case, this is a recursive definition
breadth-first: node, then its siblings, then their children in order
a tree structure might provide three or more different iterators
pre-order, post-order, and breadth-first work well even on trees that are not binary trees (inorder doesn't)
depth-first can be implemented either recursively, or using a stack
breadth-first can be implemented using a queue

constant time: stack and queue insertion and deletion, linked list insertion or deletion at the front, linked list inseration at the back if a tail pointer is kept
log time if doubling the size of the problem increases the time by one: binary search, balanced tree insertion, deletion, find
linear time: ordered linked list insertion or deletion, worst case tree insertion, deletion, or find

exam questions may expect you to be able to implement methods covered in class, such as from classes:
- ArrayStack.java
- LinkedStack.java
- BinarySearch.java (and the iterative equivalent)
- LinkedListRec.java
- BST.java
if any of these are asked, a description of the method would be given
you may have to come up with the method return type and parameters. This is especially important for recursive methods