Homework 1: Sort and Search
In this homework, you will implement the sorting algorithms from the course against the List interface, and the searching algorithms from the course inside implementations of the Set interface. You will also build a List that counts the reads and writes made on its elements. Then you will run every algorithm on data files, measure the work each one does, and compare what you measure with what the analysis in the notes predicts.
This homework is optional. It is graded with feedback, but the grade does not count toward your course grade. See Homework for why.
After this homework, you should be able to:
- Implement a data structure that counts the operations performed on it, and write unit tests for it.
- Implement selection sort, bubble sort, insertion sort, and merge sort against an interface that every sort shares.
- Implement sets that search with binary search and with the transpose and move-to-front heuristics, and implement move-to-front on a circular array.
- Run the algorithms on data files, find where the measurements disagree with the analysis, and explain why.
A link to download the starter code, hw1-starter.zip, will be posted on the course discussion board.
Important dates
| Event | Day | Date | Time |
|---|---|---|---|
| Release | Mon | Oct 12 | 09:00 AM ET |
| Due | Mon | Oct 19 | 05:00 PM ET |
Tasks
This homework has four tasks:
- Implement
MeasuredArrayList, and write unit tests for it inMeasuredArrayListTest. - Implement four sorting algorithms:
SelectionSort,BubbleSort,InsertionSort, andMergeSort. - Implement four sets:
MeasuredArraySet,MeasuredSortedArraySet,MeasuredTransposeArraySet, andMeasuredMoveToFrontArraySet. - Answer the discussion questions in
DISCUSSION.md.
I suggest you do them in this order. The drivers you need for task 4 use MeasuredArrayList, so they do not run until task 1 is done.