Classic Computer Science Puzzles

These puzzles take me back to my CS classes from college. Here’s how I encountered them:

Dinning Philosophers - Operating System Theory
Traveling Salesman - Algorithm Logic
Eight Queens - Algorithm Logic
Two Generals - Operating System Theory
Towers of Hanoi - Data Structures

The interesting thing about Towers of Hanoi is that I’ve written an implementation for the problem in C,C++,C#,Java and Scheme. Each, of course, got significantly easier!

The interesting thing about Towers of Hanoi is that I’ve written an implementation for the problem in C,C++,C#,Java and Scheme. Each, of course, got significantly easier!

Javier, sounds like you’ve got a blog post on your hands to me :slight_smile:

I’d totally forgotten about To Mock A Mockingbird since I read it in a library when I was 12.

This post’s reason enough for me to buy a copy (and also Lewis Caroll’s “Symbolic Logic” and “The Game of Logic” since I just remembered that as well and it qualifies me for free delivery)

You didn’t mention the firing squad problem:
http://en.wikipedia.org/wiki/Firing_squad_synchronization_problem

Here’s a variation that’s actually a very boring-looking puzzle with a cute story for a solution, as opposed to Byzantine Generals or Traveling Salesman, which are the other way around.

Unfortunately, this means that by reading the amusing story, you spoil the puzzle for yourself; but until you read the story, the puzzle may seem uninteresting!

http://groups.google.com/groups?selm=gq8aevcqsav78sv2ko1e02lahv24vfthob@4ax.com
(several messages down in the thread)

While I appreciate the fact that there is a group of people out there doing those kinds of things - I want to make sure the interview is appropriate for the job. I do want people to know that there are well known problems with well known solution. I don’t really care if they can solve them in an interview situation. In my 20 years in many different industries I can count on one hand the number of times I’ve needed to know these types of things. That doesn’t mean the work is simple or uninteresting, just different.

Hey Andy…

you say 99.9999999% is possible, but not 100%.

You never defined the field as having to be pure mathematics.

we all know 99.999… = 100… In the real world, you don’t need infinite 9s to accept that equality.

Mechanical Engineers get really precise with dimensions on parts, but there’s always a variance accounted for. There’s absolutely nothing in the real world that can exist without some varience… Even in a computer, floating point numbers will make a high enough order of 99.999… be 100.

So basically, the problem is not impossible in the real world. It’s not impossible in a computer world. It’s not impossible in an engineer’s world…The only one who would fail is the mathematician?

“we all know 99.999… = 100… In the real world”

It does in the math world too…

x = 99.999…
10x = 999.999…
10x-x = 999.999… - 99.999…
9x = 900
x = 100
99.999… = 100

In real life, they are both on a mountain with nothing in between, so they could just wave flags and start running :stuck_out_tongue:

By the way, if anyone ever answered my riddle, I would probably be suspicious that they already knew it. I think the answer that would give me the most confidence in a candidate would be “I don’t know, but if you give me 5 minutes with Google, I’ll have a solution for you.”

@Wayne “I still think even these are useless for most jobs since these puzzles focus on comp sci problems and hardly any jobs do. Most jobs are about building CRUD application. What good is puzzle solving if you job revolves around storing stuff in a database, reporting on it and transforming it?”

Sure, few of us need to directly solve a problem such as the Towers of Hanoi, but that isn’t the point, is it? The idea is that they exercise, as Hercule Poirot called them, “the little gray cells.” I’m not automatically looking for a “pattern” to apply in my day-to-day programming, but puzzle solving, I believe, is good for the brain.

the generals should decide when to attack before they get to the freakin’ valley. duh!

Hey Now Jeff,
Towers of Hanoi is such a classic. The 8 queens is really good too (I enjoy chess). One of my favorite puzzles I was presented in my university days that has fundamental CS concepts is the ‘Birthday Paradox’ there are quite a few variations here are two http://en.wikipedia.org/wiki/Birthday_paradox http://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Science/Birthday_probability_question
Thx,
Catto

I just finished writing up an article on The Byzantine Generals problem, which is similar to the Two Generals problem - it’s an exercise in agreement protocols.

http://marknelson.us/2007/07/23/byzantine/

Lamport, the guy who published a nice solution that is more or less the state of the art, seemed kind of miffed that the Dining Philsophers gets so much attention, and he decided that the way to get people to pay attention to your algorithm was to turn it into a story problem:

http://research.microsoft.com/users/lamport/pubs/pubs.html#byz

Lambda calculus isn’t just a core concept of lisp, it’s the smallest universal programming language. Lambda calculus is universal in the sense that any computable function can be expressed and evaluated using it, just as in a Turing Machine (the two are equivalent).

The Knapsack problem - dynamic programming.

http://en.wikipedia.org/wiki/Knapsack_problem

I liked the generals’ communication problem, but then, I got to study internetworking under a professor who did his PhD work under Comer. It brought back memories =]

As for problems that you missed, I was reminded of a problem I was given as part of an interview for a certain Seattle-based company.

You are in a room with 2 buckets. Each one contains 100 marbles - one bucket having blue marbles, the other having white.

Arrange the marbles in the buckets so that the next person coming through the door has the highest probability of picking a blue marble at random. Additionally, roughly, what is the probablity of them picking a blue marble?

I might regret this, but:

Put all white marbles at bottom of each bucket, top off each bucket with the blue marbles. The probability is then 1 that the next marble picked is blue.

(Assuming another bucket to stop marbles spilling all over floor :slight_smile: )

@Bladejester: half the white marbles in the bottom of each bucket and fill-em-up with blue?

I’ve just come from reading the dining philosophers problem in Algorithmics: The Spirit of Computing!

FizzBuzz