Your are responsible for everything that was on the first Prelim. We aren't looking to test that material, but it is understood that you know all the technical Java concepts that we have covered. That material should be part of your programming repetoire by now. Below, with each section, we list what you are responsible for and give some sample questions.
 

Questions on correctness of programs. Know what an assertion is, what a Hoare triple is, the definition of the assignment in terms of finding the precondition from the postcondition, what it takes to prove a conditional statement correct, and the checklist for understanding a loop. Given a precondition, postcondition, invariant, and bound function, you should be able to develop the loop. If we say, "linear search", "binary searech", "selection sort", "insertion sort", "partition", or "compute "x^y", you should be able to say what the problem is and write a loop with initialization for it (with invariant, of course).

1. What is an assertion? What is a Hoare triple? What does the notation
        // {precondition}
        statement
        // {postcondition}

2. Give the precondition for the following:
        // { ? }
        x= 2*x*y;
        // {x+y < 64}

3. Write the check list for understanding a loop (with initialization).

4. For each of the following problems, you should write the invariant and bound function (as we have given them) and then write the loop based on that invariant and bound function:
(a) linear search
(b) binary search
(c) partition algorithm
(d) selection sort
(e) computing x^y (x to the power y) in in time O(log y).

5. Write a loop with initialization, given the precondition, postcondition, invariant, and bound function. Of course, the answer will be graded on whether the answer can be understood in terms of the check list for understanding loops. Here are 3 examples:

(a) Write a loop (with initialization) that determines the number of elements of b[h..k-1] that are not equal to the preceding element.
    Precondition: h < k
    Postcondition: x = no. of elements of b[h..k-1] that do not equal the preceding element
    Invariant: h+1 <= i <= k and x = no. of elements of b[h..i-1] that do not equal the preceding element
    Bound function: k-i

(b) Write a loop (with initialization) that calculates the number of zeros in b[h..k-1]
    Precondition: h <= k
    Postcondition: x = no. of 0's in b[h..k-1]
    Invariant: h <= j <= k and x = no. of zeros in b[j..k-1]
    Bound function: j-h

(c) Write a loop with initialization that find the greatest power of 2 that is at most n. The algorithm must take time O(log n).
    Precondition: 0 < n
    Postcondition: b is a power of 2 and b <= n < 2*b
    Invariant: b is a power of 2 and b <= n
    Bound function: n - b

(d) Write a loop that finds the name of a node whose value is v (null if none) in a linked list b
    Precondition:   b is the name of the first node of a linked list (null if the list is empty)
    Postcondition: p is null means that v is not in linked list b.
                            p != null means that (1) p is the name of a node of linked list b,
                                                             (2) nodes before p do not contain v
                                                             (3) p.element.equals(v)
    Invariant: p is null means that v is not in linked list b.
                    p != null means that (1) p is the name of a node of linked list b,
                                                     (2) nodes before p do not contain v
    Bound function: number of nodes that follow p in the list

(e) Array b[h..k-1] contains red, white, and blue balls. Write an algorithm that permutes b[h..k-1] using at most k-h swaps so that the red balls are first, then the whites, and then the blues.
    Precondition: h<=k
    Postcondition: b[h..p-1] are reds, b[p..q-1] are whites, and b[q..n-1] are blues.
    Invariant: b[h..p-1] are reds, b[p..q-1] are whites, b[q..t-1] are unknown, and b[t..n-1] are blues.
    Bound function: t-b

(f) The following summation can be used to compute the value of Pi (the ratio of the diameter of a circle to its circumference):

    Pi = 4 * (1/1 - 1/3 + 1/5 - 1/7 + 1/9 + ...)

