Lab Assignment #3

Implementing a Priority Queue in Smaltalk

Description

In this lab you will implement a priority queue class and you will time and compare its performance to a given implementation. You have to time the execution of a given demo class-method on the given code, implement your own priority queue, and time the execution of the demo code on it, too. You will turn in the timing results, and the code.

A priority queue is a data structure that allows numbers to be inserted in any order and always knows which was the minimum or the maximum value seen (much like a thermometer which remembers its extremes). It can also extract a minimum or a maximum value from the queue. After a minimum extraction the queue knows what the next larger value is and this becomes the new minimum (same for maximum extraction).

A priority queue typically has the following operations:

min - return the minimum value in the queu
max - return the maximum value in the queu
extract_min - return and remove minimum value
extract_max - return and remove maximum value
insert: - insert a new value in the queue
isEmpty
do: - applies a block of code to each element in the queue without changing the elements themselves
collect: - applies a block of code to each element in the queue and returnes the individual results in a collection of some sort

Typically each number inserted in a queue is associated with an element, a process for example, whose priority it determines. Processes would get assigned numbers and then they would be inserted in the PriorityQueue. It's called a priority queue because it is almost like a queue except that an element with a higher priority doesn't stay at the end of the line but cuts in front of all elements with lower priorities

You are given code for a superclass PriorityQueue with two subclasses PriorityQueueOC and PriorityQueueSC. The subclasses implement priority queues with an OrderedCollection and with a SortedCollection, respectively. Your own priority queue will inherit from PriorityQueue as well, and it will be implemented internally as a linked list of nodes. You are given a Node class for this, but you still have to link them together.

Part 1 - Timing the given code

First, you are to time the performance of the each of the priority queues under repeated insertion and extraction operations. The PriorityQueue class has a demo class method that will be inherited by each class which inherits from PriorityQueue. This demo creates an instance of the class it was called on (by calling self new within the class method). It then repeatedly inserts N random numbers in the queue (and prints them to the trascript), and then repeatedly extracts N numbers from the queue (and prints them to the transcript). N is an integer argument passed to the demo method. Note that by repeatedly extracting the minimum value you are in fact sorting the numbers and you should notice this from the transcript. Run the following two examples and look at the transcript.

 PriorityQueueOC demo: 10 "sort 10 random numbers"

and then

 PriorityQueueOC demo: 40 "sort 40 random numbers"

Notice that the elements in a priority queue may be kept sorted or unsorted. Each implementation has its advantages and disadvantages. A sorted implementation would find the min and the max quickly (they're the first and the last elements in the list) but would take a while to find the right place to insert a new item. An unsorted implementation would insert quickly (insert at the head of the list) but would take a long time to find the min or the max. Compare the two given implementations by timing the demo on 1000 random numbers. Use the code below for that. Until now, you have executed code by typing it in a window, selecting it, and choosing "do it" with the middle mouse button. This time, instead of "do it" choose "print it" to actually print out the result of the code to the Transcript window. The result printed is that of the last line of code you have selected; the examples below have one one line.

 Time millisecondsToRun: [PriorityQueueOC demo: 1000]

and then

 Time millisecondsToRun: [PriorityQueueSC demo: 1000]

Which is better a sorted or an unsorted implementation?

Part 2 - Implement a priority queue with a linked list

Based on the results above decide on whether to keep your list sorted or unsorted. Implement all of the operations that priority queues should support.

Hint1: An unsorted list is easier to code.

Hint2:Your class should have an instance variable for the first node in the list and the rest will be accessible by using the nodeAfter method on this node.

Part 3 - Time the demo on YOUR code

Type the following in a window and "printIt."

  Time millisecondsToRun: [ PriorityQueueUL demo: 1000]

Turning in the timing results

For this lab you will hand in the timing results and your code. You should have the running times for the "demo" method with 1000 numbers on a PriorityQueueOC, a PriorityQueueSC, and your own priority queue. Also, hand in a couple of lines of text (VERY FEW) trying to give a reason for why each implementation ran as fast as it did.

To file out only the PriorityQueueUL code, select the PriorityQueueUL class in the system browser, then in the same window (the second column) press the middle mouse-button and select "file out".

cat times PriorityQueueUL.st | mail -s "Lab 3 - YOUR NAME" cs2390@prism.gatech.edu

Please quit from VisualWorks before you logout!!