Suppose that you have a method

int partition(int [] arr, int lower, int uppper)

which when called on a segment of an array `arr` whose elements are in positions
`lower` through `upper`, rearranges the elements of the array in that segment
and returns an integer `p` such that all elements in the segment `arr[lower...p-1]`
are less than `arr[p]`, and all elements in the segment `arr[p+1..upper]` are greater or equal to
`arr[p]`.

Show how to write a recursive method that uses the `partition` method based on the Quicksort method.

void Quicksort(int [] arr, int lower, int upper)

Write the `partition` method used in the Quicksort algorithm.

Explain the difference between *lists* and *sets*.

Define the concept of an *iterator* for a collection, and list, with
descriptions, the key methods in the `Iterator` interface.

Describe the two different approaches to implementing lists and point out the
tradeoffs in the two approaches. Name the two Java classes that are used to
implement the `List` interface.

Describe the two different approaches to implementing sets and point out
the tradeoffs in the two approaches. Name the two Java classes that are used to
implement the `Set` interface.

Explain the concept of a *map*, and explain how maps differ from
lists and sets. Give at least three methods that are in the Java `Map< K, V >`
interface.

Assume we have a class

class Node { int value; Node left; Node right; Node(int v, int left1, int right1) { value = v; left = left1; right = right1; } Node(int v) { this(v, null, null); } }

Write recursive methods for traversing a binary tree, where a reference to the root node of the binary tree is passed as parameter:

void preorder(Node t) { } void inorder(Node t) { } void postorder(Node t) { }

Write a method ` int treeSize(Node t)`
that returns the number of nodes in a binary tree `t`.

Write a method ` boolean contains(Node t, int value) `
that returns true if the given value is stored in one of the nodes of the tree rooted at
`t`, and false otherwise.

Write a method ` int numberOfLeaves(Node t)`
that returns the number of leaves in the binary tree rooted at `t`.

Define the concept of a binary search tree.

Write a method ` Node add(Node t, int value)`
that adds a value to the binary search tree rooted at `t` and returns
a reference to the root of the resulting binary search tree.