Week 14: Exercises

1. Blocking Queue

Implement a blocking queue in C# with a fixed capacity. The queue must have this interface:

class BlockingQueue<T> {

  public BlockingQueue(int capacity) {  … }

  public void enqueue(T val) { … }

  public T dequeue() { … }
}

If a thread tries to enqueue a value and the queue is full, it should block until there is space available. If a thread tries to dequeue a value and the queue is empty, it should block until there is some value in the queue.

2. Parallel Factoring

Write a method factor(int n, out int p1, out int p2) that factors an integer n that is guaranteed to be the product of two prime numbers. Speed up the calculation by using 8 threads.

3. Parallel Sorting

Write a method that sorts an array of integers, using multiple threads to speed up the sort. Which sorting algorithm(s) will work well for a parallel sort? Perform timing experiments to determine the speedup factor when you use 8 threads for the sort.

4. Prisoners and a Light Bulb

You are one of 40 recently arrested prisoners. The prison warden makes the following announcement:

You may meet together today and plan a strategy, but after today you will be in isolated cells and have no communication with one another.

I have set up a “switch room” which contains a switch and a light bulb. The switch turns the light bulb or off.

Once per hour, I will select one prisoner to enter the switch room. This prisoner may throw the switch (from on to off, or vice-versa), or may leave the switch unchanged. Nobody else will ever enter this room.

Each prisoner will visit the switch room arbitrarily often. In other words, at any given moment, each of you is guaranteed to visit the switch room again at some future point.

At any time, any of you may declare: “We have all visited the switch room at least once.” If the claim is correct, I will set you all free. If the claim is incorrect, I will feed all of you to the crocodiles.

Devise a winning strategy when you know that the initial state of the switch is off.

5. Prisoners and a Light Bulb, Part II

Continuing the previous exercise, devise a winning strategy when you do not know whether the initial state of the switch is on or off.

6. Prisoners with Red and Blue Hats

You are one of 20 recently arrested prisoners. The prison warden makes the following announcement:

I will order you all to stand in a line, and will place a red or blue hat on each of your heads. No prisoner will know the color of his own hat, or the color of any hat behind him, but he will see the hats of all the prisoners in front of him. I will start at the back of the line and asks each prisoner to guess the color of his own hat. The prisoner can answer only “red” or “blue.” If he gives the wrong answer, he will be fed to the crocodiles. If he answers correctly, he will be freed. Each prisoner will hear the answers of the prisoners behind him (but cannot tell whether those answers were correct).

You may consult and agree on a strategy beforehand but after being lined up, you cannot communicate any other way besides your answers of “red” or “blue.”

Devise a strategy that allows as many prisoners as possible to go free.