Algorithms and Data Structures

Project 2

Aim

The aim of this project is for you to get more experience with writing Ansi C code, including the use of abstract data types and non-trivial data structures and algorithms. You will also be required to analyse and compare code.

Outline

You will be improving the implementation of key components of a program which simulates a supermarket. The program uses a technique called discrete event simulation which uses a priority queue (pqueue) of "events", ordered on the time the event occurs. The program also uses queues of "people", to simulate the checkout queues in a real supermarket. You will be required to improve the queue and pqueue implementations and compare your implementation with the existing one. It is not necessary for you to understand how events or people are represented, or how the simulation works (though the code will be provided in case you are interested). Queues and pqueues are an abstract data type with a well defined interface which you will not be changing.

Overview of simulation

The program simulates the following scenario. Customers arriving at the supermarket have a shopping list. They spend some time selecting the goods (the time depends on how many items they need to buy) then choose the (open) checkout lane with the shortest queue. When they get to the front of the queue the items are priced etc and paid for (the time depending on the number of items) and the customer leaves. Initially there is only one checkout lane open but the store manager regularly checks how things are going. If the queues are long the manager may decide to have another lane opened (which takes a little time) and if there are empty queues the manager may decide to immediately close a lane. By refining the code and data the program can be used to explore the effect of different arrival patterns (and shopping lists) of customers, manager strategies (when to open and close lanes), checkout speed (eg, employing some faster but more expensive checkout staff), adding "express checkout" lanes, etc. The code (with some documentation of the implementation method) can be found in sim.c (Also in /home/stude/data/253/proj2). Sample output is provided in Out, an extract appears below (the first column is the time the event occurs):

0 manager check: Idle lane
5 customer 0 arrives wanting 10 things
7 customer 1 arrives wanting 15 things
9 customer 2 arrives wanting 20 things
...
25 customer 10 arrives wanting 29 things
26 customer 5 chooses lane 0 (queue length 1)
26 checkout start for customer 5
27 customer 11 arrives wanting 3 things
28 customer 0 chooses lane 0 (queue length 2)
29 customer 12 arrives wanting 8 things
30 manager check:
...
50 customer 7 chooses lane 0 (queue length 5)
50 manager check: Long queues - better open another lane!
51 customer 23 arrives wanting 1 things
52 checkout end for customer 6
52 customer 2 chooses lane 0 (queue length 5)
52 checkout start for customer 1
53 customer 24 arrives wanting 6 things
55 Lane 1 is now open
55 customer 25 arrives wanting 11 things
56 customer 23 chooses lane 1 (queue length 1)
...

ADT Interfaces

C is not a great language for implementing abstract data types, that is, separating the interface of a data type from its implementation. It require discipline on the part of programmers who use a data type to only use it in certain ways (in other languages the compiler can enforce this).

Queue Interface

There are five defined operations in the interface to queues:

queue_init() - returns empty queue
queue_len(queue) - returns length of queue
queue_add(queue, person) - adds person to end of queue
queue_rm(queue) - removes person from head
queue_head(queue) - returns person at head of queue; queue is unchanged

The function prototypes are defined in queue.h. These are the only things which should be relied on when using queues. In addition, the type queue is defined (unfortunately an undisciplined C programmer could write code which depends on the details of this definition, so C does not allow us to completely hide the implementation of the data type). A prototype implementation of the operations is provided in queue.c.

Priority Queue Interface

There are four defined operations in the interface to pqueues:

pqueue_init() - returns empty pqueue
pqueue_len(pqueue) - returns length of pqueue
pqueue_add(pqueue, event) - adds event to pqueue
pqueue_rm(pqueue) - removes "minimum" event, returns event

Other operations, such as changing the priority of an item and building a pqueue from a collection of items do not have to be supported. The function prototypes and the type pqueue are defined in pqueue.h. A prototype implementation of the operations is provided in pqueue.c.

Events are primarily ordered according to the 'time' field of the event type (a struct). If two events with the same time are added to the pqueue, the one added first should be considered to have a smaller time. Note that the prototype doesn't implement this enhancement - events with the same time can be ordered arbitrarily, which can affect the output of the simulation.

The task

You are required to re-implement the queue and pqueue abstract data types, without changing their interfaces, and carefully document (in a separate file) the advantages and disadvantages of your implementation compared to the prototype. You may also want to write other code for debugging purposes, but you should not submit it.

Your pqueue() implementation

You are required to implement pqueue using binary search tree(BST)s.
You implementation should take care of the enhancement mentioned for the orderings of the events mentioned above. If two events with the same time are added to the pqueue, the one added first should be considered to have a smaller time.
You are also required to analyze the performance of your BST based pqueue for the simulation. For this purpose you should compute the average complexity of your pqueue operations using an experiment in this setting. You should then compare this result with the standard implementation. You do not need to submit any extra code you wrote to compute the average complexity, but only discuss the results in your comparison.txt file. However, you do not need to make experiments with the given pqueue based on array heap; you may assume complexity figures for this implementation from the theory.
You should discuss the best and the worst case complexities of your implementations with the prototype.
As your pqueue is based on BST, your implementation can support arbitrarily long priority queues.
Your queue() implementation
All queue operations should be O(1) (ammortized complexity).
You should use only the standard list representation. (This means that you cannot use the list based queue implementation in Program 4.10, (Algorithms in C, Sedjewick) where a tail pointer is used).

For your convenience the Haskell code for a queue implementation which uses only lists is provided in queue.hs. The code is given below:

-- queue = pair of lists (q1 ++ reverse q2)
-- N operations take O(N) time overall
type Queue a     = ([a], [a])

qEmpty          = ([], [])

qPut i (q1, q2)  = (q1, i:q2)

qHead (i:q1, q2) = i        -- O(1); common case
qHead ([], q2)   = last q2  -- O(N); occurs 1 time in N

qTail (i:q1, q2) = (q1, q2) -- O(1) (as above)
qTail ([], q2)   = (tail (reverse q2), []) -- O(N)

All Your implementations should be reasonably efficient - short (priority) queues should not use excessive space.

The prototype implementation contains bugs, limitations and/or efficiency problems. Your comparison.txt should mention these and compare overall memory consumption and the time complexity for each operation and may also describe alternative efficient implementations.

Questions and answers

Questions and answers pertaining to the project will be available in QandA.html and will be considered part of the specification of the project.

Marking

This project is worth 12% of the final mark for the subject. Three marks will be awarded for the comparison; the remaining marks will be for the code, taking into consideration correctness, the algorithms and data structures used, coding style, documentation etc. Note that our testing of your code may not be based just on the current version of sim.c (and, as always, you are strongly encouraged to think carefully about how you will develop and test your own code).

Submission

You will need to submit your versions of queue.h, queue.c, pqueue.h, pqueue.c and comparison.txt (these filenames must be used). Submit using the command submit 253 2 on a Computer Science machine by 5:00pm on Thursday May 16. Verify your submission using the command verify 253 2. Late submissions will incur a penalty of two marks per day (or part thereof) late. If you cannot submit on time you should contact the tutor in charge at the soonest possible opportunity (this generally means before the deadline). Late submission will be done using the command submit 253 2.late The project is due in two weeks.