Tuesday, October 26, 2010

Quotes

This is my collection of quotes. gathered over the years.
I have strived not to record any of the soapy, flowery stuff that goes around as "inspirational" and "cute-sy". I have also hated any cheap slapstick or contradictions.
Many of the quotes below have a historical, political or scientific reference and relevance, and have an element of wit. I want them to reflect reality, so they have been uttered by (or have been attributed to) well-known personalities.
Here they are - Enjoy !


****


There are no crisis coming next week. My schedule is already full. -- Henry Kissinger.

****

Have you ever noticed ? Anyone walking slower than you is an idiot and anyone walking faster is a maniac.

****

Soap and education are not as sudden as a massacre, but they are more deadly in the long run. -- Mark Twain

****

Man is the only animal that blushes ... or needs to. -- Mark Twain

****

Show me a guy whos afraid to look bad, and I'll show you a guy you can beat every time. -Lou Brock

****

To doubt everything or to believe everything are two equally convenient solutions; both dispense with the necessity of reflection. -- H. Poincare

****

Woolsey-Swanson Rule: People would rather live with a problem they cannot solve rather than accept a solution they cannot understand.

****

The greatest love is a mother's, then a dog's, then a sweetheart's. -- Polish proverb

****

Superstition,idolatry, and hypocrisy have ample wages, but truth goes a-begging. -- Martin Luther

****

Once at a social gathering, Gladstone said to Disraeli, "I predict, Sir, that you will die either by hanging or of some vile disease". Disraeli replied, "That all depends, Sir, upon whether I embrace your principles or your mistress."

****

The second best policy is dishonesty.

****

Nothing in life is to be feared. It is only to be understood.

****

Certainly there are things in life that money can't buy,But it's very funny -- did you ever try buying them without money? -- Ogden Nash

****

Meekness is uncommon patience in planning a worthwhile revenge.

****

To a Californian, the basic difference between the people and the pigeonsin New York is that the pigeons don't shit on each other. -- From "East vs. West: The War Between the Coasts

****

He who knows others is wise.He who knows himself is enlightened. -- Lao Tsu

****

The fact that an opinion has been widely held is no evidence that it is not utterly absurd; indeed, in view of the silliness of the majority of mankind,a widespread belief is more often likely to be foolish than sensible. -- Bertrand Russell, in "Marriage and Morals", 1929

****

In War : Resolution
In Peace : Goodwill
In Victory : Magnanimity
In Defeat : Defiance
-- Winston Churchill

****

Associate with well-mannered persons and your manners will improve. Runwith decent folk and your own decent instincts will be strengthened. Keep the company of bums and you will become a bum. Hang around with rich people and you will end by picking up the check and dying broke. -- Stanley Walker

****

Good Judgment Comes From Experience. Experiences Comes From Bad Judgment.

****

Murphy's Law of Research: Enough research will tend to support your theory.

****

Don't interrupt me,
While I'm interrupting.
-- Winston Churchill.

****

Alcohol doesn't solve any problems,
but then again, neither does milk.

****

There are three kinds of lies: lies, damned lies, and statistics.
-- Benjamin Disraeli

****

I refuse to join any club that would have me as a member.
-- Groucho Marx

****

"Diplomacy" is letting them have it your way.

****

If you cannot convince them, confuse them.
-- Harry S. Truman

****

Common sense is the collection of prejudices acquired by age 18.
-- Albert Einstein

****

If you want a friend in Washington, get a dog.
-- Harry S. Truman

****

Politicians not born; they are excreted.
-- Cicero

****

Science is a differential equation and Religion is a boundary condition
-- Alan Turing

****

Time is God's way of keeping things from happening all at once.
-- Texas road-sign

****

The death of one man is a tragedy. The death of millions is a statistic.
-- Joseph Stalin

****

Death solves all problems - no man, no problem.
-- Joseph Stalin

****

Gratitude is a sickness suffered by dogs.
-- Joseph Stalin

****

