Harvey Mudd College
Computer Science 60
Optional Extra Credit Assignment (Number 12)
Due Friday, May 10, by midnight

Assembly-Language Programming




The ISC (Incredibly-Simple Computer) and its machine language ISCAL (ISC Assembly Language) is described in Chapter 13 of the text (pages 637-680). This assignment is meant to introduce (or reintroduce) low-level programming with ISCAL.

The problem

The goal of this assignment is to write Quicksort in ISCAL. Quicksort is a fast, widely-used, general-purpose sorting routine. It sorts in O(n*log(n)) expected time, though the worst-case running time is O(n^2). You should call your quicksort program qsort.isc.

The real problem

Quicksort is most naturally expressed as a recursive algorithm. When writing in ISCAL, however, you're programming at a level in which function calls (and recursion in particular) do not exist. As a result, you will need to "implement" recursion. (Don't write an iterative version of quicksort -- after all, another purpose of this assignment is to demonstrate how recursion gets implemented.) The usual (and recommended) way to handle recursion is by maintaining a stack that holds the parameters of the unfinished recursive calls.

Help!

The following subsections describe how to use ISCAL in general, how to implement recursion, what the quicksort algorithm is, and provide a starting point for your code.

Programming in ISCAL

The ISC (incredibly simple computer) and its machine language ISCAL are described both in the text (Chapter 13, pp. 640-680) and on the reference page. The reference page also has a number of ISCAL code examples and directions on how to run programs.

Briefly, however, you can try out ISCAL with one of the example files in /cs/cs60/as/a12/ .

Copy any (or all) of the files from /cs/cs60/as/a12 to your own directory. Then you can run one of them, say fac.isc , by typing 

/cs/cs60/bin/isc fac.isc
If you put the directory /cs/cs60/bin into your path by typing 
  set path=($path /cs/cs60/bin)
you will then be able to type 
isc fac.isc

The program accepts integers entered one at a time to the standard input (the keyboard) and immediately prints out the factorial of each one. If you push the limits of the program you will discover some odd behavior (negative numbers or zero for inputs that overflow the 32-bit ISC limit).

A recursive example

In addition to fac.isc , there are several other ISCAL examples to work from. To demonstrate how to implement recursion, there is a file named 

rfac.isc
that does the same thing as fac.isc, but does so recursively. It demonstrates how to build up a stack that preserves the data needed for each recursive call. This code can't be copied wholesale for use in quicksort, but it does give the idea.

Don't start from scratch!

There is also a file named 

part.isc
in the directory /cs/cs60/as/a12 that implements all of the input/output routines you need, as well as the partitioning half of the quicksort algorithm. This file is a good starting point for creating your qsort.isc file.

Your quicksort can be built by modifying subroutine 'part' in part.isc. After partitioning the array, quicksort makes two recursive calls to itself. What you have to do is add the code for making these recursive calls.

Note that quicksort does not need to return a value; rather it modifies its argument array in place. It is recommended that the array be represented by pointers to the bottom and top locations in the array. (This is the way that 'part' is set up.) The subroutine 'part' also returns the pivot element as a value. This is not needed for quicksort.

The quicksort algorithm (in Java)

Quicksort is described in detail in the text (and there may be a couple of class sildes about it), but there is also a java-code version at 

/cs/cs60/as/a12/quicksort.java
After compiling it (it will compile but complain about the use of deprecated library calls -- don't worry about those), you will need to redirect a file of numbers to it when running, e.g., 
%  /cs/cs60/bin/random 10 >  mynumbers
%  java quicksort < mynumbers
/cs/cs60/bin/random is a program that outputs a list of randomly generated integers -- however many are specified in its argument.

Ultimately, however, you need not run the java quicksort; it is there simply as a guide to the algorithm.

Submission and grading

Submit your ISCAL file implementing quicksort with the usual cs60submit command, i.e., with 

% cs60submit qsort.isc
This assignment will be worth up to 50 points, but is graded "out of" 0 points, in that it's entirely optional.