Assignment 10

Harvey Mudd College
Computer Science 60
Assignment 10, Due Friday, November 17, by midnight

Algorithmic Complexity: Sorting in prolog, rex, and Java.

Problem 1: Sorting in prolog (10 pts.)

Although the sorting algorithms we've discussed have all been in either a functional setting (rex) or an imperative one (Java), it is possible to write a prolog predicate that "sorts" a list.

For this problem, write a predicate minsort( U, S ) that takes two lists as arguments. U, the first argument, is a (potentially) unsorted list of integers. (You need not worry about anything but integers.) S, the second argument, is a sorted list of integers that contains the same elements as the first argument, U.

Your predicate does not have to work when given a variable as the first argument. However, it does need to work when given a variable as the second argument, and when no variables are given. For example, the following are typical runs:

?- minsort( [3,5,1,7], [1,3,5,7]).

yes


?- minsort( [7,11,5,2,3], X ).

X = [2,3,5,7,11] ;

no.

Hints: Calling something a "minsort" algorithm in prolog is not entirely accurate, as prolog does everything in essentially the same way: depth-first search through its rules until it finds satisfying values for variables.

However, one reason this predicate is called minsort is that you may want to implement it in two rules:

A base case (to handle empty lists).
A recursive case. In one implementation the left hand side of this rule might be
```
       minsort( U, [F|R] ) :- ...
       
```

Notice that F must be the minimum of the list [F|R]. You may want to use other predicates we've talked about or written in previous assignments. (Solutions to Assignment 9 will be in /cs/cs60/as/a9 by Monday.)

Keep your minsort predicate (and other predicates it uses) in a file named minsort.pl .

Problem 2: Swapsort in Rex (10 pts.)

Part A

Often it's possible to write more efficient algorithms to solve problems whose input is known to be constrained in some way. For example, suppose you need to write a list-sorting algorithm (returning lists in ascending order), but that the lists you need to sort are guaranteed to be almost sorted already. In fact, the only way in which list elements are out of order is that several nonoverlapping pairs of elements might be swapped.

For instance, the following are lists that you might need to sort:

[1,3,2,4,5,7,6]            (2 swaps)

[2,1,4,3]                  (2 swaps)

[6,7,8,9,11,10]            (1 swap)

On the other hand, you will not need to sort lists where more than two elements are adjacent and out of order. That is, these are examples of lists you don't need to worry about:

[3,2,1]                    (3 consecutive elements out of order)

[1,2,12,10,11,15]          (3 consecutive elements out of order)

[4,2,3,1,7]                (4 consecutive elements out of order)

Write a rex function swapsort2(L) that sorts lists (L) of the type described in the first set of examples above. Remember that you can assume that swapsort2 will only take in lists of the appropriate type. You don't need to do error checking to be sure the lists are appropriate inputs. Here's an example:

swapsort2([1,2,6,5,10,11,14,12]);

[1, 2, 5, 6, 10, 11, 12, 14]

Place your code into a file named swapsort.rex.

Note: this program is not difficult so, if you find it easy, don't think you've missed something -- you haven't.

Part B

As a comment in your swapsort.rex file, include the following information:

First, write the recurrence relation for the swapsort2 function. You may assume a worst-case input as you write the recurrence relation.
Second, state the running time (with big-O notation) of your swapsort2 function in terms of the length of the input, N. Explain in a sentence or two how you found your solution. Consider the worst-case running time, and count only the comparisons between list elements.
Finally, explain how the running time change if the inputs could have at most 3 (instead of 2) adjacent elements that were unordered? As examples, the first two lists shown above that are invalid inputs for swapsort2 are valid inputs for swapsort3. In other words, what would the running time be of a swapsort3 function? How about a swapsort4 function? A swapsortN function?

Problem 3: Mergesort in Java (20 pts.)

Note: the last 10 points, as usual, are for style and commenting on all three sorting programs

For this problem, you will write the mergesort algorithm in Java and then analyze its running time. (Just for the record, mergesort runs in O(n*logn) time.)

Files to create/modify