When we hang the capitalists, they will sell us the rope
-- Joseph Stalin

****

In wartime, truth is so precious, that it has to be protected by bodyguards of lies.
-- Joseph Stalin

****

If I can't be loved, I'll find a way to be admired.

****

The trouble with the world is that the stupid are cocksure and the intelligent are full of doubt.
-- Bertrand Russell

****

Let us swear while we may, for in heaven it will not be allowed
-- Mark Twain

****

In Paris they simply stared when I spoke to them in French; I never did succeed in making those idiots understand their own language
-- Mark Twain

****

Any Universe simple enough to be understood cannot produce a mind complex enough to understand it.
-- John Barrow

****

Moderation is a fatal thing. Nothing succeeds like excess.
-- Oscar Wilde

****

Society often forgives the criminal; it never forgives the dreamer.
-- Oscar Wilde

****

Women love us for our defects. If we have enough of them, they will forgive us everything, even our gigantic intellects.
-- Oscar Wilde

****

The well bred contradict other people. The wise contradict themselves.
-- Oscar Wilde

****

A dreamer is one who can only find his way by moonlight, and his punishment is that he sees the dawn before the rest of the world.
-- Oscar Wilde

****

And he goes through life, his mouth open, and his mind closed
-- Oscar Wilde

****

Ridicule is the tribute paid to the genius by the mediocrities.
-- Oscar Wilde

****

A little sincerity is a dangerous thing, and a great deal of it is absolutely fatal.
-- Oscar Wilde

****

Don't give a woman advice: one should never give a woman anything she can't wear in the evening.
-- Oscar Wilde

****

How can a woman be expected to be happy with a man who insists on treating her as if she were a perfectly normal human being.
-- Oscar Wilde

****

Ah, well, then I suppose I shall have to die beyond my means.
-- Oscar Wilde

****

He has no enemies, but is intensely disliked by his friends.
-- Oscar Wilde

****

Be yourself; everyone else is already taken.
-- Oscar Wilde

****

Some cause happiness wherever they go; others whenever they go.
-- Oscar Wilde

****

We are all in the gutter, but some of us are looking at the stars.
-- Oscar Wilde

****

Consistency is the last refuge of the unimaginative.
-- Oscar Wilde

****

The true sign of intelligence is not knowledge but imagination.
-- Albert Einstein

****

The important thing is not to stop questioning.
-- Albert Einstein

****

I don't know, I don't care, and it doesn't make any difference!
-- Albert Einstein

****

Any man who reads too much and uses his own brain too little falls into lazy habits of thinking.
-- Albert Einstein

****

No problem can be solved from the same level of consciousness that created it.
-- Albert Einstein

****

Only two things are infinite, the universe and human stupidity, and I'm not sure about the former.
-- Albert Einstein

****

If the facts don't fit the theory, change the facts.
-- Albert Einstein

****

A perfection of means, and confusion of aims, seems to be our main problem.
-- Albert Einstein

****

After a certain high level of technical skill is achieved, science and art tend to coalesce in esthetics, plasticity, and form. The greatest scientists are always artists as well.
-- Albert Einstein

****

The only thing that interferes with my learning is my education.
-- Albert Einstein

****

If my theory of relativity is proven successful, Germany will claim me as a German, and France will declare that I am a citizen of the world. Should my theory prove untrue, France will say that I am a German, and Germany will declare that I am a Jew.
-- Albert Einstein

****

Never wear your best trousers when you go out to fight for freedom and truth.
-- Henrik Ibsen

****

The illegal we do immediately. The unconstitutional takes a little longer.
-- Henry Kissinger

****

The absence of alternatives clears the mind marvelously.
-- Henry Kissinger

****

In crises the most daring course is often safest.
-- Henry Kissinger

****

The conventional army loses if it does not win. The guerrilla wins if he does not lose.
-- Henry Kissinger

****

The ink of the scholar is more sacred than the blood of the martyr .
-- Muhammad

****

