Lab Assignment #6

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. If you read the lab carefully it is straight forward. You have to run some given code, implement your own class, and run that code again on your class. You will turn in the timing results, but save the code for the next lab session.

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 (you will implement only isEmpty, extract_min, and insert:).

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
do: - applies a block of code to each element in the queue (in practice this block of code might change the numbers and thus the priorities or order of the associated elements)
isEmpty

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 a superclass PriorityQueue with two subclasses PriorityQueueOC and PriorityQueueSC which 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 (printIt).

 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 only the isEmpty, extract_min, and insert: operations.

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.

Hint3:You may have to implement some of the following methods as "private" to support the operations above (access is not enforced in Smaltalk, but methods which are not for general use are grouped in a "private" protocol) I suggest you implement them only as you need them.

head_insert:
head_delete
first - return first without removing it
insert - if you implement the priority queue as a sorted list this operation would insert at the proper place in the list thus maintaining the order

Part 3 - Time the demo on YOUR code

Type the following in a window and "printIt."

  Time millisecondsToRun: [ YOUR_PRIORITY_QUEUE demo: 1000]

Turning in the timing results

For this lab you will hand in the timing results. 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.

(1:30-3)
cat file.txt | mail -s "lab 4 - YOUR NAME" joita@cc.gatech.edu
OR (3-4:30)
cat file.txt | mail -s "lab 2 - YOUR NAME" jyan@cc.gatech.edu
OR (4:30-6)
cat file.txt Game.st | mail -s "lab 2 - YOUR NAME" smk@cc.gatech.edu

That's all for this lab. BUT SAVE YOUR CODE! You will need it for next week's lab!

Please quit from VisualWorks before you logout!!