Homework 2, Sorting Algorithms
Motivation
The goal of this assignment is to encourage you to become a master of a sorting algorithm. While many languages have built-in methods for sorting, as a Computer Scientist in training (or simply someone taking CS32) there is no excuse for not knowing how to properly implement at least one sorting algorithm.
The Algorithms
You will be assigned to report on one of the following five sort algorithms:
Please check Piazza for your algorithm assignment.
Mini-lecture slides
For this homework you are to prepare the slides that would accompany a mini-lecture with a duration of 10 to 20 minutes. The goal of the mini-lecture is to teach our class all there is to know about the sorting algorithm you have been assigned.
Your lecture slides must address each of the following:
- How does the algorithm work? Please provide at least two examples to help explain the procedure.
- What is the running time of the algorithm (best case, average case, worst case)? You should be able to explain why the running time is as it is.
- Are there any special cases that would make the algorithm more efficient? Explain.
- Are there any special cases that would make the algorithm less efficient? Explain.
- Does the algorithm depend on any data structures (aside from the list or array the data may already be stored in)? Explain
- Can the algorithm run in-place, that is, without the need of extra memory?
Teaching the class
If you would like to volunteer to deliver your mini-lecture, you may request to do so via Piazza. One volunteer for each sorting algorithm will be selected to teach the class. If there are no volunteers, someone will be selected at random.
Therefore, if you plan to attend Monday’s lecture (highly recommended), be prepared to give your mini-lecture. You should be prepared even if someone volunteered for your algorithm, as that student may not show up.
Collaboration
For this assignment you are encouraged to collaborate with the other students in the class. Feel free to use Piazza to discuss all the information required in your slides. You may not, however, share your lecture slides; please keep those private until the submission deadline has passed.
External Resources
In your slides, please feel free to use external resources. However, ensure you provide proper attribution to any work you include. Citing the wikipedia article is not sufficient, dig deeper to discover the actual source. If you aren’t sure how to provide a proper attribution for something, please ask on Piazza.
Additionally, linking to external resources from within your slides is strongly encouraged as there are a number of excellent sorting algorithm resources online.
Submission
Please submit your material by 10:59:59 Monday morning (08/06) using submit. Rename the file containing your slides to one of the following names; whichever is appropriate for your filetype:
- cs32_sorting.pdf
- cs32_sorting.ppt
- cs32_sorting.pptx
Submit via:
~cs32/submit hw2@cs32 cs32_sorting.{EXT}
Replace {EXT} with whatever the extension is of your file.