CMSC 246 Systems Programming
Fall 2019
Assignment #3
Due Friday, Sept 27, 2019 prior to 11:59pm
- 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.
- 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).
- 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:
- README file. This is a file literally named README. This file should follow the format of https://cs.brynmawr.edu/Courses/cs246/fall2019/README.txt Your README should clearly show the two versions of quicksort (as specified below).
- Your quicksort program from part 1, taking command line args for the size of the array to be sorted
- Your quicksort program, with improvements. Be sure to indicate with comments exactly where your "improvements" are
- The analysis described in part 3. Ideally this would be in PDF format and would include the graphs from parts 2 and 3. A text file is also acceptable. Other formats will not be read with the result that the report will receive 0 credit.
- Graphs. If you hand draw graphs, they may be turned in on Monday at the start of class. Otherwise the graphs may be included in a pdf file along with your report (which likely refers to the graphs). If not in a pdf file, then the graphs should in a image file format viewable on one of the computers in the lab using only software that is available on lab computers (e.g. jpg, png, gif, ...) I you will be turning in hand drawn graphs, but sure to indicate this in the README file. Also, you may submit photos of hand drawn graphs, but be sure they are legible.
- Do NOT include compiled code.
- Do NOT include emacs temp files, or the temp files of any other program. For emacs these are of the form xxxx~ and #xxxx#
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