Interesting problems


Bug?

The following C code has a bug in it. Can you find it? (From The Practice of Programming by Brian W. Kernighan and Rob Pike)

int read(int *ip) {
    scanf("%d", ip);
    return *ip;
}

      .
      .
      .

insert(&graph;[vert], read(&val;), read(&ch;));

The middle state in one dimensional binary automata

I came across the following problem on Alife.

Consider a one dimensional binary automaton defined as follows:

Some thoughts on the solution:


Weighing coins

This problem is quite well known. However, I had not thought of it in an information theoretic way until I came across it in Elements of Information Theory by Thomas M. Cover and Joy A. Thomas.


Computing area

This problem came up at our local programming contest in 1997. The question was designed by David Neto.

Here is some same input:
e
n
w
s
.
n
e
s
e
n
e
s
s
w
w
w
n
.
and the output corresponding to the input:
1
5

How quickly can you compute the area of a polygon described in this fashion?
What is the order of the computation that needs to be performed?
How small a program can you write to perform this computation?


A self reproducing program

This problem is a classic.
Write a program in C that produces an identical copy of its source code as output.
Here is my version: sr.c. Take a look at it only after trying the problem yourself.


A doubly linked list with just a single pointer

This problem is a slightly modified version of a problem in Introduction to Algorithms by T. H. Cormen et al, 2nd edition, McGraw Hill, 2001.

A doubly linked list is usually implemented using two pointers: prev and next.
Can you implement a doubly linked list with just a single pointer?
You may assume that you are writing the doubly linked list code in C/C++.
You should also think about the portability of the code you are writing.
Apart from the memory savings, are there any other advantages to the single pointer implementation?


Back

Updated December 19, 2001