TOPICS TO REVIEW:

Everything from Test1

Recursion 
    Program analysis

    MergeSort  and QuickSort (including performance analysis)
    Recursion w/ backtracking (understand the examples)

Data Structures:
    Basic ideas and definitions
    Stacks and queues
       what, how and why
       operations (methods)
        (array based and linked implementations)


    Lists:
       list operations
        (array based and linked implementations)
    Fixed vs Dynamic Structures: pros and cons
    Performance analysis

Trees:
    general ideas, concepts and definitions
    general trees, binary trees (definitions, traversals, applications)
    binary search trees (BST) 
        properties    
        operations on BST (and their implementations)
        performance analysis

Functors and their use

Applets:
    general ideas
    how to (basic concepts)

 

SAMPLE QUESTIONS FOR YOU TO PRACTICE:

 

  1. Multiple choice questions:

1.1.   If a stack is implemented as a singly linked list then

a)      both push() and pop() operations take O(1)

b)      either push() or pop() takes O(n)

c)      push() adds a node to a head and pop() removes from a tail of linked list

d)      both push() and pop() operations take O(n)

 

 

1.2.   Which of the following is true:

e)      Worst case running time for Mergesort is O(n2)

f)       Best case running time for Mergesort is O(n)

g)      Worst case running time for Quicksort is O(nlogn)

h)      Worst case running time for Mergesort is O(nlogn)

 

 

1.3.   What is the running time for the unsuccessful search operation on the binary search tree BST if it was created the following way: an array A of size n is first sorted,  then each element of A is inserted in a BST starting from A[0], then A[1], A[2],…,A[n].

a)      O(n)

b)      O(nlogn)

c)      O(n2)

d)      O(logn)

 

  1. State the definition of Big-Oh in terms of the statement g(n) is O(f(n)). Using this definition, prove that 4n4 + 9n3 + 3n + 2 is O(n4).
  2. What is the basic difference between a stack and a queue?
  3. Suppose we insert the following numbers in order into a stack - 5, 4, 6, 8, 7. Which numbers (order matters!) would be returned if we called the stack's remove operation 3 times? Which numbers would be returned if we had inserted the same numbers into a queue and called the queue's remove operation 3 times?
  4. Let n be a power of two and suppose you repeatedly halve n. How many times do you have to halve n to get to 1?
  5. Consider the following problem: given an array populated with numbers in the range 1-1000 and an integer k, determine if there are a pair of numbers in the array that sum to k. Describe (using pseudocode and/or english) a linear time algorithm to solve the problem (it should be O(n) where n is the size of the array). Explain why the running time of your algorithm is linear.
  6. Use pseudocode to write the algorithm for the merge subroutine in merge sort OR the partition subroutine in quicksort (if you pick the latter, you may assume that a good pivot has already been chosen and is located at the far right of the array).
  7. Suppose we have a Queue that is implemented as a linked list of Comparable objects with the Node class defined as an inner class. The Node inner class has two attributes - Comparable data and Node next. For our application, it turns out that it would be useful to have a remove operation that can remove arbitrary element from the queue. Finish the code for this method, and describe the run time of the method. If you would like, you may use the following methods that have already been written: isEmpty(), makeEmpty(), enqueue(Object o), or dequeue(). 
    /**
     * This method removes and returns a reference to the
     * first object from the queue that is equal (i.e.
     * compareTo returns 0) to the supplied Comparable
     * object.
     * @param c the object to be removed
     */
    public Comparable remove(Comparable c)  {
        //special case: empty queue 
        if(this.isEmpty())
            throw new EmptyQueueException("The Queue is Empty!!!");
        }
            
        //Insert your code here
 
    }//end remove
  1. The Fibonacci Sequence is a sequence of integers. Here are the first few elements of the sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Note that the first two numbers in the sequence are 1's and then for n > 2, the nth Fibonacci number is sum of the previous two. Write a recursive Java method that takes in an integer n and returns the nth Fibonacci number. What is the efficiency of this algorithm in big-O terms?

10.  Consider the following recursive method.

 

     public static boolean foo(int n){

           if (n <= 0)     return false;

           if (n == 1)     return true;

 

           if (n%2 == 0)   return foo(n/2);

           else            return foo(n+1);

     }

 

(a)        What is/are the base case(s) of the above method? 

 

