CSCI 151 - Prelab 4

Due at the start of class on Monday March 5

In lab 4, you'll be

The prelab questions are related to linked queues and the radix sort.  Please write or type up your solutions, and hand in a paper copy by 10 am on Monday.  Sign the Honor Pledge somewhere on your paper.  Late prelabs are not accepted.


In lab 4, you'll be writing your own Queue class, implemented as a linked list of nodes, as shown below:

linked queue 

    Question 1:

    Make a copy of the above sketch of q1.  List the steps that would be required to enqueue the value E onto q1, and show the changes in your sketch.

    Question 2:

    Draw a sketch of a second linked queue q2, this one containing the values X, Y, and Z.  Then show the changes that you would need to make to append q2 to q1.  You should do this just by altering some of the object references in the diagram, not by creating any new nodes.

    How many changes were needed?  List them.

    Question 3:

    Suppose you were to perform the same enqueue and append operations on one list of M elements and a second list of N elements.  What is the running time (in big-Oh notation) of these operations?

the Radix Sort

Radix sort is a sorting method which works by testing the characters of a set of strings, one at a time, from right to left.  Several passes are made over the data, one for each character position.  On the first pass, the strings are thrown into bins according to the final (i.e., rightmost) character of the string.  (For strings using the English alphabet, there would be 26 bins.)  After the all the strings are distributed into the bins, the contents of the bins are combined into a single list.  The process is then repeated by sorting this list into bins according to the next-to-last character, etc., until a final pass based on the first character.  When the final pass is completed, the entire list is in ascending lexicographic order.

As an example, suppose we have a 3-letter alphabet {A,B,C} and want to sort the list {AAB,BCA,CAB,BBC}.  In the first pass, we'd look at the third character of each string and put AAB into the B bin, BCA into the A bin, CAB into the B bin, and BBC into the C bin.  After combining the bins into a single list, we'd have {BCA,AAB,CAB,BBC}.  In the second pass, we'd again sort into bins, but this time looking at the second character of each string.  This time, BCA would go into the C bin, AAB into the A bin, etc.  After three passes (each time sorting into bins and then combining the bins), we'd have the sorted list {AAB,BBC,BCA,CAB}.

For the algorithm to work correctly, it's necessary that the bins are maintained in FIFO order.  That's why we'll be using queues for them in the lab.

    Question 4:

    Apply the radix sort to the following list of strings:


    After each pass (there will be 4 passes because each string is 4 characters long), show

    a.  the contents of each of the bins produced by that pass, and

    b.  the list obtained by combining the bins.

handing in your prelab

If you adhered to the honor code in this assignment, add the following statement at the top of your prelab.

I have adhered to the Honor Code in this assignment.

Write or type your solutions and hand in a paper copy by the deadline listed at the top of this prelab.  Late prelabs will not be accepted.