The requsite source code is attatched:

public class LinearNode{ private LinearNode next; private Item element; /** * Creates a node storing the specified element. * @param elem element to be stored */ public LinearNode(Item elem) { next = null; element = elem; }

/** * Returns the node that follows this one. * @return reference to next node */ public LinearNode getNext() { return next; } /** * Sets the node that follows this one. * @param node node to follow this one */ public void setNext(LinearNode node) { next = node; } /** * Returns the element stored in this node. * @return element stored at the node */ public Item getElement() { return element; } /** * Sets the element stored in this node. * @param elem element to be stored at this node */ public void setElement(Item elem) { element = elem; } }

public class ListQueue implements Queue, Comparable{ LinearNode tail; //back LinearNode head; //front private int count; private int modCount;

public ListQueue() { tail = null; count = 0; }

@Override public boolean isEmpty() { return count == 0; }

@Override public void enqueue(Item item) { LinearNode newNode = new LinearNode(item);

if(isEmpty()) head = newNode; else tail.setNext(newNode); tail = newNode; count++; modCount++; }

@Override public Item dequeue() { if(isEmpty()) throw new NoSuchElementException();

Item result = head.getElement(); head = head.getNext(); count--; modCount++; if(isEmpty()) tail = null;

return result; }

@Override public Item front() { if(isEmpty()) throw new NoSuchElementException();

return head.getElement(); } @Override public String toString() { LinearNode iter = head; String result = ""; while(iter != null) { result = iter.getElement() + " " + result; iter = iter.getNext(); } return result + "(front)"; }

@Override public int size() { return count; } @Override public int compareTo(Item i){ return ((Comparable)this.front()).compareTo(i); } @Override public Iterator iterator(){ return new LinkedListIterator(this); } /** * LinkedIterator represents an iterator for a linked list of linear nodes. */ private class LinkedListIterator implements Iterator { private final int iteratorModCount; // the number of elements in the collection private LinearNode current; // the current position /** * Sets up this iterator using the specified items. * * @param collection the collection the iterator will move over * @param size the integer size of the collection */ public LinkedListIterator(ListQueue o) { current = head; iteratorModCount = modCount; } /** * Returns true if this iterator has at least one more element * to deliver in the iteration. * * @return true if this iterator has at least one more element to deliver * in the iteration * @throws ConcurrentModificationException if the collection has changed * while the iterator is in use */ @Override public boolean hasNext() throws ConcurrentModificationException { if (iteratorModCount != modCount) throw new ConcurrentModificationException(); return (current != null); } /** * Returns the next element in the iteration. If there are no * more elements in this iteration, a NoSuchElementException is * thrown. * * @return the next element in the iteration * @throws NoSuchElementException if the iterator is empty */ @Override public Item next() throws ConcurrentModificationException { LinearNode previous = null; if (!hasNext()) throw new NoSuchElementException(); Item result = (Item)current.getElement(); previous = current; current = current.getNext(); return result; } }

}

public interface Queue extends Iterable{ /** * Add an item. * @param item an item */ public void enqueue(Item item); /** * Remove the least recently added item. * @return an item */ public Item dequeue() throws NoSuchElementException; /** * Return, but do not remove, the most least added item. * @return an item */ public Item front() throws NoSuchElementException; /** * Is the queue empty? * @return if empty */ public boolean isEmpty(); /** * Number of items in the queue. * @return number of items */ public int size(); public Iterator iterator(); }

public class BaseMerging { /** * Entry point for sample output. * * @param args the command line arguments */ public static void main(String[] args) { Queue q1 = new ListQueue(); q1.enqueue("T"); q1.enqueue("R"); q1.enqueue("O"); q1.enqueue("L"); q1.enqueue("E"); Queue q2 = new ListQueue(); q2.enqueue("X"); q2.enqueue("S"); q2.enqueue("P"); q2.enqueue("M"); q2.enqueue("E"); q2.enqueue("A"); System.out.println(q1.toString()); System.out.println(q2.toString());

//Q1 Queue merged = mergeQueues(q1, q2); System.out.println(merged.toString()); //Q2 String[] a = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"}; sort(a);//Java is pass by value only. Can't be Comparable[] a1 = mergeSort(a); System.out.println(isSorted(a1)); System.out.println(isSorted(a)); show(a1); //Q3 String[] b = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"}; shuffle(b); show(b); shuffle(b); show(b); } public static Queue mergeQueues(Queue q1, Queue q2) { Queue aux = new ListQueue(); while((!q2.isEmpty()) || (!q1.isEmpty())) { if (q1.isEmpty()) while(!q2.isEmpty()) aux.enqueue(q2.dequeue()); else if(q2.isEmpty()) while(!q1.isEmpty()) aux.enqueue(q1.dequeue()); else if(((Comparable)q1.front()).compareTo(q2.front()) 0){ aux.enqueue(q1.front()); q1.dequeue(); } else { aux.enqueue(q1.front()); aux.enqueue(q2.front()); q1.dequeue(); q2.dequeue(); } } //TODO: implement this. return aux; }

public static void sort(Comparable[] a){ Comparable[] b = a; b = mergeSort(a); } //helper public static Comparable[] mergeSort(Comparable[] a) { //base case if(a.length 0){ aux[indexAux] = b[indexR]; indexR++; indexAux++; } //The two values in the array are equal else{ aux[indexAux] = a[indexL]; indexAux++; aux[indexAux] = b[indexR]; indexAux++; indexL++; indexR++;

} } else if(indexL = b.length){ aux[indexAux] = a[indexL]; indexAux++; indexL++; } else if(indexR = a.length){ aux[indexAux] = b[indexR]; indexAux++; indexR++; } } return aux; }

