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?