Due on Wednesday 27th February
You should submit solutions to this h/w via the cms system by 11pm on Wednesday.
There are two types of questions; the first is a programming one, the other focuses more on 'pure' thinking. 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 don to actually being done. Hopefully you'll find the thought questions 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' queue 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 a file for later analysis) to see what happens as you adjust any preferences in the
ship 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:
This is question 3.6 from page 95 of the textbook. Consider the following game: N people, numbered
1 to N, are sittig in a circle. Starting at person 1, a hot potatoe is passed. After M passes, the person
holding the hot potatoe is eliminated, the circle closes ranks, and the game continues with the person who
was sitting after the eliminated person picking up the hot potatoe. The last remaining person wins. Thus,
if M=0 and N=5, players are eliminated in order, and player 5 wins. If M=1 and N=5, the order of elimination
is 2, 4, 1, 5 with player 3 winning.
- Write a 'nodal' program to solve this problem for general values of M and N, trying to make your program
reasonably efficient.
- What is the running time of your program (express this asymptotically in terms of M and N)?
|