CSCI 385 Fall 2015
Advanced Data Structures and Algorithms		Archived Class
Charles Cusack
Computer Science
Hope College
Main
Schedule
Grading
Gradebook
Policies
College
    Policies
Advice
Notes
Programs
Tutorials
CSCI 125
CSCI 255
MATH 341
Others
Admin

Homework 12

Details

Note: You may work in teams of 2 on this project if you wish. But if you do, you must do pair-programming! In other words, you must work side-by-side on the coding instead of trying to divide-and-conquer. If you plan to implement quicksort, I highly recommend working in pairs.

Implement either Mergesort or Quicksort using the algorithm given in the SIPC notes. Run tests to compare it with an optimized serial version and your naive parallel version from HW 9 (which you are welcome to improve a bit if you wish). Zip up your Sorting directory and submit it using Web handin as usual.

Here are some resources you might find helpful

  1. SPAC_CPP.pdf A version of the Parallelism and Concurrency written for OpenMP instead of Java.
  2. OpMPSorting My OpenMP version of parallel sum, parallel-prefix sum, and a start of the pack and partition algorithms. Feel free to use as you wish, but give credit! Use the Download Zip file link to download all of the files. The zipfile also includes two test cases for the runSorts algorithm and the results of my algorithm on those test cases.

Submit a hard-copy of a write-up that includes the following. (Please take the write-up seriously and don't just throw it together at the last minute.)

  1. A chart that compares the performance of the various algorithms. At a minimum, both parallel algorithms should be run on 1, 2, 4, and 8 threads. If you have access to a machine with more cores, run in on that as well.
  2. Discuss how the algorithms compare with each other. Is the new-and-improved algorithm better than your naive one? If not, explain why you think it is the case. Discuss what would happen if you had a lot more processors.
  3. Grade yourself out of 20 points, providing a clear justification.

If you are unable to complete the implementation of quicksort, you may receive up to 13/20 points for a proper implementation of pack and up to 16/20 points for a proper implementation of partition (although if you get partition correct, there is no reason that you shouldn't also get quicksort correct). My code (given above) already has a test program for pack. If you get partition correct but not quicksort, include a program that tests your partition algorithm.