
CS 302 Assignment 2:
Due date: Wednesday, February 3, 2016, midnight.
All programming assignments must be
submitted electronically.
Submit them to the graduate assistant Bikash Bamjan
by email
at lamabamj "at" unlv "dot" nevada "dot edu
before midnight of the due date.
Your email must come from your university or engineering college account.
-
Given the asymptotic complexity of each of these code fragments.
Write the answers on this sheet and turn it in by
11:30 AM on the due date. It is not necessary to explain how you got the
answers, and there is no code to turn in for this problem.
-
Write a program which
-
Reads real numbers from a file into an array of size no more than 1000,
and reports the size of that array.
-
Sorts the array using selection sort.
-
Sorts the array using bubblesort.
-
Sorts the array using quicksort.
You may not use randomization.
I did not tell you how to pick the pivot item in class. There are several
suggestions "out there." My personal favorite is to pick the item
in the middle position, namely (first+last+1)/2.
There is no known
deterministic method for picking pivots that is both
-
fast and
-
guaranteed to give O(n log n) convergence.
Quicksort is fairly tricky. Remember the story about my son who got A-
instead of A in his class because he was unable to do the last assignment,
which was quicksort? The TA was helping him, and together they couldn't do it.
You can use any implementation you can find "out there" which works, or you
can come up with your own. But if you use the implementation I showed you
in class, it is important not to replace ≤ and ≥ by < and >,
nor to replace < and > by ≤ and ≥. Bad things will happen if
you do either of those things.
-
Counts the number of comparisons for each of the sorting
algorithms, and reports that number.
Use the following four files to test your program:
a small file.
a large file.
a file that is "almost" sorted.
Do you expect bubblesort to do better in this case?
another file that is almost sorted.
A file that might give you serious
trouble if you don't follow my instructions.
The graduate assistant must be able to run your program.
Thus, the program must run on his machine.