Half the lies they tell about me aren't true.
-- Yogi Berra

****

The various modes of worship, which prevailed in the Roman world, were all considered by the people as equally true; by the philosopher, as equally false; and by the magistrate, as equally useful .
--EDWARD GIBBON
(The Decline and Fall of the Roman Empire )

****

The question of whether a computer can think is no more interesting than the question of whether a submarine can swim.
-- E. W. DIJKSTRA

****

In times of tumult and discord bad men have the most power; mental and moral excellence require peace and quietness.
-- TACITUS

****

Most people are willing to pay more to be amused than to be educated.

****

It is a miracle that curiosity survives formal education.
-- ALBERT EINSTEIN

****

Creative minds have always been known to survive any kind of bad training.
-- ANNA FREUD

****

Everything that is really great and inspiring is created by the individual who can labour in freedom.
-- ALBERT EINSTEIN

****

The believer is happy; the doubter is wise.
-- Hungarian proverb

****

The more things a man is ashamed of, the more respectable he is.
-- GEORGE BERNARD SHAW

****

No object is so beautiful that, under certain conditions, it will not look ugly.
-- Oscar Wilde

****

The Heart was made to be broken.
-- Oscar Wilde

****

Take care to get what you like or you will be forced to like what you get.
-- GEORGE BERNARD SHAW

****

Truth comes out of error more easily than out of confusion
-- F Bacon

****

To achieve the impossible, one must think the absurd; to look where
everyone else has looked, but to see what no one else has seen.

****

Anything good in life is either illegal, immoral, or fattening.
-- Pardo

****

Research is what I'm doing when I don't know what I'm doing.
-- von Braun

****

It is easier to get forgiveness than permission.
-- Stewart's Law of Retroaction

****

When in doubt, predict that the present trend will continue.
-- Merkin's Maxim

****

If you want to make enemies, try to change something.
-- Woodrow Wilson

****

As the honourable senator from New York knows, I am in favour of the
constitution, institution, and pros ... perity.

****

In American politics you ask the rich for money and the poor for votes and
expect them both to believe you.
-- A. Lincoln

****

When you don't know where you're going any road will take you there.
-- Alice

****

The most beautiful things are those that madness inspires and reason
writes.
-- Andre Gide

****

If you want to make an apple pie from scratch, you must first create the universe.
-- Dr. Carl Sagan

****

Believe those who are seeking the truth. Doubt those who find it.
-- Andre Gide

****

Judge a man by his questions rather than by his answers.
-- Voltaire

****

Not everyone who wanders is lost.
-- J.R.R Tolkien

****

Intelligence is not to make no mistakes, but quickly to see how to make them good.
-- Bertolt Brecht

****

A mask tells us more than a face.
-- Oscar Wilde

****

The old believe everything; the middle aged suspect everything: the young know everything.
-- Oscar Wilde

****

If we begin with certainties, we shall end in doubts; but if we begin with doubts, and are patient in them, we shall end in certainties.
-- Francis Bacon

****

Iron rusts from disuse; water loses its purity from stagnation ... even so does inaction sap the vigour of the mind.
-- Leonardo da Vinci

****

Progress is man's ability to complicate simplicity.
-- Thor-Heyerdahl. Norwegian ethnologist, 1914-2002

****

Life's disappointments are harder to take when you don't know any swear words.
-- Calvin & Hobbes. Fictional characters from comic series

****

The thing that is really hard, and really amazing, is giving up on being perfect and beginning the work of becoming yourself.
-- Anna Quindlen. American bestselling Author and Journalist, b.1953

****

Art is the most intense mode of individualism that the world has known.
-- Oscar Wilde

****

If you are going to achieve excellence in big things, you develop the habit in little matters. Excellence is not an exception, it is a prevailing attitude.
-- Colin Powell - American Military leader and Statesman. Chairman of the US Joint Chiefs of Staff (1989-93). US Secretary of State (2001-2004). b.1937

****

