F.10 Chapter [*]

Quick Quiz [*].1: 
Can a similar algorithm be used when deleting elements?
 
Answer:
Yes. However, since each thread must hold the locks of three consecutive elements to delete the middle one, if there are $N$ threads, there must be $2N+1$ elements (rather than just $N+1$ in order to avoid deadlock.

Quick Quiz [*].2: 
Yetch! What ever possessed someone to come up with an algorithm that deserves to be shaved as much as this one does???
 
Answer:
That would be Paul.

He was considering the Dining Philosopher's Problem, which involves a rather unsanitary spaghetti dinner attended by five philosophers. Given that there are five plates and but five forks on the table, and given that each philosopher requires two forks at a time to eat, one is supposed to come up with a fork-allocation algorithm that avoids deadlock. Paul's response was ``Sheesh! Just get five more forks!''.

This in itself was OK, but Paul then applied this same solution to circular linked lists.

This would not have been so bad either, but he had to go and tell someone about it!

Quick Quiz [*].3: 
Give an exception to this rule.
 
Answer:
One exception would be a difficult and complex algorithm that was the only one known to work in a given situation. Another exception would be a difficult and complex algorithm that was nonetheless the simplest of the set known to work in a given situation. However, even in these cases, it may be very worthwhile to spend a little time trying to come up with a simpler algorithm! After all, if you managed to invent the first algorithm to do some task, it shouldn't be that hard to go on to invent a simpler one.

Paul E. McKenney 2011-12-16