Computer Science 269
Introduction to Data Structures
Spring 2000
Assignment 4
Due Friday, March 3, 2000.

-
Goals of this assignment:
-
To learn a number of sorting algorithms.
-
To learn implementation of certain data structures used for some
of the sorting algorithms, such as binary search trees, AVL trees, and
heaps.
-
To learn how to compare the performance of different algorithms for
the same problem.
-
To learn how to judge which of a number of algorithms for a given problem
is best for a given situation.
-
To gain skill in documentation.
-
It is expected that students will discuss the assignments. But do
not turn in code written by another person. If that happens, both
persons are violating the ethics of this course. Representing the
work of another person as your own is plagiarism, and may result in
a disciplinary "F" in the course.
It is permissable (in this course, as this is up to the instructor)
for you to obtain ideas from other students or from other persons.
But you must type in the code yourself.
It is unadvisable for you to allow another student to have an electronic
copy of your work, as then you would unwittingly be a party to a breach
of these rules. Showing the other student a hard copy is less dangerous.
The above rule does not apply to copying files that I have made publicly
available. I expect that you will use those in their original form or
with appropriate modifications (made by just you, of course).
If you utilize code that you obtain from other sources, be sure to give
credit in a comment, such as:
// this code from website www.mit.edu/help/x13
-
Implement a number of sorting algorithms, each of which sorts a file of
non-negative integers.
-
For each of a number of files of various sizes, run each of your sorting
algorithms.
-
For each run, measure the time complexity, in order to better compare
the efficiency of the different algorithm.
-
Construct a table showing the time and space complexities for each
file and each algorithm, and write a conclusion.
When measuring space complexity of an algorithm, be sure to include
the space used by the run-time stack. That is, if your algorithm
uses recursion, and the depth of the recursion is O(n), then the
run-time stack uses at least that much space.
Your documentation should contain a summary
of the results and your judgment as to which algorithms are best in
various situations.
-
The following sorting algorithms should be implemented. (Note that all
of these can be implemented using arrays; none need dynamic allocation.)
Implementation of additional algorithms, some of which need dynamic
memory allocation, will be due March 10.
-
An input file for your program must be a text file, where each line
contains just one integer written in decimal. Your program must
run correctly regardless of the length of the input file, unless
it is so large that it overflows the memory of the computer.
Please run each of your 5 programs on each of the
test files of integers
that I have created. Feel free to use other input files as well.
It is not necessary to turn in copies of the input files that I provided,
as I already have copies.
-
Documentation will be a requirement for this assignment:
-
A design document.
-
Loop invariants, written as comments, for any tricky loop.
It is a judgment call whether a particular loop needs to
have its loop invariant written. Use the ``reasonable'' test.
Would a ``reasonably competent'' CSC major be helped, in understanding
your code, by seeing a comment explicitly stating this loop invariant?
-
Input and Output conditions for functions, again using the ``reasonable''
test.
-
Comments explaning variables and functions whose purpose is not obvious.
-
Other comments, as appropriate. But code that is overcommented looks
silly.
There are some students who want to write every conceivable comment,
"Just to be sure." Don't do that. I will instruct the grader to
take off points for ridiculous overcommenting. You are supposed to
use your judgment, and you are to be graded on how good your judgment
is.
-
A summary of the time and space complexities of your various algorithms
in various situations.
(This could be a hand-written document, but I
will accept a computer file to be submitted along with the other
computer files. Make sure that if you submit a computer file, that
it is readable to the grader.)
-
All files including output files showing the sorted arrays should
be put together using the "shar" command and emailed to the grader.
Be sure to include documentation indicating which files are from which
run.
-
As always, the programs must be executed on our system. You should
use the command: g++ -fhandle-exceptions
If you cannot get your program to run on our system, even though
it works on some other computer, that will be graded the same as
non-working code, in other words,
partial credit might be given.
-
Turn in all files, including a file that shows several sample runs.
All files must be turned in electronically to the teaching assisant.
His email address is schj. The deadline for electronic submission
is Friday, March 3. The submission must be timestamped
before midnight.
Here is how that is done.
Be sure to include the string "CSC 269 001 Hw4" in the subject field
of your email.
-
Do not use up your print quota printing out huge sorted files. Just
glance at them on the screen, or run a test to make sure they really
are sorted.
