Due on Tuesday 24th February

You may work in pairs for this assignment. Plan and think out carefully before you start programming. The point of question 1 is to explore manipulating a queue-like data structure and threads -- you'll find that it's relatively easy to organise what you're trying to do and to write code that almost works, but that playing with threads makes the code very sensitive to small errors, so it may take a little while to sort out all the 'debugging' to move from being nearly done to actually being done. Hopefully you'll find the second (thinking, not coding) question refreshing to play with as a break from the coding stuff.

Question 1

Imagine being in a supermarket and being about to queue to pay. There are c cashiers (imagine c = 10), and hence c queues to choose from. Since your objective is to pay and leave reasonably quickly, you should imagine that there's a 'feeder' structure from which each person chooses which cashier queue to join. Just like any queue, the only place to enter is the back, and the only place to be 'served' is the front (after which that person joins the collection of happy customers). However, these cashier queues (CQ) allow the additional ability (skip) to be able to leave in order to join the back of any other CQ that person chooses (ie, they're getting tired waiting and some other CQ looks to be better; perhaps having a shorter line, or a faster movement, for example). Using threads, run a simulation (writing suitable stats to the screen and to a file for later analysis) to see what happens as you adjust any preferences in the skip method. You will probably want to use Math.random( ) to generate cashier speeds (eg, a*Math.random() + b will give a random double between b and a+b, so that you can have the cashiers operating at different rates, yet with some random variation, possibly overlapping). You might want to experiment with various values to see if there are any good strategies (join the fastest queue, join the shortest queue, join the second best queue ...), although this question is NOT asking for you to develop an optimal strategy (that's potentially a hard question!)

Question 2

Propose a data structure which supports the stack push and pop operations and a third operation findMin which returns the smallest element in the data structure, all in O(1) worst case time.