(b)        Trace foo(5) carefully.  Show the stack frames and the variable values along with the return values carefully. (If I cannot read/follow what you are doing you will not get much credit for this part.)

  1. Suppose we have a generic LinkedList class with all of the usual methods that were described in class (e.g. addToFront(), addToBack(), removeFromFront(), removeFromBack() - all implemented as they were in class). Now suppose we wanted to implement a Stack using inheritance, and did so as follows: 
    /**
     * Here, we assume that our Stack interface has only the
     *   push() and pop() methods required.  We also assume that
     *   our generic LinkedList class has a zero argument
     *   constructor (which we will use in our constructor).
     *   We also assume that our LinkedList class's remove methods
     *   return a reference to the object that it is removing.
     */
    public class LLStack extends LinkedList implements Stack  {
        private int size;
 
        /**
         * Creates an empty stack.
         */
        public LLStack()  {
            super();
            size = 0;
        }//end no-arg constructor
 
        /**
         * Pushes an element onto the top of the stack.
         * @param o the Object to be pushed
         */
        public void push(Object o)  {
            this.addToBack(o);
            size++;
        }//end push
 
        /**
         * Pops the top element off of the stack
         * and returns it.
         * @return the popped object 
         */
        public Object pop()  {
            if(size == 0)
                throw new NoSuchElementException("The Stack is Empty!!");
            Object result = this.removeFromBack();
            size--;
            return result;
        }//end pop   
    }//end class

 

What is wrong with this implementation of a stack (other than the fact that it will inherit a lot of unneccessary methods)?

12.  What is an exception? What is the difference between an unchecked and a checked exception?

  1. We covered a binary search algorithm in class, and implemented it recursively. Repeat that recursive implementation.

 

REMINDER:  Binary search algorithm searches an int key in a sorted array of integers by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

 

int binarySearch (int [] arr, int key, int f, int l){.....

 

 

Using your implementation trace the following client call (draw each recursive call of the method):

int [] a = {1, 2, 5, 7, 9, 14, 26, 120, 123, 140};

int i = binarySearch(a, 5, 0, a.length()-1);

binarySearch (a, 5, 0, 9)

 
 
 


 

 

14.  What is an interface? How are interfaces and multiple inheritance related?

  1. Suppose you were implementing a Queue as a circular array (ring buffer). Write a toString() method for such a Queue. You must use the mod (%) operator. Your queue has the following instance variables - ints representing front, back, numElements and size.
  2. Suppose that you inserting the following elements into an empty binary search tree - 8, 3, 10, 11, 6, 5, 1, 15. Draw the tree and then show the order the nodes would be visited using a pre-order, post-order, and in-order traversals.

17.  Suppose you run a program and it crashes with a NullPointerException. What is the problem? How would you go about hunting down the offending code and correcting it?

18.  Walk me through how you would go about putting a Java applet on a web page on atlas, including copying/moving required, setting proper permissions, etc.

19.  Write the method findMax that takes an array of objects arr and a Comparator cmp and finds the maximum Object using the compare method of cmp:

public static Object findMax( Object [ ] arr, Comparator cmp ){...

 

A RANDOM COLLECTION OF QUESTIONS FOR THAT YOU CAN LOOK AT (some have answers):

Question 11)


What will be the result of attempting to compile and run the following code? 

abstract class MineBase {

 abstract void amethod();

 static int i;

}

public class Mine extends MineBase {

 public static void main(String argv[]){

 int[] ar=new int[5];

 for(i=0;i < ar.length;i++)

 System.out.println(ar[i]);

 }

}

1) a sequence of 5 0's will be printed
2) Error: ar is used before it is initialized
3) Error: Mine must be declared abstract
4) IndexOutOfBoundes Error

3) Error: Mine must be declared abstract
 

A class that contains an abstract method must itself be declared as abstract. It may however contain non abstract methods. Any class derived from an abstract class must either define all of the abstract methods or be declared abstract itself.

 

Question 15)

What will be output if you try to compile and run the following code, but there is
no file called Hello.txt in the current directory?. 

import java.io.*;

public class Mine {

    public static void main(String argv[]){

               Mine m=new Mine();

               System.out.println(m.amethod());

    }

    public int amethod() {

               try {

                   FileInputStream dis=new FileInputStream("Hello.txt");

               }catch (FileNotFoundException fne) {

                   System.out.println("No such file found");

                   return -1;

               }catch(IOException ioe) {

               } finally{

                   System.out.println("Doing finally");

               }



               return 0;

    }



}

1) No such file found
2 No such file found ,-1
3) No such file found, Doing finally, -1
4) 0

3) No such file found, doing finally, -1

The no such file found message is to be expected, however you can get caught out if you are not aware that the finally clause is almost always executed, even if there is a return statement.

 

Question 16) *

Which of the following statements are true?

1) Methods cannot be overriden to be more private
2) static methods cannot be overloaded
3) private methods cannot be overloaded
4) An overloaded method cannot throw exceptions not checked in the base class

1) Methods cannot be overriden to be more private

Static methods cannot be overriden but they can be overloaded. If you have doubts about that statement, please follow and read carefully the link given to the Sun tutorial below. There is no logic or reason why private methods should not be overloaded. Option 4 is a jumbled up version of the limitations of exceptions for overriden methods

 

Question 17)

What will happen if you attempt to compile and run the following code? 

class Base {}

class Sub extends Base {}

class Sub2 extends Base {}

public class CEx{

    public static void main(String argv[]){

               Base b=new Base();

               Sub s=(Sub) b;

    }

}

1) Compile and run without error
2) Compile time Exception
3) Runtime Exception

3) Runtime Exception