You will want copy the Mergesort.java file from /cs/cs60/as/a10. In that file, you will find a simple linked list class (with the ability to generate long lists of "random" floating-point numbers between 0.0 and 1.0.

The file you submit will be the Mergesort.java file, with the code for mergesort completed in the Mergesort class, and an analysis of your program's running time within a java comment.

Part 1: coding mergesort

The skeleton provided in Mergesort.java has a placeholder (that currently does nothing) named mergesort as follows:

static List mergesort(List list, long length)
{
  return list;
}

You will need to fill in code that implements mergesort using the simple List class provided. We are not using the Java LinkedList class in order to be certain of the operations being performed in each step through the algorithm.

Also, because the fast running time of mergesort requires that duplicate data not be created, you should follow these guidelines:

Do not use the constructor for the List class, except to create the initial list filled with "random" values. That is, don't create new Lists, just modify the original one.

Do not allocate or use any more space than necessary. That is, you can allocate new references to lists, but avoid copying lists. (A new list reference is small and takes almost no time to create, but copying an entire list could potentially be very costly.)

Do modify the list passed into mergesort by manipulating the reference links that comprise the list. Basically, you are taking advantage of side effects to save space and time.

You should perform three steps in your mergesort algorithm:
1. Split of the input list into two equal or almost-equal halves.
2. Recursively sort the two lists.
3. Merge the two sorted lists back into a final list that gets returned.

Notice that the rex code provided in the notes "skips over" the initial split (with a call to map), but the split is critical in the Java implementation.

Part 2: analyzing mergesort

In a comment inside your Mergesort.java file, include an analysis of the running time of your mergesort algorithm. You will need to write a recurrence relation (because mergesort should be recursive). In your recurrence relation you only need to worry about counting comparisons between list elements. Once you have the recurrence relation, "unwind" it to show that the running time is, indeed, O(n*log(n)). In your analysis, you may assume that n, the number of elements in the list to be sorted, is a power of 2.

Reading

Complexity and its analysis is covered in Chapter 11 of the text.

Submission

You should submit your Mergesort.java, your swapsort.rex, and your minsort.pl source files in the usual way, i.e., by running

% cs60submit 10

Extra Credit

1. For optional bonus credit (up to 10%), consider the following "Totally Excellent" (?) Sorting Algorithm! (with acknowledgements to creator Ran L-Hadas): Professors Curly, Mo, and Larry of the Pasadena Institute of Technology have proposed the following sorting algorithm called Stoogesort: First use recursion to sort the first two-thirds of the elements in the array. Next use recursion to sort the last two thirds of the array. Finally, use recursion to sort the first two thirds again.

Write down the recurrence relation for the running time of Stoogesort. Solve this recurrence relation using the unwinding technique. Carefully show all the steps in your unwinding analysis. You may assume that n (the length of the array to be sorted) is equal to (3/2)^k for some k. (Here the ^ symbol means "to the power of.")
Express the running time of Stoogesort as O(n^x) where x is some real number. Give the actual value of x.
How does the running time of this algorithm compare to that of Mergesort? Is it better or worse? Explain your answer carefully.

Type your answer to this question as a comment in your Mergesort.java file. If you prefer to write it on paper (writing mathematical symbols is easier that way), you may hand it in under the door of Olin 1265 by midnight on Sunday, November 19.

2. A second optional bonus credit problem (up to 10%) is to write a prolog version of minunsort(U, S). minunsort does the same thing as minsort (Problem 1, above), except that the first argument can be a variable. Your minunsort predicate does not have to work correctly, however, if the second argument is provided with a variable. Thus,

?- minunsort( U, [1,2,3] ).

U = [1,2,3] ;

U = [1,3,2] ;

U = [2,1,3] ; 

U = [2,3,1] ; 

U = [3,1,2] ; 

U = [3,2,1] ; 

no

Repeated values for U are acceptable. The minunsort predicate should be submitted in your minsort.pl file

Harvey Mudd College Computer Science 60 Assignment 10, Due Friday, November 17, by midnight