Requirements for CS330 Fall 2001 Project 4
This series of experiments you must take code from the book (or from the Web) and make it work on your own. Hand in what you have got on the deadline. The quiz will ask at least one question about the work you did in this project. The experiments are based on coding and debugging well known sorting algorithms(4B..4E) and a well known data structure(4A). Hints: (1) Start the first one as soon as you can. (2) fix any errata in the book before downloading or typing any code. (3) Download code rather than retyping it. (4) Allow time for errors. Some will be similar to ones on previous projects -- eg. missing declarations -- but some are subtle bugs. Some will be obvious if you see them.
4A. Chapter 14: Test, fix, and document any problems with the book's code that derives orderedVector from the STL vector.
4B. Chapter 14: Test, fix, and document any problems with the book's code for treeSort using the STL vectors and multisets. (hint <set> includes multiset). Keep it simple! Note. Budd has a comment that uses the 'copy' algorithm to produce output: high energy magic.
4C. Chapter 14: Test, fix, and document any problems with the book's code for quickSort. Note: test the partition function thoroughly. This form of it often has bugs that occur in special cases like small or empty data sets.
4D Priority Queues Chapter 15: Test, fix, and document any problems with the book's code for heapSort. Do not use Budd's/Book's code for priority_queue or priority_queue algorithms. Instead use #include <queue> that has priority_queue, make_heap, and sort_heap in it already. What can you remove from Budd's code?
4E. Hash Tables Chapter 17: Test, fix, and document any problems with the book's code for RadixSort.
Bonus Points for a one page graph and report comparing the times you got of several different sorting algorithms. At least 6 algorithms. +1 point per algorithm included.
Hand in Your code at the start of the Final Examination. Grading: Each step (A, B, C, D) will be given the same weighting (5 points each). Bonus points can make up errors else where in the class and/or/final. The grade depends on writing simple obvious code and using comments for documentation. You must document any changes made to the books code, the purpose of each classes and function, any remaining unfixed errors, and any clever ideas. Include any invariants etc. that might help convince the reader that your code works. Mark changes from the book with a hilighter pen before handing in.