CIT594 Final Exam Spring 2009 Name_________________________________________

Please keep all your answers short and to the point. Do not provide extra information that was not asked for.

1. (6 points) Distinguish between a compiler and an interpreter.

An interpreter reads a program and executes it (does what it says to do).
A compiler reads a program and translates it into another language.

2. (6 points) Precisely define the following terms as they apply to a binary tree.

1. depth
The maximum of the distances from the root to each leaf.

2. balanced
If d is the depth of the binary tree, all leaves are at depth d or depth d-1.

3. left-justified
If d is the depth of the binary tree, all leaves at depth d are as far left as possible.

3. (8 points) What are Dave's four rules for doing recursion?

Do the base case(s) first.

Recur only with a simpler case.

Do not both use and modify global variables.

Don't look down.

4. (5 points) Suppose a class `IntList` has public instance variables `int value` and `IntList next`, with the obvious meanings. Write a recursive method `int size` to count the number of values in the IntList `list`.

int size(IntList list) {
if (list == null) return 0;
else return 1 + size(list.next);
}

5. (5 points) Write the iterative version of the `int size()` method described in the previous question.

int size(IntList list) {
int count = 0;
while (list != null) {
count++;
list = list.next;
}
return count;
}

6. (2 points) If we define `int myArray[][] = new int[3][8]`, what value is in `myArray[1]`?

An int array containing 8 zeros.

7. (6 points) Tell how long each of the following statements take (Big-O notation), and briefly defend your answer.

1. `for (int i = 0; i < a.length; i++) a[i] = i * i;`

O(a.length), since we do one constant time operation for each element of a.

2. `for (int i = 0; i < 10000; i++) a[i] = i * i;`

O(1), since the number of iterations is fixed, and each pass through the loop does only constant-time operations.

8. (6 points) For each of the following sorting methods, describe the order of elements in the array when you are partway through sorting.

1. Insertion sort

All the elements to the left of some index are sorted with respect to one another.
Precisely: For increasing k, i < j & j < k implies a[i] <= a[j].

2. Selection sort

All the elements to the left of some index are in their final position.
Precisely: For increasing k, i < k & i < j implies a[i] <= a[j].

9. (4 points) The word "heap" is used in computer science for two different things. Give both definitions.

A heap is an area of memory from which the programmer can allocate storage.

A heap is a binary tree in which every node has the heap property.
(A node has the heap property if the value in the node is at least as large as the value in any child of that node.

10. (3 points) The Sun-supplied `Stack` class extends the `Vector` class. Why does your instructor think this is a bad design?

Because a Vector has many operations which should not be available to a Stack.

11. (6 points) In what order are the nodes of this binary tree traversed
 in preorder? A B C D in inorder? B D C A in postorder? D C B A

12. (8 points) Here are two methods for finding the maximum value in an array of integers. Each is correct. Which one is faster? By how much? Defend your answer.

 ```int max1(int[] nums, int last) { if (last == 0) return nums[0]; else { if (nums[last] > max1(nums, last - 1)) { return nums[last]; } else { return max1(nums, last - 1); } } }``` ```int max2(int[] nums, int last) { if (last == 0) return nums[0]; else { int temp = max2(nums, last - 1); if (nums[last] > temp) { return nums[last]; } else { return temp; } } }```

The second one is much faster.

The first takes exponential time, O(2nums.length), because every call may result in two recursive calls.

The second makes one call for each element of the array, so is only linear time, O(nums.length).

13. (8 points) Given the following letters and their frequencies:

A, 5%;    B, 12%;     C, 31%;    D, 34%;     E, 17%;    F, 1%

1. Draw the corresponding Huffman tree.

 A + F = 6 (v) B + v = 18 (w) w + E = 35 (x) C + D = 65 (y) x + y = 100 (z)
2. Tell the binary encoding for each letter.

 A = 0010 B = 000 C = 10 D = 11 E = 01 F = 0011

14. (8 points) In the A* algorithm formula `f(N) = g(N) + h(N)`, what do each of the following stand for?

1. `N`

A particular node in the search tree.
2. `g`

The (known) cost of getting from the start node to node N.
3. `h`

The estimated cost of getting from node N to a goal node.
4. `f`

The estimated cost of getting from the start node to a goal node via a path passing through node N.

15. (4 points) When searching a graph, what are the two techniques for avoiding getting caught going around and around in a cycle?

Mark each node as you get to it, so you know not to explore from there again.

Keep a set of visited nodes, so you know not to explore from them again.

16. (3 points) Define dynamic programming algorithm.

An algorithm which "remembers" previous results and uses them when computing new results.

17. (4 points) Draw a plausible parse tree for the Java statement
`    absX = x > 0 ? x : -x;`

18. (2 points) In the `Preferences` method `get(key, xxx)`, what is the second parameter used for?

A default value, to return in case the key is not found.

19. (4 points) Alpha-beta searching is based on what two assumptions?

The farther ahead you look, the better you can choose a move.

Your opponent has the same heuristic (means of evaluating each node) as you have.

(One point of credit: The earlier you can find a cutoff, the more searching you will save.)

20. (2 points) When should you refactor code?

Whenever you see a way to improve it.
-or-
When it is necessary in order to add new functionality.