Information About the First Test

The first test will be given in class on Wednesday, October 5. The test will cover everything that we have done from the beginning of the term through class on Friday, September 30. This includes exceptions and the try..catch..finally statement; the analysis of algorithms; recursion; linked lists; the concept of abstract data types; stacks and queues; binary trees, binary sort trees, and expression trees. The reading for this material is Sections 8.3, 8.5, 9.1, 9.2, 9.3, and 9.4. We have also talked about a few things that are not in the textbook, notably Merge Sort, doubly-linked lists, and turtle graphics.

You can expect a variety of questions on the test. There will be some definitions and essay-type questions. There could be one or two questions that ask you to analyze the run time of some code. Some questions will ask you to write code segments or methods or possibly even complete classes. There might also be some questions that ask you to read some code and figure out what it does.

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

exceptions exceptions are represented in Java by objects in subclasses ofThrowablehow exception handling compares to other ways of dealing with errors handling exceptions: the try..catch statement the finally clause in a try statement, and why it might be used throwing exceptions: throw new ExceptionClass(errorMessage); checked exceptions and mandatory exception handling questions of efficiency of a program run-time analysis of algorithms worst-case analysis, best-case analysis, and average case analysis log_{2}(n) and how it arises in analysis of some algorithms "Big Theta" and "Big Oh" notation ( Θ(f(n)) and O(f(n)) ) comparing Θ(n) to Θ(log(n)), or Θ(n^{2}) to Θ(n*log(n)) disregarding "constant multiples" and "lower order terms" Linear Search versus Binary Search Selection Sort and Insertion Sort have run time Θ(n^{2}) Merge Sort (including how to do it by hand) Merge Sort has run time Θ(n*log(n)) recursion recursive subroutines direct recursion and indirect recursion base case of a recursion, and why base cases are essential infinite recursion, and why "marking" locations as already visited is important maze-solving and similar recursions recursive geometric objects such as the Koch Curve and Sierpinski Triangle using turtle graphics and recursion to draw pictures of recursive geometric objects the QuickSort recursive algorithm the idea of QuickSortStep (but not the detailed code) the general idea of why QuickSort has average case run time Θ(n*log(n)) the worst case run time of QuickSort linked data structures understanding names such as "employee.boss.name" and "node.next.next" simple linked lists the head of a list; why you always need to keep a pointer to the head traversing a linked list; using a "runner" to move down the list basic linked list processing, such as searching, or adding up items in a list the meaning of "while (runner != null)" and "runner = runner.next" adding a node to the head of a list why working at the head of a list is often a special case inserting and deleting nodes in a list using a "tail" pointer in a list; adding a node a the end of a list doubly-linked lists; next and prev pointers using a "sentinel node" at the head of a list Abstract Data Types (ADTs) an ADT can have more than one implementation the "Stack" ADT stack operations: push, pop, isEmpty how to implement a stack as an array how to implement a stack as a linked list the "Queue" ADT queue operations: enqueue, dequeue, isEmpty how to implement a queue as a linked list with tail pointer activation records and how they are used to implement subroutine calls how recursion is implemented using the stack of activation records using a stack or a queue instead of recursion binary trees left and right subtrees implementing binary trees using nodes with left and right pointers root node, leaf node, parent node, child node recursive processing of trees inorder, preorder, and postorder traversals of a binary tree binary sort tree (BST) inserting items into a binary sort tree searching for an item in a binary sort tree balanced binary tree inserting/searching in a balanced binary sort tree has run time Θ(log(n)) expression trees to represent binary expressions finding the value represented by an expression tree postfix expressions how to use a stack to evaluate a postfix expression

Here are a couple of sample essay-style questions from old exams, just to give you an idea of what kinds of questions might be asked:

**1.** What is a Binary Sort Tree? What property does a Binary Sort
Tree have that a plain binary tree does not have?

**2.** When your program encounters an error at run time, why is it a
good idea to throw an exception rather than, for example, print an error message or
terminate the program?

Here are a few practice questions about pointers and linked data structures. These questions use the following classes and variables:

class ListNode { class TreeNode { String item; int item; ListNode next; TreeNode left, right; } } ListNode head; TreeNode root;

**1.**
Draw the data structure that is created by the following code segment:

ListNode n1, n2; n1 = new ListNode(); n1.item = "Johnny"; n1.next = new ListNode(); n1.item = "Jane"; n2 = new ListNode(); n2.item = "Jill"; n2.next = n1; n2.next.next.next = n1;

**2.**
Write a code segment that will find and print the **longest** string in
the list that *head* points to. (If there are several strings with the same maximal length,
output the one that comes first in the list.)

**3.**
Write a method with one parameter of type *ListNode* and a return type
of *boolean*. The method should test whether the items in the list are
*already* sorted into increasing order.

**4.**
Write a recursive method with one parameter of type *TreeNode*
that finds the number of nodes in the tree in which the item is equal to 17.

**5.**
The *height* of a binary tree is defined to be the number of nodes on the
longest path from the root to any leaf. The height of an empty tree
is zero. Figure out how to compute the height of a non-empty tree from the
heights of its left and right subtree, and write a recursive method, with
a parameter of type *TreeNode*, to find the height of a binary tree.

**6.**
Draw a binary tree containing at least 12 items, and list the
items in the order that they would be visited by a pre-order, by
an in-order, and by a post-order traversal.

Here are two practice problems about recursion.

1. Consider this recursive method: | 2. Consider the following recursive | using turtle graphics: void guess(int level) { | if (level == 0) { | void draw(double size, int level) { System.out.print("*"); | if (level == 0) { } | turtle.forward(size); else { | } else { System.out.print("("); | turtle.forward(size/2); guess(level - 1); | turtle.turn(90); System.out.print(("|"); | draw( size/2, level-1 ); guess(level - 1); | turtle.turn(180); System.out.print(")"); | turtle.forward(size/2); } | draw( size/2, level-1 ); } | turtle.back(size/2); | turtle.turn(90); a) Show the output from guess(1) | } b) Show the output from guess(2) | } c) Show the output from guess(3) | | a) Show the drawing from draw(10, 0) | b) Show the drawing from draw(10, 1) | c) Show the drawing from draw(10, 2) | d) Show the drawing from draw(10, 3)

And here are some practice problems on analysis of algorithms.

Consider the following subroutines. Each subroutine processes an array, A, of integers. In each case, discuss the run time of the code as a function of the array size, N. (The subroutines are not necessarily meant to do anything useful!)

1) static void One(int[] A) { int sum = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) sum = sum + A[i]*A[j]; } System.out.println(sum); } 2) static boolean Two(int[] A) { int N = A.length; for (int i = 1; i < N; i++) { for (int j = 0; j < i; j++) { if (A[i] == A[j]) return false; } } return true; } 3) static int Three(int[] A) { int N = A.length; int s = 0; int i = 1; while (i < N) { s = s + A[i]; i = 2 * i; } return s; }