COP 3337
Section U05
Spring 2017


                     Programming Problems and Solutions
                     ==================================



    Problem 1.
    ==========

      Write a recursive method,

    public static <T extends Comparable< ? super T>>
        void merge(LinkedList<T> list1, LinkedList<T> list2,
        LinkedList<T> list)

    that takes as input two linked lists, list1 and list2,
    sorted in the increasing order of compareTo and merges them
    onto list.
    Assume that when the call to merge is made none of the 3 lists
    is null and list is empty. You may also assume that none of
    the items of list1 and list2 is null. Both list1 and list2 may
    have duplicate items, and some items may occur in both lists.
    When you merge, keep the duplications.

    For example, if list1 is
        Bill, Dan, Dan, Mark

    and list2 is
        Bill, Carol, Mark, Mark

    when the method returns, list must be
        Bill, Bill, Carol, Dan, Dan, Mark, Mark, Mark

    Write the method from scratch, i.e. do not use the classes
    Collections and Arrays. Use only the methods of the LinkedList class.

    A Solution:
    -----------

     // merge the 2 sorted lists list1 and list2 onto list
    // list1 and list2 are sorted in the increasing order
    // list must also be sorted in increasing order.
    // do not eliminate duplications
    public static <T extends Comparable< ? super T>>
            void merge(LinkedList<T> list1, LinkedList<T> list2,
            LinkedList<T> list)
    {

        // base case
        if (list1.isEmpty())
        {
            // copy list2 and return
            list.addAll(list2);
            return;
        }

        // base case
        if (list2.isEmpty())
        {
            // copy list1 and return
            list.addAll(list1);
            return;
        }

        // now we have recursion
        // get the heads of the two lists without removing them
        T item1 = list1.peek();
        T item2 = list2.peek();
        // compare the heads, enter the smallest into
        // list and remove from the list that belonged
        // if the heads are equal, enter from list1
        if ( item1.compareTo(item2) <= 0)
        {
            list1.removeFirst();
            list.add(item1);
        }
        else
        {
            // insert from list2
            list2.removeFirst();
            list.add(item2);
        }
        merge(list1,list2,list);
    }


    The program has the drawback that it changes list1 and list2.
    If you do not want them changed, write the method,

    public static <T extends Comparable< ? super T>>
       void mergeLists(LinkedList<T> list1, LinkedList<T> list2,
            LinkedList<T> list)
    {

         // copy the 2 list onto 2 new lists, l1 and l2
         LinkedList<T> l1 = new LinkedList<>();
         l1.addAll(list1);
         LinkedList<T> l2 = new LinkedList<>();
         l2.addAll(list2);
         // call merge
         merge(l1,l2,list);
    }

    Problem 2:
    ==========

    Write the method

    public static double getSecond(double[] arr)

    that computes the second largest number of arr.
    If arr is null or has less that 2 items then throw an illegal argument
    exception.

    For example, if arr = { 10.0, 30.0, 20.0, 15.0},

    getSecond(arr) must return 20.0 since 20 is the second largest value.

    If arr = { 10.0, 5.0, 0.0, 10.0}

    getSecond(arr) must return 10.0 because the largest number is 10.0 and
    the second largest number is also 10.0.

    Do NOT sort the array.

    A program:
    ----------

    // find the second largest value of the array arr
    public static double getSecond(double[] arr)
    {
       // check if arr has at least 2 numbers
       if (arr == null || arr.length <= 1)
           throw new IllegalArgumentException("less than 2 numbers");

       // initialize max and second to -Infinity
       double max = Double.NEGATIVE_INFINITY;
       double second = Double.NEGATIVE_INFINITY;

       // process the items of arr
       for ( double curr : arr)

            // see if curr > max
            if (curr > max)
            {
                // update both max and second
                second = max;
                max = curr;
            }
            else if (curr > second)
                // update only second
                second = curr;

        return second;
    }

    Excercise: Change it to work when double is replaced by <T extends Comparable<? super T>>.

    Problem 3:
    ==========

    Write the method

    public static <T> boolean isSublist(LinkedList<T> l1, LinkedList<T> l2)

    that takes as input two lists, l1 and l2, and returns true if l1 is
    a sublist of l2 and false if it is not. We say that l1 is a subslist
    of l2 if the elements of l1 occur in l2 in the same order in which
    they occur in l1, though the elements that are adjacent in l1 may
    not be adjacent in l2. For example,

    a, b, c is a sublist of b, a, c, b, a, c, b
                           -     -     -
    because the first list is formed by taking the underlined items of
    the second list.

    On the other hand

    a, b, a is not a sublist of b, a, c, c, b, c

    Let's see why. The second list must contain an a followed by,
    not necessarily immediately, by a b, and the b must be followed by an a.
    So, we must take the first a, and then the b that follows it. However,
    the b is not followed by an a, as shown below

    b, a, c, c, b, c
       -        -

    The method throws a null pointer exception if either l1 or l2 or both
    are  null and return trues if l1 is the empty list.

    Write the method below. Use good style and put comments.

    A Program:
    ----------

     // return true if l1 is a sublist of sublist of l2
    // l1 is a sublist of list if the items of sub occur in
    // the same order in l2. For example, a, b, c is a sublist of l2 if
    // there are 3 items with the values a, b, and c in this order
    // in list such that a precedes a and b precedes c.
    // throw a null pointer exceptione if either list is null
    public static <T extends Comparable<? super T>>
            boolean  sublist(LinkedList<T> l1, LinkedList<T> l2)
    {
        if (l1 == null || l2 == null)
            throw new NullPointerException("Null list");
        if ( l1.size() == 0)
            return true; // l1 is empty
        if (l2.size() == 0)
            return false; // l1 is not empty, but l2 is

        // get two iterators, one for list and one for sub
        ListIterator<T> it1 = sub.listIterator()B;
        ListIterator<T> it2 = list.listIterator();

        while (it1.hasNext())
        {
            // get the next item in sublist
            T item = it1.next();
            boolean found = false; // true if found in list1
            // look for item in list starting with the current position
            while (it2.hasNext())
            {
                T curr = it2.next();
                if ( curr == null && item == null || curr.equals(item))
                {
                    found = true;
                    break;
                }
            }

            if (!found)
                return false;
        }

        return true;

    }

    Problem 4:
    ==========

    Write the method

    public static <T extends Comparable<? super T>> void split(LinkedList<T> list, 
          T pivot, LinkedList<T> list1, LinkedList<T> list2)


    that empties list1 and list2 and then traverses list and puts 
    all items <= pivot in list1 and all items > pivot in list2. Do not modify list. 
    You may assume that the items of list are not null. However, list can 
    be null or empty.

    For example, if list contains the names
    "Bill", "Mark", "Ann", "Dan", "Laura", "Alex", "Norman", "Paul" 
     and pivot = "Laura",

     list 1 must contain
     "Bill", "Ann", "Dan", "Laura", "Alex"

     and list2 must be
     "Mark", "Norman", "Paul"

     Use the java.util.LinkedList class.

    A Program:
    ==========

    // split list into 2 lists list1 and list2
    // list1 contains the items <= pivot
    // list2 contains the items > pivot
    public static <T extends Comparable <? super T>> void
       split(LinkedList<T> list, T pivot, LinkedList<T> list1, LinkedList<T> list2)
    {
        // empty the two lists
        list1.clear();
        list2.clear();
        // start processing list
        ListIterator itr = list.listIterator();
        // while there items, process them
        while (itr.hasNext())
        {
            // get the next item
            T item = (T) itr.next();

            // process it
            if ( item.compareTo(pivot) <= 0)
                list1.add(item);
            else // add item at the end of list2
                list2.add(item);
        }

    }