CMSC 246 Systems Programming
Spring 2021

Assignment #3
Due March 10 before 11:59:59

1. Random Numbers utility
   Write a program that takes a single command line parameter -- an integer -- call it N. The program then generates N random numbers, one number per line, in the range 0-N (including both 0 and N in the range). For instance, if the name of the compiled executable is rr, then a trace of this program might look like:

   [gtowell@powerpuff HW3]$ rr 5
   4
   3
   5
   4
   0
       

2. Pipe reader Write a program to read integers from a unix pipe and store those integers in an array. The array should be statically allocated in the global space and should be able to store at least 50,000,000 integers. (This array MUST be in the global space.)
3. Implement Quicksort
   
   Pages 207-209, Chapter 9, of King's book provide an implementation of the Quicksort algorithm. Study the algorithm carefully and then implement it. You implementation should be done within the pipe reader program written in the previous part. That is, your impementation must sort the array read by your pipe reader. Also your implementation should take advantage of the fact that the array is stored as a global.
   
   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. For instance, your output might look like -- for N=6.

     [gtowell@powerpuff HW3]$ rr 6 | ss
     Read: 6
     0 3
     1 3
     2 3
     3 4
     4 1
     5 1
     
     SORTED
     ======
     0 1
     1 1
     2 3
     3 3
     4 3
     5 4
   

4. Evaluating Quicksort
   
   Once you have completed the previous step, modify your sorting algorithm so that its only output is the time required for sorting (using the timing function discussed in class).

   Create a shell script to collect data from at least 30 trials for a well chosen set of sizes of sorted lists. For example, for a simple selection sort, your data points might be for 10000, 20000, 40000, 80000, 160000, 320000 and stopping there because 160000 takes about 30 seconds (on powerpuff). Compute the mean and standard deviation of each of your runs. For quicksort you r sizes will be MUCH larger, maybe 50 million or more on the upper end.

   Here is a useful start for your shell script

         #!/bin/bash
         for ((n=0;n<5;n++))
         do
          if [[ $n -eq 0 ]]
          then
             rr 20 | ss > res20file
         else
             rr 20 | ss >> res20file
         fi
         done
       

   This shell script will run my random list (executable named rr) and sort (executable named ss) 5 times putting the output into a file name "res20file". The first time will create "res20file", eliminating everything that might previously have been in "res20file". Subsequently it will append to "res20file".
   To make a shell script copy the above into a file in the same directory as your other executables, suppose you name that file "shelly". Then execute the following Unix command

       chmod 777 shelly
     

   (We will get to chmod.) Having done that you should be able to use the script like:

       ./shelly
     

   which if you copied, without editing, my script above would create a file named res20file. You can edit the script file and run it without recompiling. You are not required to use a script file as outlined above. However, it is by far the easiest way to complete the assignment.
   Draw a graph (hand drawn graphs -- on graph paper -- are acceptable) showing your data. Each datapoint on your graph should be the average of at least 30 trials for a given sample size. Show mean and standard deviations on your graph using a box and whiskers format. Be careful and aware of the fact that you are on a multiprocessor machine. Be sure to label everything clearly and choose your axes appropriately.
5. Improving Quicksort
   One of the best (and easiest) ways of improving the performance of Quicksort is to stop recursion when the size of the split goes below about 15. Then, after Quicksort completes, run insertion sort on the entire partially sorted array.
   Implement this modification of Quicksort.
   Collect data akin to the data collected above and include these points in your graph. Label these points something likely, for instance "Hybrid Quicksort".

Scripting in Linux
Note that "scripting in linux" is quite distict from "shell script"as described above
Once done, you will need to show the 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 each of the above 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 hand in:

• all the program files
• the script file showing one run of your program (from part 3) that shows that you implementationof quicksort works correctly
• Graphs showing the data from parts 4 and 5. (Possibly only one graph.) If hand drawn take a picture and include that
• The usual README

How to Hand in:

  /home/gtowell/bin/submit -c 246 -p N -d aN