Without the cast to sub you would get a compile time error. The cast tells the compiler that you really mean to do this and the actual type of b does not get resolved until runtime. Casting down the object hierarchy is a problem, as the compiler cannot be sure what has been implemented in descendent classes. Casting up is not a problem because sub classes will have the features of the base classes. This can feel counter intuitive if you are aware that with primitives casting is allowed for widening operations (ie byte to int).

4. How can Sherlock Holmes solve a mystery - recursively?

A.    (1) Examine one clue, and (2) examine the remaining clues.

B.    (1) Question one witness, and (2) question the victim.

C.    (1) Eliminate one witness, and (2) eliminate the remaining witnesses.

D.    (1) When one suspect remains, that is who did it. (2) Examine the evidence to eliminate one suspect, then eliminate the remaining suspects.

D

 

3. Look at square numbers again:

square(1) = 1

square(N) = square(N-1) + 2N -1

Which Java method below successfully implements this definition?

A.   

int square( int N )

{

  if ( N<1 )

  {

    return 1;

  }

  else

  {

    return N*N;

}

B.   

int square( int N )

{

  if ( N==1 )

  {

    return 1;

  }

  else

  {

    return square(N-1) + 2*N - 1; 

  }

}

C.   

int square( int N )

{

  if ( N=1 )

  {

    return 1;

  }

  else

  {

    return square(N-1) + 2*N - 1; 

  }

}

D.   

int square( int N )

{

  if ( N==1 )

  {

    return 1;

  }

  else

  {

    return square(N); 

  }

}

B

 

 

4. Look at square numbers one more time:

square(1) = 1

square(N) = square(N-1) + 2N -1

Assume the definition has been implemented correctly. How many activations will there be on the activation chain if main() calls square(5)?  How many recursive calls?

A.    1

B.    3

C.    5

D.    6

C

 

1. Consider a definition of mystery():

mystery(0,N) = N

mystery(P,Q) = mystery(P-1, Q+1)

According to this definition, what is mystery(2,4)?

A.    0

B.    2

C.    4

D.    6

D

 

2. Look at mystery() again:

mystery(0,N) = N

mystery(P,Q) = mystery(P-1, Q+1)

Which of the following Java methods correctly implements it?

A.   

int mystery( int P, int Q )

{

  if ( Q==0 )

  {

    return Q;

  }

  else

  {

    return mystery(P-1, Q-1); 

  }

}

B.   

int mystery( int P, int Q )

{

  if ( P==Q )

  {

    return Q;

  }

  else

  {

    return mystery(P-1, Q); 

  }

}

C.   

int mystery( int P, int Q )

{

  if ( P==0 && Q==0)

  {

    return 1;

  }

  else

  {

    return mystery(P-1, Q+1); 

  }

}

D.   

int mystery( int P, int Q )

{

  if ( P==0 )

  {

    return Q;

  }

  else

  {

    return mystery(P-1, Q+1); 

  }

}

D

 

Top of Form

9. Here is another definition. Assume that x is a variable that represents a single character and that X represents a string. The operator "+" means concatenation.

rev( "" ) = ""

rev( x+X ) = rev(X) + x

What is rev( "fooey" )?

A.    "ooeyf"

B.    "ooey"

C.    "Fooey"

D.    "yeoof"

 

 

10. Here is the definition.

rev( "" ) = ""

rev( x+X ) = rev(X) + x

Which of the following correctly implements it?

A.   

String  rev( String str )

{

  if ( str == ""  )

    return str;

  else

    return rev( str.substring(1) ) + str.charAt(0);

}

B.   

String  rev( String str )

{

  if ( str.length() == 0 )

    return str;

  else

    return rev( str.substring(1) ) + str.charAt(0);

}

C.   

String  rev( String str )

{

  if ( str.length() == 0 )

    return str;

  else

    return rev( str.substring(0) ) + str.charAt(0);

}

D.   

String  rev( String str )

{

  if ( str.length() == 0 )

    return str;

  else

    return rev( str.substring(0) ) + str.charAt(1);

}

 

______________________________________________________________

Consider this definition of the sum of the elements in an integer array:

sum( array, index ) = 0, if index == array.length

 

sum( array, index ) = array[index] + sum( array, index+1), if index < array.length

Write a Java method that implements this definition and a program to test it. The method should look something like:

int sum ( int[] array, int index )

{

 . . .

}

The testing program will call sum( testArray, 0 ).

 

a) Write your own recursive definition of the maximum element in an array of integers. Then, implement your definition in Java and test it with a testing program.

b) Implement an iterative method with the same signature, and similar time complexity.

_______________________________________________________________

A palindrome is a string that is the same when reversed. For example, "abba" is a palindrome. Here is a math-like definition:

palindrome( "" ) = true

 

palindrome( x  ) = true

 

palindrome( x+X+y ) = false, if x != y

                    = palindrome( X ), if x == y

The symbol x stands for a single character, as does y. The symbol X stands for a string of characters. The symbol + stands for concatenation.

Implement a recursive method palindrome(….) that will check whether a given string is a palindrome or not and write a client call that tests it.