CSC383 Final Exam(s): Sample Review Problems

In Java, what is a checked exception?

In Java, how do you tell whether an Exception is checked or not?

In writing a class under what conditions should the code for a method use the 'throw' statement to throw an exception? In this case, which is preferable: a checked exception or unchecked?
Given the code for bubble sort, selection sort, insertion sort, or shell sort, be able to count the comparisons and/or swaps it makes for a given input array (of very small size).
What is the order of growth (1, log(N), N, N*log(N), N², N³, 2^N) where N is the size of the data structure for:
1. the method:
```
E get(int index)	  
	
```
  for ArrayList?
  
  for LinkedList?
2. the method:
```
E next()	      
	    
```
  for an ArrayList iterator?
  
  for a LinkedList iterator?
How do you 'declare' the generic parameters Key and Value for a binary search tree. (The declaration must indicate that the values of the actual type used for Key must implement Comparable.)
The Node class used for the generic class LinkedList<E> declares the data member to be of type E. Alternatively, in earlier versions of Java LinkedList was not generic; the data member of Node was Object.

What are 2 advantages of making a class such as LinkedList<E> be generic?

Hint: How does making the LinkedList class be generic make a difference for the add method? the getFirst() method?

For each of the following methods, what is the order of growth for an input array of size N?

 1, log(N), N, N*log(N), N², N³, 2^N

public void f(int[] a)
{
  int N = a.length;
  int s = 0;
  for(int i = 0; i < N; i++) {
	  s = s + a[i];
  }
}

public void f(int[] a)
{
  int N = a.length;
  int s = 0;
  for(int i = 0; i < N; i++) {
     for(int j = 0; j < N - 1; j++) {
	  s = s + a[i] + a[j];    
     }
  }
}

public void f(int[] a)
{
  int N = a.length;
  int s = 0;
  int k = N / 2;
  while(k > 0) {
    s = s + a[k];
    k = k / 2;	      
  }
}

A method, A, is executed for input sizes 1000, 2000, 4000, and 8000. The ratios for the running times when the size is doubled are given by the table below.

N T(2N)/T(N)

1000 1.5

2000 1.25

4000 1.10

Answer should be chosen from the list of usual growth functions:
```
 1, log(N), N, N*log(N), N², N³, 2^N	      
	    
```
Write the code for a 'remove(E x)' method for a doubly linked list that removes the first occurrence of x from the list and returns true or just returns false if x was not in the list.

Assume the list uses a head and a tail sentinel nodes; so even an empty list has these two nodes. The private members of the list are:
```
 private Node head;
 private Node tail;
 private int size;
 	    
```
where Node is an inner class:
```
private Node
{
  E data;
  Node prev;
  Node next;
  Node(E d) 
  {
    data = d;
    prev = null;
    next = null;
  }
}	      
	    
```
Write the code for the get method for a binary search tree implementation of a symbol table. It should return the value associated with the given key k or null if the key is not in the symbol table. You must use recursion! (So write a public get that calls a private recursive get method).
The private members of the class:
```
  Node root;	      
	    
```
where Node is an inner class
```
private class Node
{
  Key key;
  Value value;
  Node left, right;
  public Node(Key k, Value v) {
     key = k;
     value = v;
  }
}	      
	    
```
```
public Value get(Key k);

private Value get(Key k, Node t)
	    
```

N	T(2N)/T(N)
1000	1.5
2000	1.25
4000	1.10

A min heap of integers 6 integers is stored in an int array a at positions a[0] - a[5]. The root is a[0] at level 0, a[1] and a[2] are its children at level 1, etc.:

a[0]	3
a[1]	4
a[2]	8
a[3]	10
a[4]	9
a[5]	12
a[6]

Give 7 values a[0], a[1], ..., a[6] of this min heap after inserting the value 2.

Here is an binary search tree that was built using insertion without rebalancing.

Which of the following orders of insertion would correspond to this tree. There may be more than one answer!

A. 40 60 10 20 30 35 25 50
B. 40 20 30 35 60 50 10 25
C. 40 20 60 10 50 35 30 25
D. 40 60 50 20 30 35 25 10
E. 40 20 60 10 30 50 25 35
Is the binary search tree in the previous problem an AVL tree? If not, explain how it violates the condition.
Below is the diagram to rebalance an AVL tree when the AVL condition is violated at the node P because of an insertion to the right of P's right child.

Complete the method rotateLeft(Node p) below that (1) rebalances the tree at P, (2) adjusts the heights of nodes whose children have changed, and (3) returns a reference to the new root node R of the rebalanced subtree.
```
Node rotateLeft(Node p)
		{    
  
}
	        
```
where the Node structure is
```
private class Node
{
  public E data;
  public Node left;
  public Node right;
  public int height;

  public Node() { height = -1; }
  public Node(E d) { data = d; height = 0; }
	      }    
	        
```
You may use this private method to get the height of any tree Node:
```
private int height(Node p)
{
  if (p == null) {
     return -1;
  } else {
     return p.height;
  }
}
	          
```
A program is to be written that reads a text file with the complete works of Shakespeare and prints the distinct words in sorted order with their frequency of occurrence.

You decide to create a symbol table class with the usual symbol table operations:
- void put(String word, Integer count)
- Integer get(String word)
- Iterator iterator()
where the iterator will need to return the words in sorted order

To implement your class, you consider two choices:
- Binary Search Tree (not balanced)
- Balanced Binary Search Tree (e.g. AVL tree or RedBlack tree)
- Hash Table
For each choice explain how it would satisfy the each of the requirements.

For all the choices which would probably be faster? Explain your answer.
An index of the words in a collection of files is to be built. Then for each word, the index should allow finding all the files that contain that word.

Describe what data structure(s) you would use to build the index and give a brief description of how the index would be built and used.

A hash table using separate chaining has M chains numbered 0 - (M - 1). The hash function is

 int h(String x) 
 {
		int r = 0;      
   for(int i = 0; i < x.length(); i++) {
      r = r + x.charAt(i);
   }
   return r % M;  // assumes r does NOT become negative
 }

Using this hash function insert the following strings into the hash table below where the number of chains M = 8.

		cat dog ear foe are

If a chain has no strings, enter null.

Note: Assume

   "a".charAt(0) as an integer is 97
   "b".charAt(0) as an integer is 98
   etc.

Example: h("abc") is (97 + 98 + 99) % 8 = 6. So "abc" would be placed on chain 6.

Keys

Chain	Keys
0
1
2
3
4
5
6
7