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:

Dining Philosophers Concurrency and Deadlocks	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?
Travelling Salesman P=NP	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?
Eight Queens Algorithm Design	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 Generals Communication Protocols	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?
Towers of Hanoi Recursion	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:

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 R₁ might have the lock, and then another reader R₂ request access. It would be foolish for R₂ to wait until R₁ was done before starting its own read operation; instead, R₂ 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 R₁ might have the lock, a writer W be waiting for the lock, and then a reader R₂ request access. It would be foolish for R₂ 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.

GOPAL KRISHNA SHARMA

Sunday, February 17, 2013

Classical Computer Science Puzzles