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?