You know you've read a good book when you turn the last page and feel a little as if you have lost a friend.
- Paul Sweeney.

****

Risk! Risk anything! Care no more for the opinions of others, for those voices. Do the hardest thing on earth for you. Act for yourself. Face the truth.
- Katherine Mansfield. New Zealander Writer, 1888-1923

****

If we're growing, we're always going to be out of our comfort zone.
- John Maxwell. American Author and motivational speaker

****

One of the most important lessons that experience teaches is that, on the whole, success depends more upon character than upon either intellect or fortune
- William Edward Hartpole Lecky. Irish Historian and Essayist. 1838-1903

****

To sin is a human business, to justify sins is a devilish business.
- Leo Nikolaevich Tolstoy. Russian moral Thinker, Novelist and Philosopher, notable for his influence on Russian literature and politics. 1828-1910

****

I like men who have a future and women who have a past
- Oscar Wilde.

****

All that we are is the result of what we have thought. The mind is everything. What we think we become.
- Buddha.

****

He who does not understand your silence will probably not understand your words.
- Elbert Hubbard. American editor, publisher and writer, 1856-1915

****

Do not worry about your difficulties in mathematics, I assure you that mine are greater.
-Einstein

****

Computers are useless. They can only give you answers.
-Pablo Picasso

****

Haste is of the devil. Slowness is of God.
-H L Mencken

****

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them.
-Laurence J. Peter

****

There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.
-C.A.R. Hoare

****

I have always found that plans are useless, but planning is indispensable.
-Dwight Eisenhower

****

It's not at all important to get it right the first time. It's vitally important to get it right the last time.
-Andrew Hunt and David Thomas

****

Don't worry about the world coming to an end today. It's already tomorrow in Australia.
-Charles Schulz

****

Many journalists have fallen for the conspiracy theory of government. I do assure you that they would produce more accurate work if they adhered to the cock-up theory.
-Sir Bernard Ingham

****

A painting in a museum hears more ridiculous opinions than anything else in the world.
-Edmund de Goncourt

****

Every time I paint a portrait, I lose a friend
-John Singer Sargent

****

"Therefore" is a word the poet must not know.
-Andre Gide

****

One does not discover new lands without consenting to lose sight of the shore for a very long time.
-Andre Gide

****

Nothing is so silly as the expression of a man who is being complimented.
-Andre Gide

****

Nothing prevents happiness like the memory of happiness.
-Andre Gide

****

It is unthinkable for a Frenchman to arrive at middle age without having syphilis and the Cross of the Legion of Honor.
-Andre Gide

****

It is better to be hated for what you are than to be loved for something you are not.
-Andre Gide

****

A samurai once asked Zen Master Hakuin where he would go after he died. Hakuin answered 'How am I supposed to know?'
'How do you not know? You're a Zen master!' exclaimed the samurai. 'Yes, but not a dead one,' Hakuin answered. ( - Zen)
****

Do not seek the truth, only cease to cherish your opinions. ( - Zen)
****

If you understand, things are just as they are; if you do not understand, things are just as they are. ( - Zen)
****

It takes a wise man to learn from his mistakes, but an even wiser man to learn from others. ( - Zen)
****

The ten thousand questions are one question. If you cut through the one question, then the ten thousand questions disappear. ( - Zen)
****

The tighter you squeeze the less you have. ( - Zen)
****

Though the bamboo forest is dense, water flows through it freely. ( - Zen)
****

To do a certain kind of thing, you have to be a certain kind of person. ( - Zen)
****

To follow the path, look to the master, follow the master, walk with the master, see through the master, become the master. ( - Zen)
****

When the pupil is ready to learn, a teacher will appear. ( - Zen)
****

When you reach the top, keep climbing. ( - Zen)
****

A weed is a plant whose virtues are only waiting to be discovered. ( - Zen)
****

Women may spend their whole lives looking for true love. If you wish for true love, learn to love yourself. ( - Zen)
****

You do not wait for fulfillment, but brace yourself for failure. ( - Zen)
****

