COMP 212 - Exam #3

Instructions:

  1. The examination is open book with no time limit.
  2. Just like for the projects, create a README file to indicate what you have and/or have not done, and to point out specific details that you feel I need to know when grading your work.  You have the option to tell me how much time is spent on this exam.  This is purely for statistical purpose only and does not affect your grade in any way.
  3. You are allowed to consult any written materials available under the sun, except code from your current Comp212 classmates.  If your code is based on materials that I did not provide you, just give me the references in the README file.
  4. You are not allowed to discuss the exam in any way with anybody beside myself, your humble instructor.
  5. Do not post your question on the newsgroup.  E-mail me your question instead. I will reply to you directly, and if deemed necessary, I will forward my reply to the newsgroup as well.  I will check my e-mail as often as I can to catch your questions.
  6. Write your code in the most object-oriented way possible, that is with the fewest number of control statements and no checking of the states and class types of the objects involved.
  7. In all of the questions, feel free to write additional helper methods or visitors to get the job done.
  8. Make sure you use the Singleton pattern whenever appropriate.
  9. There are four questions for a total of 100 points.
  10. You have until 5:00 PM, Monday, December 20, 1999,  to complete and submit the exam.  Since this is the last day of all finals, you cannot use any slack days.
  11. To submit the exam, follow the latest instruction posted on the Comp212 web page.  When you are ready to submit, notify me via e-mail with your pledge of honor.  Do not modify the time stamps on your exam files.
  1. Write the code for the class specified below.  You are free to add appropriate private methods.  20 points

    public class Utility
    {
    /**
    * Prints an array of int for indices ranging from lo to hi. The printed array
    * should be bracketed by matching curly braces. The array elements should
    * be separated by commas.
    * Examples:
    * For an empty array A, printArray (A, 0, A.length-1) should print {}.
    * For the array A containing the single int -3,
    * printArray (A, 0, A.length-1) should print {-3}.
    * The array containing -3 and 5 in this order,
    * printArray (A, 0, A.length-1) should print {-3, 5}.
    *
        * @param A an array of int.
        * @param lo an index in the range [0:A.length-1].
        * @param hi an index in the range [0:A.length-1].
    */
        public static void printArray(int[] A, int lo, int hi)
        {// Student to write code.
        }

    /**
    * Computes and returns x to the n-th power: xn.
        * @param x
        * @param n >= 0.
        * @return x to the n-th power, for example power (-2, 3) == (-2)3 == -8.
    */
        public static int power(int x, int n)
        {    // Student to write code.
        }

    /**
    * Tests printArray(...) and power(...).
        * @param args
    */
        public static void main(String[] args)
        {// Student to write code for testing of key cases.
        }
    }

  2. Copy SelectionSorter from week 14 handouts and modify it to print the whole array after each split.  You can assume you have written Utility.printArray (...)correctly, and you can use it in your code for this problem.  The output to the main method should look like the following.  20 points

    A = {99, -34, 0, 5, -7, 0}

    Selection sorting A...
    {-34, 99, 0, 5, -7, 0}
    {-34, -7, 0, 5, 99, 0}
    {-34, -7, 0, 5, 99, 0}
    {-34, -7, 0, 0, 99, 5}
    {-34, -7, 0, 0, 5, 99}
    Sorting done!!!

    A = {-34, -7, 0, 0, 5, 99}

  3. Bubble sort is an elementary and very slow sorting algorithm.  You can find it in many data structures textbooks.  The idea is to scan the array from bottom to top several times, swapping adjacent elements if they are out of order, so that, one at a time, the smaller elements "bubble" to the top.  Feel free to consult any textbook on bubble sort.  Here is the pseudo-code describing bubble sort on an array A[0:N] of int. 

        for (int i = 0; i < N; i++)
        {
            for (int j = N; j > i; j--)
           {
                if (A[j] < A[j-1])
                {
                     swap A[j] with A[j-1];
                }
           }
        }

    The following is an example of output that displays the re-arrangement of an array during each scan of the array.


    A = {99, -34, 0, 5, -7, 0}

    Bubble sorting A...
    {-34, 99, -7, 0, 5, 0}
    {-34, -7, 99, 0, 0, 5}
    {-34, -7, 0, 99, 0, 5}
    {-34, -7, 0, 0, 99, 5}
    {-34, -7, 0, 0, 5, 99}
    Sorting done!!!

    A = {-34, -7, 0, 0, 5, 99}


    Write the code to implement bubble sort to fit into Susan Merritt's sorting taxonomy (see week 14 handouts).  Below is the specification.  30 points

    public class BubbleSorter extends ASorter
    {// Student to write other appropriate field(s), constructor(s), and method(s);

    /**
    * Splits A[lo:hi] into A[lo:lo] and A[lo+1:hi] in such a way that adjacent
    * elements in A[lo:hi] are compared and swapped if they are out of order,
    * and in the end, the smallest element is "bubbled up" to become A[lo].
        * @param A the array A[lo:hi] to be sorted.
        * @param lo the low index of A.
        * @param hi the high index of A.
        * @return ???? student to fill out what the split index should be.
    */
        public int split(int[] A, int lo, int hi)
        {    // Student to write code.
        }

        /**
        * Joins sorted A[lo:s-1] and sorted A[s:hi] into A[lo:hi].
        * @param A A[lo:s-1] and A[s:hi] are sorted.
        * @param lo the low index of A.
        * @param s the split index.
        * @param hi the high index of A.
        */
        public void join(int[] A, int lo, int s, int hi)
        {// Student to write code.
        }

    /**
    * Tests BubbleSorter.
    */
        public static void main(String[] args)
        {// Student to write code to test BubbleSorter.
        }
    }

  4. A polynomial of one variable, p(x),  is an expression of the form

    anxn + an-1xn-1+ ... + a1x + a0,

    where n is a non-negative integer, ak  (k = 0.. n) are numbers, and an is a number not equal to 0. 

    n is called the degree of p(x),ak  (k = 0.. n) are called the coefficients of p(x), and an is called the leading coefficient of p(x). 

    For examples:

    We can describe polynomials  in the following manner.  A polynomial can be constant or non-constant; if it is constant, it has a leading coefficient and degree 0; if is not constant, it has a leading coefficient, a non-zero degree, and a lower degree polynomial.  The polynomial intrinsic behavior is to provide the clients with its degree, its leading coefficient, and its lower degree polynomial (if any).

    Your task is to design a system of classes to implement polynomials in the most flexible way.  For the sake of simplicity, we shall consider polynomials with integer (int) coefficients only.  Your polynomial implementation must provide ways to

    1. evaluate a polynomial for a given value of x; for example, if p(x) = -3x2 + 7 then p(-1) = (-3)(-1)2 + 7 = 4. Use Utility.power (...), if needed.
    2. add two polynomials together and obtain the resulting sum.

    Your polynomial system must be designed in such a way that, adding at a later time the capability to multiply polynomials, perform long division on polynomials, etc. will only require adding new classes to the system and not any modification and recompilation of the existing code.  Also, suppose at a later time you come up with a better algorithm to evaluate a polynomial, your system should allow you to replace the old evaluation algorithm with the new one without any modification and recompilation of the existing code.  Explain and describe briefly your design in terms of well-known patterns.  Write appropriate test code.  30 points