CSC 477/677 Assignment 3
Due date, March 11, 2004, 4:00 PM.
All assignments must be handwritten
(not typed or printed from a computer file)
in your own handwriting, on 8.5 by 11 inch paper. Write your name on
each sheet, and do not fold the pages or crimp the corners.
Turn the pages in to me or to the graduate assistant on the due date.
-
Work problem 4.1 on page 139 of your textbook.
-
Apply quicksort to sort the list
D,I,V,I,D,E,A,N,D,C,O,N,Q,U,E,R.
Show the array at each step.
To make it easier to grade, always pick the first item in the array to
be the pivot item. (This is normally not a good choice.)
-
What sorting algorithm do you think would be best in each of the following
situations? Explain.
-
You are given many thousands of lists, each of which is very small. In fact,
their average size is 1. (You need to sort each list separately.)
-
You have a list of donors that you want to alphabetize. This list was formed
by concatenating lists of donors from each of the 50 states. Each state
list was sorted. The total number of names is approximately 100,000.
-
We will implement a heap of letters as an array, as shown in class.
Start with an empty heap, and perform the following operations:
Insert(G);
Insert(N);
Insert(B);
Insert(H);
Insert(M);
Insert(R);
Insert(V);
Insert(C);
DeleteMin;
DeleteMin;
DeleteMin;
What will the array be after those operations? Show the array at each step.
Additional problems to be added after Tuesday's lecture.
-
Additional problems to be added after Tuesday's lecture.
Back to
Course Page