public static void shuffle(Object[] a) { //TODO: implement this. }

//sorting helper from text private static boolean less(Comparable v, Comparable w) { return v.compareTo(w)

//sorting helper from text private static void show(Comparable[] a) { for (Comparable a1 : a) System.out.print(a1 + " ");

System.out.println(); } //sorting helper from text public static boolean isSorted(Comparable[] a) { for (int i = 1; i Background In order to practice divide and conquer algorithms, we will apply the idea to sorting and other tasks. Your goal is to first create a method that uses the merge concept to integrate two queue ADTs. Second, you will implement mer gesort from scratch to ge a better understanding of its divide and conquer (D& C) natur Lastly, you will create an O(nlogn) algorithm for shuffling an input array Divide and Conquer algorithms are conceptually similar to the recursive programming technique we saw earlier in the course. The idea is to break apart a problem into multiple (large) pieces. For example, the half of an array, and then the second half of an array. In terms of recursion, we might save that the sub-problem /2. This contrasts with the standard n 1 size of many recursive a Size n e of work is accomplished during each call. In general, D&C algorithms require multiple recursive calls while simple recursion, like summing or displaying a list, requires only a single call. D& C algorithms are often more complicated to write than simple recursive algorithms, but, the extra work pays off because D&C algorithms can end up with logarithmic Big-Oh factors instead of linear factors. This is why mergesort is an O(nlogn) algorithm This document is separated into four sections: Background, Requirements, Testing, and Submission You have almost finished reading the Background section already. In Requirements, we will discuss what is expected of you in this homework. In Testing, we give some basic suggestions on how the code may be ted. Lastly, Submission discusses how your source code should be submitted on BlackBoard 2 Requirements 135 points] In this programming project you willpractice the implementation of D&Calgorithms. Download the attached base files for a starting place; they include some very simple testing code. You may modify the base file with your answers for all three questions. However, please retain the signatures of the two stub methods and make sure you keep a of your code in the base file. Also attached is Sorting.java, which includes the textbook's sorting algorithm implementations for reference. The LinearNode, List Queue, and Queue classes should not be modifi (Sedgewick and Wayne: 2.2.14) Merging sorted queues Develop a static method that takes two queues of sorted items as arguments and returns a queue that results from merging the queues into sorted order. Emptying the input queues is fine. If you need to make any assumptions about the typing of the contents of the queues, please state them in a comment. I10 pointsl Reimplement the mergesort algorithm to pass only arrays as parameters. This should include a helpe mergesort (Comparablell a and a merge method, public static method, public static Comparable Comparable merge(Comparable a, Comparablell b). Do not use global or class variables (Note that this approach is slower than the mergesort from the book. The goal is to better understand the mergesort concept.) I15 pointsl public static void shuffle (objectll a), that shuffles an array in nlo g(n) time using Implement a method, a merging action. Assume calls to the Random library happen in constant time. It should be possible for any element to re-position to any other position. Include a comment explaining why your algorithm uns in nlogn time. I10 points