CS 2401 Final Exam

Date: December 10, 2009.
Name: ____________________________________________

1. Write a recursive method to multiply two positive integers x and y using repeated addition. Trace your code on the example of x = 4 and y = 3. Describe advantages and disadvantages of recursion vs. iteration solving a problem, from the viewpoint of easiness to write, easiness to understand, and running time.

2-3. Write a method reverseColumn to reverse the first column (column 0) of a generic 2D matrix and a method reverseRow to reverse the first row (row 0) of a generic 2D matrix (reverseRow). Show how the 2D matrix declared below will look like after the methods reverseColumn and reverseRow are applied in this order.
int[] matrix = {{1, 2, 3},
               {4, 5, 6},
               {7, 8, 9}};

Reversing a 1D array means reversing the order: for example, 5, 6, 7 becomes 7, 6, 5.

4-5. Suppose that a linked list is implemented as a node
public class Node{
  public String 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 "John" to a list consisting of elements "Joseph" and "Joe". Then present a piece of code and pictures for the array implementation of a linked list.

6. Suppose that you already have an implementation of a queue, with operations addQueue and deleteQueue implemented. Use this queue to manage the documents sent to a printer. Show the state of the queue step-by-step. Assume that the queue starts empty and then it receives three documents: Doc1, Doc2 and Doc3 in that order. Assume that these documents are sent to the queue in intervals of two minutes and that they are remove from the queue by the printer that takes three minutes to print each document.

7-8. Show, step by step, how bubble, insertion sort, quicksort, and mergesort will sort a list 7, 4, 3, 5. 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 sequential search and 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 each search? Write down a method implementing sequential search and another implementing binary search. Assume that the list is implemented as an array.