Harvey Mudd College
Computer Science 60
Assignment 11, Due Thursday, April 13, 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:
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 10 will be in
/cs/cs60/as/a10 by Monday.)
Submit 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.
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.
- 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 and Empirical Complexity Analysis (20 pts.)
For this problem, you will write the mergesort algorithm in Java and then test
its running time empirically in order to validate that it runs in
n*log(n) time, rather than O(n) or O(n^2).
Files to create/modify
You will want copy the Mergesort.java file in
/cs/cs60/as/a11.
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 inserted into the
Mergesort class, and a table of running times vs. problem
sizes (see the model table below) 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)
{
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 need to follow these guidelines:
- Do not use the constructor for the List class, except
to create the initial list filled with "random" values.
- 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:
- Split of the input list into two almost-equal halves
A good way to do this is to create two new lists and
add pointers alternatively to each from the original.
See the picture below for an illustration.
Feel free to add the pointers in reverse order, if you
like (this actually makes the split easier to code).
- Recursively sort the two lists.
- Merge the two sorted lists back into a final list that
gets returned.
- Notice that the above guideline performs a split, then a sort,
then a merge step. The rex code provided in the notes "skips
over" the initial split (with a call to map), but it's important
in the Java implementation.
Be sure you test your code so that you know that mergesort is
working before going on to the empirical analysis of its running
time (the next part of the problem).
Here is the illustration of one way to split a linked list.
Part 2: analyzing mergesort
For this part, you will need to use the code provided (in a comment
in the main method) in Mergesort.java
to test your mergesort algorithm (from Part 1) on lists of various sizes.
By uncommenting the code in main,
you should create a table of the following form. The three columns
list the running time of your mergesort algorithm divided by
N, Nlog(N), and N^2, respectively, for
the various list lengths (N) shown to the left. Note that
T(N) represents the actual running time of your
mergesort algorithm (in milliseconds) on a list of size N.
The values represent the wall clock time, not
the processor time, but it should be a good enough approximation to use.
Note: Be sure to include your table of running times
in a comment inside your Mergesort.java file.
T(N) T(N) T(N)
list ----- ------- -----
length (N) N Nlog(N) N^2
N = 512
N = 1024
N = 2048
N = 4096
N = 8192
N = 16384
N = 32768
N = 65536
N = 131072
N = 262144
N = 524288
N = 1048576
Warning : when you submit Mergesort.java, comment
out the table-building code and leave in the
original list sorting code. We will use the latter for testing.
Once the table has the above values filled in (within a
comment in your Mergesort.java file), explain in a comment at the top of
the file what the values in the table indicate about the
asymptotic running time of mergesort.
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
You will be asked to input the assignment number (11).
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. (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.
You may type the answer to this part into a file named stoogesort.txt
and submit it with cs60submit (Assignment 11) or hand it in
on paper to Olin 1245 by 6:00 pm Sat., April 15.
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