## CS 2401 Final Exam

Date: May 11, 2010.
Name: ____________________________________________

1-2. Write a recursive method for computing Fibonacci numbers Fib(n). Reminder: Fib(1) = Fib(2) = 1, and Fib(n) = Fib(n-1) + Fib(n-2). Trace your code on the example of n = 4. 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 for transposing a general square matrix A --> AT. Reminder: Transposing means that rows become columns and vice versa: (AT)ij = Aji. For example, for the matrix
```  1  2  3
4  5  6
7  8  9
```
the transposed matrix takes the form
```  1  4  7
2  5  8
3  6  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 * (11 + 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, 11, and 20, then dequeue twice and after that add 0 and 1. Write a method for adding an element to 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 5, 11, 20, 1, 0. Write a code for one of these sorting algorithms. What is the worst-case and average complexity of each of these sorting algorithms? Is it possible to have a sorting algorithm which is much faster than mergesort?

```

```
8. Show, step by step, what will happen if we add elements 5, 11, 7, 20, and 13 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 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 20 in the sorted list 0, 1, 5, 11, and 20. 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, 11, 20, 0, and 1. Assume that as a hash function, we take remainder modulo 5: h(n) = n % 5. What are advantages and disadvantages of hash tables?