## CS 2401 Final Exam

Date: May 14, 2010.
Name: ____________________________________________

1-2. Write a recursive method for computing the power ab. Trace your code on the example of a = 3 and b = 3. Describe advantages and disadvantages of recursion vs. iteration in solving a problem, from the viewpoint of easiness to write, easiness to understand, and running time.

```

```
3. Write a method that, given a general square matrix A, returns an array consisting of all its diagonal elements. For example, for the matrix
```  1  2  3
4  5  6
7  8  9
```
your method should return an array consisting of the elements 1, 5, and 9. Trace your method on the example of this matrix.

```

```
4. Show, step by step, how a stack can be used to transform an expression 5 - (14 - 20) into the postfix form, and how a stack can be used to compute the value of the resulting postfix expression.

```

```
5. Show, step by step, the state of a queue -- implemented as an 3-element array - when we first add 5, and 14, then dequeue, then add 20 and 0, dequeue again and add 1. Write a method for dequeuing a queue represented as an array.

```

```
6-7. Show, step by step, how bubble sort, selection sort, insertion sort, quicksort, and mergesort will sort a list consisting of the elements 2, 0, 10, 5, 14. Write a code for one of these sorting algorithms. What is the worst-case and average complexity of each of these sorting algorithms?

```

```
8. Show, step by step, what will happen if we add elements 2, 0, 1, 5, and 14 to the binary search tree; do not forget to balance at every step at which balancing is necessary. Show how the resulting tree will look like in a reference-based and in an array-based implementation of trees. What is the purpose of balancing? No code is needed.

```

```
9. Show, step by step, how sequential search and binary search will look for an element 0 in the sorted list 20, 14, 5, 1, and 0. What is the worst-case and average complexity of each search? What are relative advantages and disadvantages of these two search algorithms? Write down a method implementing sequential search and another implementing binary search. Assume that the list is implemented as an array.

```

```
10. Show, step by step, how the hash table will looks like if we sequentially add to it elements 5, 14, 20, 0, and 1. Assume that as a hash function, we take remainder modulo 7: h(n) = n % 7. What are advantages and disadvantages of hash tables?