Term n (for n>= 1) in this sum is 4*((-1)^(n-1)/(2n-1).

Write a well-specified Java method that calculates this sum, terminating the computation when either of the following conditions is true:

    (a) 1000 numbers have been added.
    (b) The absolute value of the last number added to the sum is strictly less than 0.00001.

Be sure to write and use a loop invariant and bound function.

(g)  Write a Java method calculates the string representation of that integer. For example, given the integer 34, it should return the string "34" consisting of the character `3' and the character `4'. You can use standard integer and string operations, but you are not allowed to use the built-in Java method String.valueOf.
 

Questions on searching and sorting. You should know the following algorithms (some of them written as recursion procedures): linear search, binary search, partition, selection sort, insertion sort, merge sort, quick sort. You should know what their worst-case and best-case execution times are.

1. The departmental phone number is 2557316. Show how the order of the digits changes as the digits are sorted using Quick
Sort, Insertion Sort, and Merge Sort. For Quick Sort, assume that the first item is used as the pivot item (this is not a good choice).

2. For each of the following problems, you should write the invariant and bound function (as we have given them) and then write the loop based on that invariant and bound function:
(a) linear search
(b) binary search
(c) partition algorithm
(d) selection sort

3. You should be able to write mergesort and a simple version of quicksort.

4. Consider the following sorting methods: Insertion Sort, Merge Sort, and Quick Sort.

     a.What is the running time for each method when all the the array values are equal?
     b.When the values are in order?
     c.When the values are in reverse order?
 
 

Questions on algorithmic analysis. Basically, know Weiss chapter 5. See the handout on algorithm analysis for a detailed list of what you have to know (it tells you what you are NOT responsible for). In addition, you should be able to prove that a given function is O(f(n)) (for some f(n)), and you should be able to analyze an algorithm and figure out its order of execution time.

1.  (a) Java Nagila, a CS211 student, implemented a bunch of algorithms and came up with the following running times as a function of input size.  Using big-O notation, write down the simplest and most accurate expressions for the complexity of these algorithms.

       f(n) = 2n log(n) + 4n + 17 * log (n)
       g(n) = log(n*n*n)

(c) The following method returns the element number i of an integer list.

public static int element (List list, int i) {
        if (i == 1) return list.first();
        return element(list.rest(), i-1);
}

2.  Fill in the table below with the expected time for each operation. Use big-O notation. The operations are insert (place a new item in the data structure), find (test if a given item is in the data structure), getMin (return the value of the minimum item in the data structure and delete it from the data structure), and successor (given an item, return the successor of that item).
 

Questions on data structures. 1. Linked lists. We have used the terms linked list, linked list with header, doubly linked list, and doubly linked list with head and tail with technical meanings. You have to know what those terms mean. You should be able to write algorithms that travers these kinds of lists, do something to each element. You have to be able to remove and element from and add an element to these kinds of linked lists (don't memorize code; instead, be able to draw the situation and develop the code from the drawing). Know the advantages and disadvantages of using these kinds of linked lists. Be able to say what the order of execution time is for these operations on the different kinds of linked list: find a value, delete the minimum value, delete a node whose name is known, insert a value after a given node, insert a value before a given node.  All of these are straightforward and obvious if you understand the details of the different kinds of list.

2. Hash tables. Know how to implement a set in a hash table (as discussed in a recitation handout). You do not have to know a hash function, bubt you have to know what its purpose is. Know about linear probing, quadratic probing, how an element is added, how an element is deleted. Know what the load factor is and how many probes can be expected when the load factor is 1/2.

3. Binary trees. Weiss, sections 18.1.1 (not 18.12 and 18.13), 18.2, 18.3). Know the definition of a binary tree and how a binary tree is implemented. Be able to write methods that perform preorder, inorder, and postorder traversals of trees. (Don't read Weiss, section 18.4, to find out about preorder, inorder, and postorder traversal, because he doesn't do them recursively.) Know how to implement an expression in a binary tree.

4. Binary search trees. Weiss, section 19.1) Know the definition of a binary search tree. Know how to lok for a value in a binary search tree, to find the minimum value of a binary search tree, and to add a value to a binary search tree.

1.  (a) In the class below, insert a static procedure that appends to linked list L1 the elements of L2 --the last node of this list is changed to contain the name of the first cell of L2.  The  method does not return anything.  The lists are built using class ListNode, given below.

(b) What is the asymptotic complexity of your algorithm, expressed as a function of n1 and n2, where n1 is the number of
elements in L1 and n2 is the number of elements in L2?  Justify your answer (briefly).

class ListNode {
        protected Object element;
        protected ListtNode next;

        // Constructor: an instance with element x and next field n
        public ListNode (Object x, ListNode n)
            {  element = x;  next = n; }

        public Object getElement ()
                {  return element;  }

        public ListNode getNext ()
                {    return next;  }

        // Set this node's element to x
        public void setElement (Object x)
                {  element = x;  }

        // Change this next field to n
        public void setNext (ListNode n)
                {  next = n; }

        // Print this element together with the rest of the elements in this List
        public String toString () {
              if (next == null)
                return element.toString();
              return element.toString() + " " + next.toString();
        }
}
 

2. You have a hash table of size m=11 and a (not very good) hash function h:

        h(x) = (sum of the values of the first and last letters of x) mod m

where the value of a letter is its position in the alphabet (e.g., value(a)=1, value(b)=2, etc.). Here are some precomputed hash values:

