CS 2401 Final Exam

Date: Tuesday, May 12, 2009.
Name: ____________________________________________

1. Write a recursive method for computing the sum of the inverses Sn = 1/1 + 1/2 + 1/3 + ... + 1/n. Explain first how you go from the case n-1 to the case n, then transform this algorithm to code, and trace your code on the example of n = 3. Describe advantages and disadvantages of recursion vs. a more traditional method of solving a problem, from the viewpoint of easiness to write, easiness to understand, and running time.

2. Show the sequence of moves that solves the Hanoi tower problem for n = 2 and for n = 3.

3-4. Suppose that a linked list is implemented as a node
public class Node{
  public int info;
  public Node link;
Write a piece of code for adding an element in front of the list. Draw the corresponding pictures on the example of adding an element 5 to a list consisting of integers 12 and 2009. Then present a piece of code and pictures for the array implementation of a linked list.

5. Suppose that you already have an implementation of a stack, with operations push and pop implemented. Write down a method that uses the stack operations to check that in a given expression, every opening curly bracket { has a matching closing bracket }. Trace your code on the example of an expression {ab}}.

6. What is an abstract data type (ADT)? What are the advantages of using ADTs? Give an example of two different implementation of the same ADT. In Java, how do we implement an ADT so as to guarantee that we can access the corresponding objects only via appropriate operations?

7-8. Show, step by step, how bubble, insertion sort, quicksort, and mergesort will sort a list 5, 12, 2, 9. No code is needed. What is the worst-case and average complexity of each of these sorting algorithms?

9. Show, step by step, what will happen if we add elements 5, 12, 2, and 9 to the binary search tree; do not forget to balance at every step at which balancing is necessary. No code is needed.

10. Show, step by step, how binary search will look for an element 9 in the sorted list 2, 5, 9, 12. What is the worst-case and average complexity of binary search? Write down a method implementing binary search. Assume that the list is implemented as an array.