Zen students must learn to waste time conscientiously. ( - Zen)
****

Truth is beautiful; without doubt, but so are lies - Emerson
****

"There is no security on this earth; there is only opportunity." (Douglas MacArthur)

****

"Economic history is a never-ending series of episodes based on falsehoods and lies, not truths. It represents the path to big money. The object is to recognize the trend whose premise is false, ride that trend, and step off before it is discredited." (George Soros)

****

A civilized society is one which tolerates eccentricity to the point of doubtful sanity.
Robert Frost

****

If you want peace, prepare for war.
Roman Aphorism

****

Thursday, October 21, 2010

The man who loved china - Simon Winchester

I just finished reading a lively biography of Prof. Joseph Needham of Cambridge (the old one). Titled "The man who loved china", written by Simon Winchester. Winchester describes the life and work of the Prof. Needham in manner that kept me hooked on to it for the whole week, until I finished it. He is plain blunt at times, but always colorful in describing the life and times of Prof. Needham.
I hadn't heard about the 'sinophile' professor before I read this book. But the man is most remarkable. The professor began as a researcher in bio-chemistry at the Caius college, Cambridge. Prof. Needham was eclectically intellectual, charming, outspoken and eccentric. When he had made his mark in the top-line research in his area in his early years, he shifted track. Enticed and egged on by his chinese mistress, he learnt the Chinese language and dabbled with calligraphy. He undertook a dangerous mission into China at the height of japanese invasion in the second world war. He pursued a deep study of China, its history of scientific development and eventually creating systematic and detailed notes. 24 large volumes of the scientific and intellectual history of China were written and published by him. He smoked cigars, researched, ventured, lectured and lived a life of fruitful writing till the very end.

He lived a long life, but I found the sheer volume of his research and intellectual output staggering. His roving eye for pretty women did not waver even at age 95. The author tells that at age 94, when the professors wife died, he married his chinese mistress, after having been in courtship for more than 50 years. When she too died, he made proposals to three other women and all of them politely declined.

I got glimpses of the life of the 'dons' at Cambridge university from the book. It sounds like utopia for the serious researchers - wonder if the IITs are a poor imitation.

The sad part is that Prof. Needham was a socialist (but not a communist according to the author. I tend to disagree). He was right from the "red's nest" that cambridge seems to have become prior to 1950s. I am dismayed by the fact that communism had so much of appeal to the intellectual class, in that period of history. Its not as if the murderous excesses of the Stalins and Maos were unknown to the world at large. But their heads were buried deep in the sand. Prof. Needham was found to be an unequivocal and fanatic supporter of almost everything that Chinese government stood for. He was certainly charmed and in love with chinese history, science and language, but mistook the voice of the chinese communist governments as the voice of the chinese people.

There is also a fact that the professor could not really get to the analysis of why chinese contemporary science lagged behind so much, even as science in its history was so far ahead of europeans. One notable cause was that chinese did not develop a competitive mercantile class who needed to innovate to stay in business. The biggest ambition of medival chinese youth was to join the corrupt and burgeoning bureaucracy and in that manner, earn the security and continuance of the government establishment. Justs struck me that this idea runs parallel to the same trend in maharashtrian youth. And the lag of marathis among other communities is also evident.

Prof. Needham has published the most comprehensive and systematic treatment of chinese scientific history. I don't think I would have the stamina to read up on all of those 24 volumes, but Winchester's byte sized offering suits me great. Its something similar to what I thought on reading "Koba the dread" by Martin Amis. I could not imagine myself reading all the volumes by Solzenitsyn on life in the Gulags. Amis's work covered all of it in a far more colourful and concise manner. Compilations from research are needed but commentaries on those same research subjects, if well-written are much more worth my time. A big thank you to the Amis's and Winchester's.

Saturday, October 2, 2010

Project Euler problem involving optimization

