CMSC 246 Systems Programming
Fall 2019

Assignment #3
Due Friday, Sept 27, 2019 prior to 11:59pm

  1. Implement Quicksort

    Pages 207-209, Chapter 9, of King's book provides an implementation of the Quicksort algorithm. Study the algorithm carefully and then implement it. Your implementation must be able to sort an array of N integers, where N is a positive integer and where N is provided as a command line arguement to the program. Rather than getting N integers from the keyboard as in the book's implementation, write a function that draws N random number in a fixed range large enough so that there are few duplicates; for example 0-1000000.

    Provide a script showing that your implementation of Quicksort correctly sorts an array when N=15. To do this, print the array before and after sorting.
  2. Evaluating Quicksort

    Collect data from runs of Quicksort (using the timing function discussed in class (Sept 23)) to verify that Quicksort is, indeed, an NlogN algorithm. Because of the limited accuracy of timing and the speed of the computer, you will likely need to sort very large lists. The shortest runtimes you should use should be more than 1 second.
    Draw a graph showing your data. (Use whatever graphing software works for you, probably a spreadsheet. Hand drawn graphs -- on graph paper -- are acceptable). Each datapoint on your graph should be the average of at least 30 trials. Show mean and standard deviations on your graph. Be careful and aware of the fact that you may be on a machine being used by several people. (Do not use powerpuff for timing.) Be sure to label everything clearly and choose your axes appropriately.

    For ease of data collection it is acceptable to code values of N into the program for parts 2 and 3 (and thus, recompile between trials).

  3. Improving Quicksort

    Pages 208-209, Chapter 9, of King's book describe 3 ways of improving Quicksort. Pick one and implement it. As an alternative, replace the book's array index notation with pointer math. Or come up with some other likely technique for speeding up quicksort.
    Collect data with your "improved" algorithm that exactly mirrors the data from part 2. Draw a new graph that highlights the differences in speed between the original and your improved algorithm. Run t-tests (Sept 23) on your data to show that your improved algorithm differs (or not) from the original. (Your improvement may actually slow things.)
    Write a brief (1 paragraph-ish) analysis of your modification to Quicksort that describes exactly what you did and why you would expect that change you made to improve Quicksort's speed. ("Because the book said it would" is not a sufficient answer. Nor is "Knuth said so", or any of the other 36 methods discussed in class.) If your results shows no change (or a negative improvement) speculate on why this occurred.

Scripting in Linux
Once done, you will need to show sample runs of programs, as required above. In order to record the runs, you can use the Linux command script.
Go to your Assignment directory and enter the command: script session

You will get your command prompt back. Next, run the programs as you normally would. Once done, enter the command: exit (or CTRL-D)

This will end your script session. If you now look a the contents of the session file, you will see that the entire interaction has been recorded in it (as a script!).

What to submit:

Collect together is a single directory all of the following: When you have everything ready in this directory go to the directory containing the one with the information you want to submit. For instance, suppose that the files specified above are in /home/YOU/cs246/a3. Then you should go to /home/YOU/cs246.
Use the submit program as follows:
  /home/gtowell/bin/submit -c 246 -p 3 -d a3
This will package up everything in the directory a3 and submit it under your login name along with a timestamp of your submission date.

Back to CMSC246 Home page