CS 2401 Final Exam

1-2. Recursion:

1. Write a recursive method (code) for computing the sum of all the elements of a linked list.
2. Trace your method on the example of a list consisting of elements 12, 10, and 20.
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 for checking whether all the elements of a matrix are positive. For example, for the matrix

     1  2  3
     4  5  6
     7  8  9
   

   the answer should be "true", while for the matrix

     1  -2 3
     4  5  6
     7  8  9
   

   the answer should be "false".
2. Trace your method on the example of the second matrix.
3. Using big-oh notation, give the worst-case running time for your algorithm.

1. Rewrite the expression 12 - 10 * (20 - 1) 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, 10, and 20, then dequeue twice and after that add 1 and 0.
2. Write a method for enqueuing an element in a queue represented as an array.
3. Using big-oh notation, what is the worst-case running time for your enqueue 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, 10, 20, 1, 0.
2. Write code for one of these sorting algorithms (clearly specify which one).
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. Suppose you start with an empty AVL binary search tree. Show step by step what will happen if you add elements 12, 10, 20, 1, and 0 to the binary search tree in that order. Balance at each step where it 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, 10, 11, and 20.
2. What is the worst-case and average-case number 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 a hash table with six "buckets" will look if we sequentially add to it elements 12, 10, 20, 0, and 1. Assume that as a hash function, we take remainder modulo 6:
   h(n) = n % 6.
2. What are advantages and disadvantages of hash tables?
3. List two properties of a good hash function.