Assignment 10: Sorting and Spampede (Starter)!
Due Tuesday 19th by 11:59 PM

Pair programming is permitted on all parts of this week's assignment.

This week you will work on implementing bubble sort, insertion sort, and selection sort in Prolog, Java, and Racket.

Sorting (65 points)

To reinforce some of the sorting algorithms you've learned in CS 60, you'll be implementing these sorting algorithms in each of the three languages from CS60.

In the hw10 directory you'll find:

• hw10p1.txt (change to .pl)
• hw10p1.rkt
• SortingStuff.java
• SortingStuffTest.java

The Java starter file provides the following method signatures. We are using the SortingStuff class, but do not plan to make SortingStuff objects and you will write the following static methods for the class.

	public static boolean bubble(int[] arr) {
	public static int bubbleSort(int[] arr) {
	public static void insert(int[] arr, int index) {
	public static void insertionSort(int[] arr) {
	public static int minIndex(int[] arr, int startIndex) {
	public static void selectionSort(int[] arr) {

The Racket starter file provides approximately half of the functions necessary for sorting. The following functions are provided: selectionSort, insertionSort, and bubble. You will write the following functions:

	min
	remove
	insert
	bubbleSort

The Prolog starter file provides approximately half of the predicates necessary for sorting. The following predicates are provided: min, remove, insert, and bubbleSort. You will write the following predicates:

	selectionSort 
	insertionSort 
	bubble

Test cases are provided for all of the sorting [methods/functions/predicates]. Before writing the code for any of these [methods/functions/predicates] you should provide comments describing why each test case is important. For example, you might describe the base case or corner case that a test checks. If there is important functionality that won't be tested by the provided test cases, you should add test cases. One purpose of this is to get familiar with what each of these [methods/functions/predicates] does before trying to figure out how it does that.

Part 2: Big-O running times...

35 points

For these questions, you will be analyzing the running time of algorithms. We will be interested in worst-case analysis. You will need to express the worst-case running time using big-O notation. In addition to your answers, be sure to show your reasoning for each of the problems in the hw10pr2.txt file (just as ASCII text).

Submitting these answers    Include your answers to these problems in the hw10pr2.txt file.

• Question #A
  What is the big-O running time of this portion of code, in terms of n? Explain your analysis clearly and carefully. (Notice how i is increasing!)

          for (int i=1 ; i≤n ; i *= 2)
             for (int j=0 ; j<i ; ++j)
                // constant time work here
          

• Question #B NEW: This problem is now extra credit!
  What is the big-O running time of this portion of code, in terms of n? Explain your analysis clearly and carefully. (Notice how j is increasing!)

          for (int i=1 ; i≤n ; ++i)
             for (int j=1 ; j<i ; j *= 2)
                // constant time work here
          

• Question #C
  Identify the runtime of reverse (below). You must use the fact that append runs in time O(N), where N is the length of the first input to append.

  			(define (reverse L)
  			   (if (null? L)
  				 '()
  				(append (reverse (rest L)) (list (first L)))))
  		

• Question #D
  Below is the code for prefix from Hw1. Identify the big-O runtime. (Remember to define the variables you use in your runtime!!!)

  		(define (prefix? P L)
  		  (cond [(null? P) #t]
  				[(equal? (first P) (first L)) (prefix? (rest P) (rest L))]
  				[else #f]))
  		(check-expect (prefix? '() '(s p a m))   #t)
  		(check-expect (prefix? '(s p) '(s p a m))   #t)
  		(check-expect (prefix? '(s m) '(s p a m))   #f)
  		(check-expect (prefix? '(p a) '(s p a m))   #f)
   		

• Question #E (This question was removed because the code I posted was incorrect - Colleen)
  Below is the code for sublist, which calls prefix. Describe an example of a three-element list S and a six-element list L that require (sublist? S L) to do the most work (the most equality-comparisons). In other words, what inputs cause the largest number of equality-comparisons between elements to be made?

  		(define (sublist? S L)
  		  (cond ((null? S) #t)
  				((null? L) #f)
  				((prefix? S L) #t)
  				(else (sublist? S (rest L)))))
  		(check-expect (sublist? '() '(s p a m))   #t)
  		(check-expect (sublist? '(s p) '(s p a m))   #t)
  		(check-expect (sublist? '(s m) '(s p a m))   #f)
  		(check-expect (sublist? '(p a) '(s p a m))   #t)
  		(check-expect (sublist? '(a b c) '(b a b a c))  #f)
  		(check-expect (sublist? '(a b c) '(b a b c c))  #t) 		

• Question #F
  Dude - this relies on sublist too! Whoops! Also, suppose that -- in general -- the inputs to sublist? are of length N and 2N, respectively. In this case, what is the resulting worst-case big-O running time of your sublist? function?
• Question #G: Stooge Sort!
  
  Larry, Mo, and Curly have designed a new StoogeSort sorting algorithm that works as follows on an array of N elements:
  • If the input list has 0 or 1 elements, it's already sorted - just return it.
  • If it has 2 or more elements:
    • recursively use StoogeSort to sort the first N-1 elements, leaving the final element untouched at the back of the list
    • afterwards, recursively use StoogeSort to sort the last N-1 elements, leaving the first element untouched at the front of the list
    • finally, after both these steps, compare the first two elements of the resulting list. If they're out of order, swap them; if they're in order, don't do anything.
  Remarkably, StoogeSort actually sorts! But the stooges are not sure of its run-time.

  So, for this algorithm, write a recurrence relation that captures its running time in terms of the number of comparisons made. Then, "unwind it" in order to find the running time of this sorting algorithm:

            T(1) = 0      # no comparisons if the list is 1 element long (or 0)
            T(N) = something
          

  Use the "unwinding" technique we developed in class to determine the big-O running time for this function, in terms of the input size, N.

Extra Credit

Using the List class from Homework 6, implement and test:

• Quick Sort (10 points)
• Bubble Sort (10 points)

You will turn in both List.java and ListTest.java. Half of the points will be based upon your thorough testing of the sorting method and testing any helper methods you write. Please use the following signatures. Your methods should modify the List. You shouldn't create any new ListNodes (i.e., you shouldn't call new ListNode()), but you may create additional ListNode references. You may create additional Lists (i.e., you can call new List()).

	public void quickSort()
	public void bubbleSort()