This is about my try at a moderate level programming problem from Project Euler, problem # 15.
With usual approach (and attitude), I thought I should be done in 15 minutes on this one, but stretched me for six times that estimate.
Problem is about finding the number of routes through a n*n grid, starting from top-left and ending at bottom-right (for n=20).

My sequence of attempts -
1/ Simplest recursive function that traversed right and down and counted routes on reaching destination. Too bad, it took unacceptably long for n=20 case. In retrospect, I should have avoided coding this approach, knowing the size of inputs.
2/ Making a recurrence relation, with the hope that I would not even need a program to calculate this. That is, if the problem of size N can be expressed in terms of problems of (size < N) and the if I could get a closed form, simple calculation would have done it.
I got this -
For a grid size (m*n),
T(m, n) = T(m-1, n)+T(m, n-1) ..... m <> n
2*T(m-1, n) ..............m==n

For the case when m==n, we have utilized the symmetry : T(m-1, n)=T(m, n-1).

Bringing this recurrence to a closed form is beyond my technical means today, so I modified the code to follow this recurrence and calculate. This too failed since the size n=20 was overwhelming my 64-bit dual core server even then.

3/ After almost giving up after some frustrating debugging and some old fashioned pen-paper workout of the recursion, I wanted to create a cache of T(m, n) values that were getting calculated. Certainly, many values were being repeatedly calculated in various "branches" of the recursion. In this case, the cache needed was no more bigger than n*n=400. So now the code only calculated a T(m, n) if it was being caclulated for the first time and re-used that.
Now the code was terminating in a flash even for large input sizes, but throwing wrong answers.
4/ The last mistake was about the return data-type of the function, that needs to be kept in min for almost all Euler problems. It was a silly 'int'. C++ did not warn of truncation, never mind what the compiler option was.

So I have a few things to take home today, caching at appropriate places being the most important of them.

Wednesday, September 1, 2010

long time


Just made it a point to put in a snap of my little princess here, born on 2nd Nov 2009 ...

Saturday, June 20, 2009

File locking protocol with only shell scripting primitives

Writing this post out of some faint feeling of guilt and disappointment of not being able to keep up to the writing habit and discipline. It happens to be my first post ofthe year 2009. A lot many things have happened over these months, but as usual,the more things change, the more they seem to remain the same. So I jump directly to the point that pushed me to post this.


Encountered a problem today, regarding certain shell script running on a linux box.The script could be invoked by many users simultaneously. Now the problem is that the script used to write some text to a file. The changes could be updates through a redirect ('>>') or even deletes through 'gnu_sed'. As you might have guessed, the file being written to by the script was common to all users as well. I was looking for a way to serialize the 'write' access. Several incidents showed that multiple concurrent users eventually messed up the file contents through the concurrent shell script invocations.


Now, someone suggested a file locking mechanism. Each invocation of the script will lock the file and other invocations wait till it is released. I don't know for sure, but there is no shell interface for locking some file. I am aware of seeing something like that interface only at the system/C programming level through fcntl/flock calls. I had to think for a while before getting to the following algorithm, that is purely based on shell scripting primitives and guarantees a predictable first-in-first-out ordering. It also ensures that starvation cannot occur. Deadlocks are out of question, with there being only one resource to lock.


Here it is,
1/ Lets assume that a shell script (S) modifies the file (F) and we have a set of processes {P0, P1, ... Pn} that can concurrently invoke S to modify F according to some arbitrary logic.
2/ We make a kind of wrapper script (S2) to control access to S and add some logic.
3/ S2 works like this,
It creates a temporary file in the same directory with a name whose uniqueness is guaranteed e.g - a file named lock., pid - known quantity of the process P.
4/ Next, it checks for the creation dates on all lock.<*> files in that directory.
case 1 : If it finds that the date on its own lock file is earliest, it can invoke the script.
case 2 : If it finds another lock file with an earlier date, it sleeps for a configurable duration and repeats step '4/' once it wakes up. If the dates of another lock file co-incide and they are earliest among all locks, we can make the process with the lower pid the winner. The higher pid process waits and repeats 4/ after sleep.
5/ S2 finally invokes S which does all he work in exclusive mode for 'writes'.
6/ Delete the lock file created by self (having the own pid) after done and S returns control to S2.



