:::::  Homework Assignment #3  :::::

Due Wednesday, November 18, 2009 by midnight! 


*** All work has to be done individually! ***


Theme : Comparison of sorting algorithms


  In this homework, you will describe, implement, and compare the actual performance of three sorting algorithms. 

  Here are the sorting algorithms you should work on:

  1) selection sort
  2) merge sort 
  3) count sort 

  We didn't cover selection sort and merge sort in class. You will have to do some research to find out how they work. Count sort was covered in class. 

  There are four parts to this homework.

  1) Describe the algorithm (written)
    Describe how each sorting algorithm works and what their complexity are in big-O notation. 

  2) Implement them (programming)
    Here, you have to implement each algorithm. 
    Use the sort.c file provided. 

  3) Measure the performance of each algorithm using a profiler (run it)
    We'll use a profiler to measure the time each algorithm took. 
    A profiler is a programming tool that records time spent on each function. 
    Since we're implementing algorithms in a function, we'll use the profiler to measure the time it took for the algorithm to run. 

    The name of the profiler we'll use is called gprof. 

    To use it, you need to do three things.
     a) compile sort.c with the -pg option. 
        # gcc -pg -o sort sort.c

     b) run sort
        # ./sort

        This will create a file called gmon.out.

     c) run gprof and store the output in prof.out
        # gprof ./sort > prof.out


     The performance metrics you're looking for is in the prof.out file. 

     In this file, look at the "flat profile" section which is the top of the file. 
     You'll see columns like "% time", "cumulative seconds", "self seconds", etc.
     The last column "name" is the name of the function. 

     The relevant columns for this homework are "calls", "total ms/call", and "name". 

     Here's a link for more information about gprof.
     http://www.cs.utah.edu/dept/old/texinfo/as/gprof.html


  4) Do some experiments and write a short discussion on what you expected and what you found. (written)
    Run your sort program with MAX_SIZE of 2500, 50000, and 100000.
     (The last one may take some time to run to completion.)
    Explain how the running time changes for each algorithm. 

    In part 1, you did research on the computational complexity (Big-O notation) of each algorithm. 
    Compare this with your actual running times of each algorithm. 
    Does the Big-O notation correctly represent the difference in algorithm performance? 
    Explain why or why not. 


 What to submit:

  1) sort.c : your implementation of sorting algorithms.
  2) written.txt: your written answers for part 1 and part 4
  3) 3 prof.out files: from running sort with MAX_SIZE = 2500, 50000, and 100000

    


 Grading:

  Your homework will be graded out of 100 with the following breakdown:

  - Part 1 (20 points)
     - 5 points each for selection sort and count sort
     - 10 points for merge sort

  - Part 2 (50 points)
     - correctness of implementation (35)
     - neatness and comments (15)

  - Part 3 (0 points)

  - Part 4 (30 points)
     - Write a good evaluation of your experiment



 
How to submit:
  1) make a directory called homework3
  2) copy or move your report, prof.out files, and source code file to homework3.
  3) 'cd homework3' to get into that directory
        make sure you check that you're in homework3 by issuing a 'pwd' Unix command.
  4) Type '~jk2520/submit hwk3' in shell prompt.
     For example, this is what it'd look like with the CUNIX shell prompt, 
          $ ~jk2520/submit hwk3
 
     The submit script will ask some questions and let you submit homework.
     You will receive a confirmation email if the homework was submitted properly.