Draw a picture of the resulting hashtable (using linear probing) after inserting, in order, the following words: ibex, hare, ape, bat, koala, mud, dog. Which cells are looked at when trying to find bird?  What is the load factor for the hash table?

3.  (a) What is quadratic probing, and why is it preferred over linear probing?
       (b) What is a probe? What is the expected number of probes, using linear probing, when the load factor is 1/2?
 

4.  Where is the smallest element in a Binary Search Tree? The following picture represents a BST (Binary Search Tree).

             (22)

           /      \

       (14)        (25)

      /   \       /    \

   (11)   (16) (23)     (40)

                  \     /

                 (24) (32)

• In what order are the nodes visited during a preorder traversal?  Inorder traversal?  Postorder traversal?
• Show the tree that results when 15 is inserted into the tree.

6. Write recursive methods for printing the inorder, preorder, and postorder list of the nodes of a binary tree.

7. For each of the following problems, choose the best of the listed data structures and explain why your choice is best. Assume that the data set is going to be large unless otherwise indicated.  Where several operations are listed you should assume, unless stated otherwise, that the operations occur with about equal frequency.

• Operations are Insert, DeleteMax, and DeleteMin.

sorted array or sorted doubly-linked list
• You have a set containing Java's keywords.

ordered array or balanced tree
• You have a set that can contain anywhere from 100 to 10,000 words. Operations are insert, find.

unordered linked-list or hash table
• You have a large set of integers with operations insert, findMax, and deleteMax.

unordered array or Hashtable

1. Explain in a sentence or two the difference between overloading and overriding.
 

2. Consider a database for keeping track of student grades in CS211. A student's scores in the assignments are kept in an object of type StudentGrades; array element Scores[i] is the score in assignment i for that student. An object of type BigBook contains an object of type StudentGrades for every student who has submitted an assignment. The total number of students in the course is known to be less than 100. An outline of the class definitions are shown below.

class BigBook {
   private int MaxClassSize = 100;
    private int numAssignments;   // The number of assignments
    private studentGrades[] Folio;  // An entry is either null or the name of a StudentGrades folder

    // Constructor: an empty folio of students and NA assignments
    public BigBook(int NA) {
        numAssignments = NA;
        Folio = new StudentGrades[MaxClassSize];
    }
    ...
}

class StudentGrades {
    private String name;  // Scores contains the grades for student name
    private int[] Scores;

    // Constructor: a student named grunt with an array of NA assignment scores
    public StudentGrades(String grunt, int NA) {
        name = grunt;
        Scores = new int[NA];
    }
......
}

(a) Write methods in one or both classes that will permit my secretary to enter a grade for a student for a particular assignment into her database. The method invocation must look like the following:

    CS211database.Enter(``Albert Gore'', 4, 10);

In this invocation, CS211database is an object of type BigBook, and Enter is an instance method. This invocation should check the database for a student named Albert Gore. If this student is not in the database, first insert them into the database. Then, change the grade for assignment 4 with a grade of 10, provided the assignment number is in the range 0..NumAssignments-1. You may not add or remove any instance variables in either class.

(b) If a method in class StudentGrades is passed a reference to an object of type BigBook, can that method access the field NumAssignments in this object? Explain two ways in which this method can determine the number of assignments.
 

3.  (a)  Write exactly one method that takes in an integer and may throw one of  two new exceptions (of type Exception) with messages "Too high!" and "Too low!".  If the value is out of the range 0..100 (inclusive), throw the appropriate exception.

(b)  Suppose method A calls method B, and method B calls method C, and C is defined to potentially throw an exception.  Can this exception be handled in method A?  If not, why?  If so, how?

4. Java does not allow multiple inheritance because two classes can define methods with the same signature that do completely different things.  Therefore, if a child class extends two such  classes, if it refers to one of these pre-existing methods in a super class, JAVA won't know which method to execute.  However, Java does allow a class to implement more than one interface.  Why don't interfaces have the same problem with method ambiguity that classes do?
 

Questions on recursion

1. Give a recursive algorithm for making change with the smallest number of coins. The input to your method is an integer array coins[] containing the possible values for the coins and an int that is the change needed. The output should be an array indicating the number of each coin needed. So, if the input is coins[] = {1, 5, 10, 25} and amount = 55, then the output should be an array change[] = {0, 1, 0, 2}. Hint: For the recursive step, subtract the amount of one coin from the amount of change needed. Be careful to use the smallest number of coins in your solution.

2. Specify and a recursive method that determines whether a String s is a palindrome.  A palindrome is a String that reads the same backward and forward.