CS 2401 Final Exam

1-2. Recursion:

1. Write a recursive method for transforming a decimal number into a binary number.
2. Trace your method on the example of n = 10.
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.

1. Write a method that, given a general square matrix A, returns the sum of the diagonal elements from the upper-left to lower-right; this sum is called a trace of the matrix. For example, for the matrix

     1  2  3
     4  5  6
     7  8  9
   

   your method should return the value 1 + 5 + 9 = 15.
2. Trace your method on the example of this matrix.
3. Using big-oh notation, what is the wost-case running time for your algorithm?

1. Rewrite the expresion 12 * 7 - (20 + 10) in postfix form.
2. Show, step by step, how a stack can be used to compute the value of the resulting postfix expression.

1. Show, step by step, the state of a queue -- implemented as an 3-element array - when we first add 12 and 7, then dequeue, then add 20 and 1, dequeue again and add 0.
2. Write a method for dequeuing a queue represented as an array.
3. Using big-oh notation, what is the worst-case running time for your dequeuing method?

1. Show, step by step, how bubble sort, selection sort, insertion sort, mergesort, quicksort, and heapsort will sort a list consisting of the elements 12, 7, 20, 1, and 0.
2. Write a code for one of these sorting algorithms.
3. Draw a table listing the worst-case and average-case complexity for each of the six sorting algorithms.
4. True or False: It is possible to implement a sorting algorithm that is much faster than heapsort. Justify your answer.

1. Show, step by step, what will happen if we add elements 12, 7, 20, 1, and 0 to an initially empty AVL binary search tree; do not forget to balance at every step at which balancing is necessary.
2. Show how the resulting tree will look like in an array-based implementation of trees (leave blank spaces for any nodes that do not exist in the tree).
3. In 1-2 sentences, what is the purpose of balancing?
4. State the condition that every node in a binary search tree must satisfy.

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

1. Show, step by step, how the hash table with four "buckets" will looks like if we sequentially add to it elements 7, 12, 20, 1, and 0. Assume that as a hash function, we take remainder modulo 4:
   h(n) = n % 4.
2. What are advantages and disadvantages of hash tables?
3. List two properties of a good hash function.