Classical Computer Science Puzzles
http://www.codinghorror.com/blog/2007/09/classic-computer-science-puzzles.html
That said, many fundamental
computer science concepts can be summarized well in puzzle form, which aids
tremendously in teaching and learning these key concepts. Here's a quick list
of the classic computer science puzzles that I remember from my
university days:
|
|
Five philosophers sit around a
circular table. In front of each philosopher is a large plate of rice. The
philosophers alternate their time between eating and thinking. There is one
chopstick between each philosopher, to their immediate right and left. In
order to eat, a given philosopher needs to use both chopsticks. How can you
ensure all the philosophers can eat reliably without starving to death?
|
|
|
A salesperson has a route of
cities that make up his or her beat. What's the most efficient sales route
that visits each city exactly once, and then returns to the home city?
|
|
|
Given eight queens on a standard 8
x 8 chessboard, how many unique positions-- exclusive of rotations and mirror
images-- can those eight queens occupy without attacking each other?
|
|
|
Two armies, each led by a general,
are preparing to attack a city. The armies are encamped outside the city on
two mountains separated by a large valley. In order to capture the city, the
generals must attack at exactly the same time. The only way for the generals
to communicate is by sending messengers through the valley. Unfortunately,
the valley is occupied by the city's defenders, so there's a chance any given
messenger will be captured. Each general has no way of knowing if their
messenger arrived. How do the generals coordinate their attack?
|
|
|
You have a stack of discs, from
largest to smallest, that slide on to the first peg of a three peg board.
Your goal is to move the entire stack of discs from the first peg to the
third peg. However, you can only move the topmost disc of any peg, and
smaller discs must always be placed on larger discs. How many moves will it
take?
|
I consider this the "greatest
hits" of classic computer science puzzles. But I'm sure I've forgotten a
few. Are there any other puzzles I've missed that express fundamental computer science
concepts, the type that would be taught in a typical undergraduate computer
science course?
=======================================================================
Sleeping barber problem
In
computer science, the
sleeping
barber problem is a classic
inter-process communication
and
synchronization problem
between multiple
operating system processes. The problem is
analogous to that of keeping a barber working when there are customers, resting
when there are none and doing so in an orderly manner.
The analogy is based upon a hypothetical barber shop with one barber. The
barber has one barber chair and a waiting room with a number of chairs in it.
When the barber finishes cutting a customer's hair, he dismisses the customer
and then goes to the waiting room to see if there are other customers waiting.
If there are, he brings one of them back to the chair and cuts his hair. If
there are no other customers waiting, he returns to his chair and sleeps in it.
Each customer, when he arrives, looks to see what the barber is doing. If
the barber is sleeping, then the customer wakes him up and sits in the chair.
If the barber is cutting hair, then the customer goes to the waiting room. If
there is a free chair in the waiting room, the customer sits in it and waits
his turn. If there is no free chair, then the customer leaves. Based on a naïve
analysis, the above description should ensure that the shop functions
correctly, with the barber cutting the hair of anyone who arrives until there
are no more customers, and then sleeping until the next customer arrives. In
practice, there are a number of problems that can occur that are illustrative
of general scheduling problems.
The problems are all related to the fact that the actions by both the barber
and the customer (checking the waiting room, entering the shop, taking a waiting
room chair, etc.) all take an unknown amount of time. For example, a customer
may arrive and observe that the barber is cutting hair, so he goes to the
waiting room. While he is on his way, the barber finishes the haircut he is
doing and goes to check the waiting room. Since there is no one there (the
customer not having arrived yet), he goes back to his chair and sleeps. The
barber is now waiting for a customer and the customer is waiting for the
barber. In another example, two customers may arrive at the same time when
there happens to be a single seat in the waiting room. They observe that the
barber is cutting hair, go to the waiting room, and both attempt to occupy the
single chair.
The Sleeping Barber Problem is often attributed to
Edsger
Dijkstra (1965), one of the pioneers in computer science.
Many possible solutions are available. The key element of each is a
mutex, which
ensures that only one of the participants can change state at once. The barber
must acquire this mutex exclusion before checking for customers and release it
when he begins either to sleep or cut hair. A customer must acquire it before
entering the shop and release it once he is sitting in either a waiting room
chair or the barber chair. This eliminates both of the problems mentioned in
the previous section. A number of
semaphores are also required
to indicate the state of the system. For example, one might store the number of
people in the waiting room.
A
multiple sleeping barbers problem has the additional complexity of
coordinating several barbers among the waiting customers.
==========================================================================
Producer-consumer problem
The
producer-consumer problem (also known as the
bounded-buffer
problem) is a classic example of a multi-
process synchronization
problem. The problem describes two processes, the producer and the consumer,
who share a common, fixed-size
buffer used as a
queue. The producer's job is
to generate a piece of data, put it into the buffer and start again. At the
same time, the consumer is consuming the data (i.e., removing it from the
buffer) one piece at a time. The problem is to make sure that the producer
won't try to add data into the buffer if it's full and that the consumer won't
try to remove data from an empty buffer.
[1]
The solution for the producer is to either go to sleep or discard data if
the buffer is full. The next time the consumer removes an item from the buffer,
it notifies the producer, who starts to fill the buffer again. In the same way,
the consumer can go to sleep if it finds the buffer to be empty. The next time
the producer puts data into the buffer, it wakes up the sleeping consumer. The
solution can be reached by means of
inter-process communication, typically
using
semaphores. An inadequate
solution could result in a
deadlock where both processes
are waiting to be awakened. The problem can also be generalized to have
multiple producers and consumers.
The problem with this solution is
that it contains a race condition that can lead to a deadlock.
Consider the following scenario:
- The consumer has just read the variable itemCount,
noticed it's zero and is just about to move inside the if-block.
- Just before calling sleep, the consumer is interrupted
and the producer is resumed.
- The producer creates an item, puts it into the buffer,
and increases itemCount.
- Because the buffer was empty prior to the last
addition, the producer tries to wake up the consumer.
- Unfortunately the consumer wasn't yet sleeping, and the
wakeup call is lost. When the consumer resumes, it goes to sleep and will
never be awakened again. This is because the consumer is only awakened by
the producer when itemCount is equal to 1.
- The producer will loop until the buffer is full, after
which it will also go to sleep.
Since both processes will sleep
forever, we have run into a deadlock. This solution therefore is
unsatisfactory.
An alternative analysis is that if
the programming language does not define the semantics of concurrent accesses
to shared variables (in this case itemCount) without use of
synchronization, then the solution is unsatisfactory for that reason, without
needing to explicitly demonstrate a race condition.
==========================================================================
Cigarette smokers problem
The cigarette smokers problem is a
concurrency problem in computer science, originally described in 1971 by S. S. Patil.
Problem description
Assume a
cigarette
requires three ingredients to smoke:
- Tobacco
- Smoking
Paper
- A match
Assume there are also three
chain
smokers around a table, each of whom has an infinite supply of
one
of the three ingredients — one smoker has an infinite supply of tobacco,
another has an infinite supply of paper, and the third has an infinite supply
of matches.
Assume there is also a non-smoking arbiter. The arbiter enables the smokers
to make their cigarettes by
arbitrarily (
non deterministically) selecting two of
the smokers, taking one item out of each of their supplies, and placing the
items on the table. He then notifies the third smoker that he has done this.
The third smoker removes the two items from the table and uses them (along with
his own supply) to make a cigarette, which he smokes for a while. Meanwhile,
the arbiter, seeing the table empty, again chooses two smokers at random and
places their items on the table. This process continues forever.
The smokers do not hoard items from the table; a smoker only begins to roll
a new cigarette once he is finished smoking the last one. If the arbiter places
tobacco and paper on the table while the match man is smoking, the tobacco and
paper will remain untouched on the table until the match man is finished with
his cigarette and collects them.
Argument
Patil's
argument was that
Edsger Dijkstra's
semaphore primitives were limited. He used
the cigarette smokers problem to illustrate this point by saying that it cannot
be solved with semaphores. However, Patil placed heavy constraints on his
argument:
- The agent
code is not modifiable.
- The
solution is not allowed to use conditional statements or an array of semaphores.
With these two constraints, a solution to the cigarette smokers problem is
impossible.
The first restriction makes sense, as Downey says in
The Little
Book of Semaphores, because if the agent represents an
operating
system, it would be unreasonable or impossible to modify it every time a
new application came along. However, as
David
Parnas points out, the second restriction makes almost any nontrivial
problem impossible to solve:
It is important, however, that such an investigation [of Dijkstra
primitives] not investigate the power of these primitives under artificial
restrictions. By
artificial we mean restrictions which cannot be
justified by practical considerations. In this author's opinion, restrictions
prohibiting either conditionals or semaphore arrays are artificial. On the
other hand, prohibition of "
busy
waiting" is quite realistic.
Solution
If we remove the second of Patil's constraints, the cigarette smokers
problem becomes solvable using binary semaphores, or
mutexes. Let us
define an array of binary semaphores
A, one for each smoker; and a
binary semaphore for the table,
T. Initialize the smokers' semaphores to
zero and the table's semaphore to 1. Then the arbiter's code is
time.sleep(T)
# choose smokers i and j nondeterministically,
# making the third smoker k
signal(A[k])
and the code for smoker
i is
while true:
time.sleep(A[i])
# make a cigarette
signal(T)
# smoke the cigarette
============================================================================
Readers-writers problem
In computer
science, the first and second readers-writers problems are examples
of a common computing problem in concurrency. The two problems deal
with situations in which many threads must access the same shared
memory at one time, some reading and some writing, with the natural
constraint that no process may access the share for reading or writing while
another process is in the act of writing to it. (In particular, it is
allowed for two or more readers to access the share at the same time.) A readers-writer lock is a data
structure that solves one or more of the readers-writers problems.
The first readers-writers problem
Suppose we have a shared memory area with the constraints detailed above. It
is possible to protect the shared data behind a mutual exclusion
mutex, in which case
no two threads can access the data at the same time. However, this solution is
suboptimal, because it is possible that a reader
R1 might
have the lock, and then another reader
R2 request access. It
would be foolish for
R2 to wait until
R1
was done before starting its own read operation; instead,
R2
should start right away. This is the motivation for the
first
readers-writers problem, in which the constraint is added that
no reader
shall be kept waiting if the share is currently opened for reading. This is
also called
readers-preference, with it's solution below:
semaphore wrt=1,mutex=1;
readcount=0;
writer()
{
wait(wrt);
//writing is done
signal(wrt);
}
reader()
{
wait(mutex);
readcount++;
if(readcount==1)
wait(wrt);
signal(mutex);
///Do the Reading
///(Critical Section Area)
wait(mutex);
readcount--;
if(readcount==0)
signal(wrt);
signal(mutex);
}
The
second readers-writers problem
Suppose we have a shared memory area protected by a mutex, as above. This
solution is suboptimal, because it is possible that a reader
R1
might have the lock, a writer
W be waiting for the lock, and then a
reader
R2 request access. It would be foolish for
R2
to jump in immediately, ahead of
W; if that happened often enough,
W
would
starve. Instead,
W should start as soon
as possible. This is the motivation for the
second readers-writers problem,
in which the constraint is added that
no writer, once added to the queue,
shall be kept waiting longer than absolutely necessary. Here, P() is for wait
and V() is for signal. This is also called
writers-preference.
A solution to the
writers-preference scenario is presented below:
[1]
int readcount, writecount; (initial value = 0)
semaphore mutex_1, mutex_2, mutex_3, w, r ; (initial value = 1)
READER
P(mutex_3);
P(r);
P(mutex_1);
readcount := readcount + 1;
if readcount = 1 then P(w);
V(mutex_1);
V(r);
V(mutex_3);
reading is performed
P(mutex_1);
readcount := readcount - 1;
if readcount = 0 then V(w);
V(mutex_1);
WRITER
P(mutex_2);
writecount := writecount + 1;
if writecount = 1 then P(r);
V(mutex_2);
P(w);
writing is performed
V(w);
P(mutex_2);
writecount := writecount - 1;
if writecount = 0 then V(r);
V(mutex_2);
The
third readers-writers problem
In fact, the solutions implied by both problem statements result in
starvation — the first readers-writers problem may starve writers in the queue,
and the second readers-writers problem may starve readers. Therefore, the
third
readers-writers problem is sometimes proposed, which adds the constraint
that
no thread shall be allowed to starve; that is, the operation of
obtaining a lock on the shared data will always terminate in a bounded amount
of time.
A solution with fairness for both readers and writers might be as follows:
semaphores: no_waiting, no_accessing, counter_mutex ( initial value is 1 )
shared variables: nreaders ( initial value is 0 )
local variables: prev, current
WRITER:
P( no_waiting );
P( no_accessing );
V( no_waiting );
... write ...
V( no_accessing );
READER:
P( no_waiting );
P( counter_mutex );
prev := nreaders;
nreaders := nreaders + 1;
V( counter_mutex );
if prev = 0 then P( no_accessing );
V( no_waiting );
... read ...
P( counter_mutex );
nreaders := nreaders - 1;
current := nreaders;
V( counter_mutex );
if current = 0 then V( no_accessing );
Note that sections protected by counter_mutex could be replaced by a
suitable
fetch-and-add atomic instruction, saving two potential
context switches in reader's code.
Note also that this solution can only satisfy the condition that "no
thread shall be allowed to starve" if and only if semaphores preserve
first-in first-out ordering when blocking and releasing threads. Otherwise, a
blocked writer, for example, may remain blocked indefinitely with a cycle of
other writers decrementing the semaphore before it can.
===============================================================================
Travelling Salesman Problem
The Traveling Salesman Problem is
one of the most intensively studied problems in computational mathematics. These
pages are devoted to the history, applications, and current research of this
challenge of finding the shortest route visiting each member of a collection of
locations and returning to your starting point.
|
|
|
|
Given a collection of cities and
the cost of travel between each pair of them, the traveling salesman
problem, or TSP for short, is to find the cheapest way of visiting
all of the cities and returning to your starting point. In the standard
version we study, the travel costs are symmetric in the sense that traveling
from city X to city Y costs just as much as traveling from Y to X.
The simplicity of the statement of
the problem is deceptive -- the TSP is one of the most intensely studied
problems in computational mathematics and yet no effective solution method is
known for the general case. Indeed, the resolution of the TSP would settle
the P versus NP problem and fetch a $1,000,000 prize from the Clay
Mathematics Institute.
Although the complexity of the TSP
is still unknown, for over 50 years its study has led the way to improved
solution methods in many areas of mathematical optimization.
|
|
|
Much of the work on the TSP is
motivated by its use as a platform for the study of general methods that
can be applied to a wide range of discrete optimization problems.
This is not to say, however, that the TSP does not find applications in
many fields. Indeed, the numerous direct applications of the
TSP bring life to the research area and help to direct future work.
The TSP naturally arises as a
subproblem in many transportation and logistics applications, for example
the problem of arranging school bus routes to pick up the children in a
school district. This bus application is of important historical
significance to the TSP, since it provided motivation for Merrill Flood,
one of the pioneers of TSP research in the 1940s. A second TSP
application from the 1940s involved the transportation of farming equipment
from one location to another to test soil, leading to mathematical studies
in Bengal by P. C. Mahalanobis and in Iowa by R. J. Jessen.
More recent applications involve the scheduling of service calls at cable
firms, the delivery of meals to homebound persons, the scheduling of
stacker cranes in warehouses, the routing of trucks for parcel post
pickup, and a host of others.
Although transportation
applications are the most natural setting for the TSP, the simplicity of
the model has led to many interesting applications in other areas. A
classic example is the scheduling of a machine to drill holes in a circuit
board or other object. In this case the holes to be drilled are
the cities, and the cost of travel is the time it takes to move the drill
head from one hole to the next. The technology for drilling varies
from one industry to another, but whenever the travel time of the drilling
device is a significant portion of the overall manufacturing process
then the TSP can play a role in reducing costs. Other examples
from the TSP literature can be found on the web page "The
Traveling Salesman Problem".
To give the reader a sample of
some current applications of the TSP, we provide on the following pages a
list of some of the applied (and not-so-applied, but still fun) work that
has involved modules from the Concorde TSP library.
|
|
|
|
P vs NP Problem
Suppose that you are organizing
housing accommodations for a group of four hundred university students. Space
is limited and only one hundred of the students will receive places in the
dormitory. To complicate matters, the Dean has provided you with a list of
pairs of incompatible students, and requested that no pair from this list
appear in your final choice. This is an example of what computer scientists
call an NP-problem, since it is easy to check if a given choice of one hundred
students proposed by a coworker is satisfactory (i.e., no pair taken from your
coworker's list also appears on the list from the Dean's office), however the
task of generating such a list from scratch seems to be so hard as to be
completely impractical. Indeed, the total number of ways of choosing one
hundred students from the four hundred applicants is greater than the number of
atoms in the known universe! Thus no future civilization could ever hope to
build a supercomputer capable of solving the problem by brute force; that is,
by checking every possible combination of 100 students. However, this apparent
difficulty may only reflect the lack of ingenuity of your programmer. In fact,
one of the outstanding problems in computer science is determining whether
questions exist whose answer can be quickly checked, but which require an
impossibly long time to solve by any direct procedure. Problems like the one
listed above certainly seem to be of this kind, but so far no one has managed
to prove that any of them really are so hard as they appear, i.e., that there
really is no feasible way to generate an answer with the help of a computer.
Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP
(i.e., easy to check) problem independently in 1971.
