1. Suppose statement2 may throw an exception in the following code:

try{

statement1;

statement2;

statement3;

}

catch(Exception ex1){

System.exit(0);

}

finally{

statement4;

}

statement5;

Answer the following questions:

a.  If no exception occurs, will statement3, statement4 or statement5 be executed?

b.  If    an    exception    of    type Exception is   thrown,   will statement3, statement4 or statement5 be executed?

c.  If an exception that is not of type Exception is thrown, will statement3, statement4 or statement5 be executed?

2. Evaluate the following postfix expression using a stack. Show all the steps. 20 6 * 6 5 * 31 + 1 - / 9 - *

3. Determine the exact number of iterations executed by the following code and the time complexity of the code using Big-O notation? Show your work.

for (int i = n; i > 0; --i)

for (int j = n/20; j > 0; j /= 2)

for(int k = 1; k < n; k *= 3)

int product = i * k + j * (k-2) + k;

4. Assume the following list of values {18, 9, 32, 22, 75, 83, 3} to be sorted using Merge sort. Show all the steps to sort the list.

5. Assume the following list of values {16, 80, 22, 55, 64, 95, 25} to be         sorted using quicksort. Use a pivot as the first element of the list. Show the steps to sort the list.

6. The nodes in a binary tree in pre-order and in-order sequences are as follows: Pre-order: A B C D E F G H I

In-order: D C B A F E G I H

Draw the binary tree and write the post-order traversal of the tree.

7. Remove the node with value 9 from the following binary search tree. Write the in-order traversal of the BST after the deletion.

8. Redraw the following max heap after adding a node with value 92 and rebuilding the heap. Write the list of the nodes as stored in the heap’s array list.

9. Assume a hash table has the initial size 4 and its load factor is 0.5, show the hash table after inserting the keys 34, 29, 53, 44, 120, 39, and 45, using linear probing.

10. Assume a hash table has the initial size 4 and its load factor is 0.9, show the hash table after inserting the keys 34, 29, 53, 44, 120, 39, and 45, using separate chaining.

1. Write a recursive method to compute the following series: M(n)   =   1   + + +   .  .  .    +

Write a test program that displays M(n) for n = 1, 2, . . ., 10

2. Write a recursive method to find occurrences of a character c in a string s.

3. Write a generic recursive method removeDuplicates that removes duplicates from an ArrayList. The method returns a new ArrayList that contains the    elements from the original list with no duplicates.

4. Write a generic method max that finds the maximum value in an ArrayList.

5. Add the methods addAll(ArrayList), removeAll(ArrayList), retainAll(ayList<E>), and toArray() to the classes ArrayList and LinkedList, and determine their time complexity.

[1, 2, 3].addAll([3, 4]) results in the first list equal to [1, 2, 3, 3, 4]

[1, 2, 3].removeAll([3, 4]) results in the first list equal to [1, 2] [1, 2, 3].retainAll([3, 4]) results in the first list equal to [3] [1, 2, 3].toArray() returns the array {1, 2, 3}

6. Add the methods indexOf(E value), lastIndexOf(E value)a to the class LinkedList and determine their time complexity.

7. Add a method reverse() to the class LinkedList to print the elements of the list in reverse order (from the last element to the first element). Determine the time            complexity of the method.

8. Write a test program that stores 5 million integers in a linked list and test the time to traverse the list using an iterator vs. using the method get(index).

9. The quicksort algorithm covered in class selects the first element in the list as the pivot. Revise it by selecting the median among the first, middle, and the last elements in the list. Compare the two quicksort algorithms on three arrays. The first array contains random integers, the second is sorted and the third is in reverse order.

10. Add the method sort() to the class LinkedList. The method should sort the   elements of the list using bubble sort. Determine the time complexity of the method.

11.The heap data structure covered in class is a maxheap where every node is greater than its children. Modify the class to implement a min-heap where every node is less than   its children. Use the min-heap to implement the priority queue data structure.               Determine the time complexity of all the methods in the heap-based priority queue         class. Write a program that offers one million integers in the priority queue and polls        them from the queue. Display the average number of iterations of the methods offer() and poll().

12. Implement the clone and equals methods for the BST class. Two BST trees are    equal if they contain the same nodes. The clone method returns a deep copy of the tree. Determine the time complexity of the two methods.

13. Add the following methods to the BST class.

// Iterative preorder traversal using a stack

// No recursion

public void iterativePreorder()

// Recursive search method

public boolean recursiveSearch(E item)

14.The class HashMap seen in class uses a LinkedList to store collisions. Replace LinkedList with BST. The generic type K must be a subtype of Comparable.

Redefine HashMap and test it using the same test program from ALA 10.

15. Add the following methods to the class HashMap:

a. public ArrayList<K> keys(): returns an array list with all the keys in the hash table.

b. public ArrayList<V> values(): returns an array list with all the values in the hash table.