Check out "Hungarian sort dance" in youtube and see if it helps you better
understand the various sort algorithms.
Analyze the following code and provide a "Big-Oh" estimate of
its running time in terms of n. Explain your analysis.
int k = n;
while (k > 0) {
for (int j=0; j < n*n; j++)
sum += data[j];
k = k / 8;
}
Review recursion
in Module
4 of CS-1112 (at least up through palindrome checking).
Read again the step-by-step example of quicksort in Module 2 of this
course. Then, show how quicksort works on the array (length=6) of characters
"D F C E B A", by following the pseudocode, using the bidirectional
partitioning algorithm. At the beginning
of each call to
quickSortRecursive(), show the complete state of the stack,
as in the first example from the CS-1112 material, including the
values of L, R and p.
Let W(n) be the "work done" (time taken) by MergeSort on an array of
size n. Write the recurrence relation for W(n) and
work out the solution as was done in class for quicksort.
Review binary trees from from a previous course, or
from an online source.
Insert the following elements "A C B G H D E F" (in that order)
into a standard
binary search tree and draw the tree at each step.
Consider a complete binary tree with n leaves.
How many interior nodes (in terms of n) does the tree have?
Use the appropriate summation formula as part of your reasoning.
Duplicate removal, part 2. Recall the duplicate
removal problem from Exercise 1. Consider a slight variation
of the problem in which duplicates are removed from
the original array and leaving the remaining (unique) items
in the same array but packed together, with zeroes replacing
all elements after the unique elements.
Thus, if given
the array
[2,3,2,2,1],
what is returned is
[3,1,2,0,0],
along with the new length
3.
Just like in part 1, we are not interested in the order
of the unique elements, so any order is permissible.
Show how duplicate removal
can be done in time O(n log n) in the same array as
the input array. That is, write pseudocode in the style
we have been using in class. Explain why your algorithm
takes O(n log n) time.
Who devised quicksort? Read a short bio and
write down three things about this person. (We will
do the occasional such exercise for you to learn about
great computer scientists, most of whom are still alive.)
Note: Credit will not be given only for answers - show all your
work: your reasoning, steps you took to get your answer etc.
Implement the non-recursive version of MergeSort.
Also, implement the small-size cutoff optimization, with InsertionSort
as the small-size sort. Experiment with various cutoff sizes to
see whether this approach makes a difference.
Your MergeSort will need to implement
the SortingAlgorithm interface.
(and therefore the Algorithm interface)
so you can use the AlgorithmTest environment.
Note:
You will also implement a main method with (at least) the following
tests:
Create tests to make sure the merge works.
Test the sort with 10 elements to see if the result is sorted
and that no elements were overwritten or "lost" in the sorting.
The same with 100 elements.
Note: name your basic MergeSort (without the optimization)
MergeSort, and name the optimized version
MergeSortOpt.
Use merge.props as the properties
file in the test environment.
You do not need to implement the sort-index methods, only the
sort-in-place methods. You can change the
sortingTester.testComparable
property to false if
you (temporarily) want to avoid testing strings.
Recall that String's
implement the Comparable
interface and that anything that implements that interface
can be compared using the compareTo method.
Submit pseudocode for your algorithm.
Compare your optimized (non-recursive) MergeSort with your basic
(non-recursive) MergeSort in terms of actual performance.
Replace InsertionSort with SelectionSort for the small-size
sorts. Do you see a significant difference?
Submission:
For both algorithm comparisons above, submit a plot (in ex2.pdf)
using either the plot from the test environment or some other plotting
package (such as Gnuplot).
For this assignment and others, you will need to follow
the usual submission instructions
carefully. Remember, pen-and-paper answers should be in your ex2.pdf.
As usual, you are expected to implement your own copious testing
of your algorithms.