We can assert that the FIFO ordering will be maintained, ensured by having the creation dates as the decider.Starvation is prevented by having the processes first create a lock file and thus marking the availability for ascript invocation.A process also has the luxury of relinquishing lock on the file by simply deleting its lock file, regaining lock by simply re-creating the lock file when it needs and queueing up again for access. If a process wants to justread the file, we can allow the script to make a copy of the file and release the lock as soon as possible.



Issues -
1/ The script S should be 'well-behaved'. Otherwise, it can simply use 'exit' to finish the processinstead of returning control to S2 for cleaning up the lock. file of that process. Ifany such pid file is left out in the system ,we can end up with a total starvation because noprocess will find its lock file better than the dead process' lock. A simple workaround is thatif a process P finds that is is deprived of a lock because of only one other process P, it verifies if the process who owns the lock P is still alive with the 'ps -ax' commands.If the process P is not alive, this process P can delete the lock file created by the dead process and assumeto be owner. Only one process will do this check because only one process will be in the 'second' position from gaining access.



2/ Another problem is much tougher to crack. The overall response/efficiency of this locking protocol heavily dependson the sleep time for the processes. The process has to go to a sleep if it finds that the script is already locked. We need the sleep time to be equal to the approximate time that the script S takes to run. If the sleep time is too low, processes will spend computing resources checking locks too frequently, only to find that theyhave to continue sleeping. If it is too high, the processing is under-utilised. In any case, the sleep has to happen, since I cannot find a way that the OS notifies the sleepingprocesses with this scheme. The OS does not participate in any locking here so it cannot help. Overall, If the requesting processes are assumed to be arriving frequently and steadily, then I will prefer having the sleep time on the higher-end. This is because once enough processes are sleeping, there will be a steady state when enough processes keep waking up and continue processing without the under-utilization problem. On the other hand, if the incoming processes are bursty in nature, then I think the sleep time needs tobe kept on the lower-end.
The above protocol certanly solves the central problem mentionned in the link, http://members.toast.net/art.ross/rute/node24.html.


- QED -

Friday, September 26, 2008

Challenge problem - From a classic Steven Krantz book -

I have simply been unable to crack this one, particularly the general version of this problem... any hints ?
You have six points on a piece of paper. Every point will be joined to every other point by either by a red line segment or by a blue line segment. You can colour any line in anyway you choose. Show that there will have to be either be a triangle that is all blue or a triangle that is all red.
Formulate a generalization of the last problem. Suppose that you have k colors. How many points are required to guarantee that the process of joining all possible pairs of points with line segment segments of one of these colors will guarantee that there is a triangle of just one color?

Saturday, September 13, 2008

Interesting problems - first batch

Housie Magic -
This one arose from a party in my company, where we played Housie. The game goes like this - Every participant is distributed Housie tickets, each of which has 15 random numbers (distinct on a given ticket) printed on them. Numbers are between 1 to 100. Next, random numbers in the same range are selected and the numbers are called out. All participants who have the number on their ticket cross them. The first participant who gets all numbers crossed on their own ticket wins, and gets the prize.
Certainly, all numbers on the ticket are random and those called are random too. So everyone has an equal chance of winning. But there is a twist .....
What if you are allowed to take up more than one ticket ? You then get a bigger range of numbers to cross. Does that increase your chances of winning the prize ? Remember that to win, you need to have all numbers on any single ticket crossed.
Comments welcome ...
Sorting -
I ask this one for interviews and get varying answers... Given an array of integers (of size N), what is the most efficient algorithm to find out the 'K' largest numbers ? Note that K <= N, K > 0.
We don't want the largest K numbers to be sorted by themselves, just find the largest set. Is there a way to find the K numbers in less than O(N*K) ?