*** MOVED ***

NOTE: I have merged the contents of this blog with my web-site. I will not be updating this blog any more.


A Bold Question

Does anyone know why comics writers put one or two words in every sentence in every dialogue in bold typeface?

For example, "Watchmen" is perfect in every other way except for this flaw. I tend to translate bold typeface as indicating an emphasis on a word or a phrase, so it is rather jarring to read dialogues mouthed by characters in comics.

Why do they do this?


RMS, GPLv3 and Bangalore

Richard Stallman will be talking about "Free Software: Current Status and Challenges" at 11 AM in the Faculty Hall in IISc Bangalore tomorrow (Saturday, 19th August 2006). I came to know of this event just this afternoon and I understand that this is too short a notice, but I hope to meet some of the fellow Free Software enthusiasts in Bangalore.

On a related note, Bangalore will also be hosting the Fourth International Conference on GPLv3 on the 23rd and 24th August 2006, this time in IIM-B. Both Richard Stallman and Eben Moglen will be presenting in this event. Since this falls in the middle of a work week (Wednesday/Thursday), I will have to skip it.


Good Math, Bad Math

I came to know of Mark Chu-Carroll's "Good Math, Bad Math" blog via a post in "Programming Musings", the blog of José Antonio Ortega Ruiz. Mark writes mostly about mathematics, the theoretical foundations of programming, debunking bad use of mathematics in popular and not-so-popular media, etc.

I find many of Mark's articles very interesting to read, though many others go way over the top of my head. Some of his recent articles that I found really interesting include one that shows how absurd arithmetic with Roman numerals can be, one on Poincaré Conjecture, some in the "Friday Pathological Programming Language" series, one on zero, one on i, one on e, one on φ, one on Ω, one on π, one on continued fractions, etc. The old home for the GM/BM blog contains many more interesting and insightful articles on math and programming theory. What an amazing guy!

Highly recommended.


Balancing Acts

You are given 8 billiards balls, numbered 1 to 8, identical in shape and size. All but one weigh exactly the same. The odd ball is either heavier or lighter than the others. Using just three weighings on an ordinary two-pan balance, find the odd ball out as well as whether it is heavier or lighter than the others.

If you solve the previous puzzle, solve the same problem for 12 billiards balls (instead of 8) while keeping the maximum weighings to just three. Yes, there is a solution for this puzzle - if you give up, you can find the solution here.

For the first puzzle (with just 8 billiards balls), here is my solution (obfuscated using rot-13):
  1. Xrrc onyyf ahzorerq 1, 2 naq 3 ba bar cna naq 4, 5 naq 6 ba gur bgure.
  2. Vs gurl onynapr, gurl ner nyy abezny naq bar bs 7 naq 8 vf gur bqq onyy. Jrvtu 7 ntnvafg 1.
  3. Vs gurl onynapr, 8 vf gur bqq onyy naq lbh pna svaq vgf bqqvgl ol jrvtuvat vg ntnvafg 1.
  4. Vs gurl qba'g onynapr, 7 vf gur bqq onyy naq lbh jvyy vzzrqvngryl xabj vs vg vf urnivre be yvtugre guna gur bguref.
  5. Vs gur onyyf qba'g onynapr va fgrc #1, bar cna jvyy tb qbja. Jvgubhg ybff bs trarenyvgl, nffhzr guvf vf gur bar pbagnvavat 1, 2 naq 3. Rvgure bar bs 1, 2 naq 3 vf urnivre guna gur bguref be bar bs 4, 5 naq 6 vf yvtugre guna gur bguref.
  6. Xrrc 1 naq 5 ba bar cna naq 4 naq 2 ba gur bgure. Xrrc 3 naq 6 nfvqr.
  7. Vs gurl onynapr, bar bs 3 naq 6 vf gur bqq onyy. Sebz fgrc #5, jr pna pbapyhqr gung rvgure 3 vf urnivre guna gur bguref be 6 vf yvtugre guna gur bguref. Jrvtu 3 ntnvafg 1.
  8. Vs gurl onynapr, 6 vf gur bqq onyy naq vf yvtugre guna gur bguref.
  9. Vs gurl qba'g onynapr, 3 vf gur bqq onyy naq vf urnivre guna gur bguref.
  10. Vs gur onyyf qba'g onynapr va fgrc #6, rvgure gur cna jvgu 1 naq 5 jvyy tb qbja be gur cna jvgu 4 naq 2 jvyy tb qbja.
  11. Vs gur cna jvgu 1 naq 5 tbrf qbja, sebz fgrc #5 jr pna pbapyhqr guna rvgure 1 vf gur bqq bar bhg naq vf urnivre guna gur bguref be 4 vf gur bqq bar bhg naq vf yvtugre guna gur bguref.
  12. Jrvtu 1 ntnvafg 8. Vs gurl onynapr, 4 vf gur bqq bar bhg naq vf yvtugre guna gur bguref. Vs gurl qba'g, 1 vf gur bqq bar bhg naq vf urnivre guna gur bguref.
  13. Vs gur cna jvgu 4 naq 2 tbrf qbja va fgrc #10, sebz fgrc #5 jr pna pbapyhqr gung rvgure 2 vf gur bqq bar bhg naq vf urnivre guna gur bguref be 5 vf gur bqq bar bhg naq vf yvtugre guna gur bguref.
  14. Jrvtu 2 ntnvafg 8. Vs gurl onynapr, 5 vf gur bqq bar bhg naq vf yvtugre guna gur bguref. Vs gurl qba'g, 2 vf gur bqq bar bhg naq vf urnivre guna gur bguref.
  15. Va fgrc #5, vs 4, 5 naq 6 tb qbja, pneel bhg gur erznvavat fgrcf ol fjnccvat 1, 2 naq 3 jvgu 4, 5 naq 6 erfcrpgviryl.
I confess that I had to finally give up while trying to solve the 12-ball variation in the second puzzle.


Lost Books on Computer Programming

I am not into old books on computers the way Graydon seems to be, but I still feel sad that the current generation of programmers will most likely never get exposed to some of the great books on computer programming that I was able to read when I was young.

At least here in Bangalore, it is almost impossible to buy these books from a bookshop unless they have either retained very old stock or are selling second-hand books. For example, here are a few books that seem to be very difficult to buy these days in Bangalore:
  1. "The Elements of Programming Style", Brian Kernighan and P. J. Plauger.
  2. "Algorithms + Data Structures = Programs", Niklaus Wirth.
  3. "A Discipline of Programming", Edsger Dijkstra.
  4. "The Science of Programming", David Gries.
  5. "Communicating Sequential Processes", C. A. R. Hoare.
  6. "How to Solve it by Computer", R. G. Dromey.
  7. "Microprocessors: A Programmer's View", Robert B. K. Dewar and Matthew Smosna.
(I am sure I have not listed a lot of other interesting and important books here, but these are the names that readily spring to my mind.)

Of these, I have only been able to buy Dromey's book so far. In my opinion, it is one of the most under-appreciated books in computer science and deserves to be read by every novice programmer. It is a perfect complement to the usual textbooks for a Data Structures and Algorithms course.

A kind soul has scanned in the pages from "A Discipline of Programming" and made them freely available to everyone. The electronic version of "Communicating Sequential Processes" is now freely available for download. But I still wish I had these books "for real".

By the way, Robert Dewar hopes to produce an updated version of "Microprocessors: A Programmer's View" sometime soon.

Alarmingly, some relatively recent books are also becoming difficult to find these days. For example:
  1. "Programming Pearls", Jon Bentley.
  2. "The Practice of Programming", Brian Kernighan and Rob Pike.
I also note rather sadly that the "XYZ Unleashed" and "Learn ABC in 3 Days" type books are still going strong even after almost a decade.

Thankfully, the "The Art of Computer Programming" (TAOCP) series by Donald Knuth is still easily available. "Structure and Interpretation of Computer Programs" (SICP) by Harold Abelson, Gerald Jay Sussman and Julie Sussman is also visible in bookshops from time to time.

I think the strong sales of TAOCP are more due to the "classic book" effect than anything else. To quote Mark Twain, "A classic is a book that everyone wants to have read but no one wants to read". If there are people who have actually read TAOCP, they seem to have been rather successful at avoiding to meet me. To quote Bill Gates, "If you have read The Art of Computer Programming from cover to cover, send me your resume!".


The Suez Crisis and The IBM PC

"Those who cannot remember the past are condemned to repeat it."

A recent issue of The Economist featured the article "An Affair to Remember" about the Suez crisis (also known as the Sinai War) of 50 years ago. I found it to be a very interesting read. It provides some great insights into the events precipitating the formation of the European Union, the establishment of the US and the Soviet Union as the only superpowers, the reasons for the different way that the British and the French view the US, etc. I also found it a bit surprising how the then British prime minister Anthony Eden and his foreign secretary blatantly lied to the House of Commons about the sinister collusion between Britain, France and Israel that led to the war.

In the light of the recent events, it is amusing to find out that at that time the US actually went via the UN to put a stop to this uncalled-for agression by the Israelis, the British and the French against the Egyptians. It was apparently also the last time that the US actually acted against Israel while intervening in a war.

How times change.

The same issue of The Economist also featured the article "Getting Personal" about the 25th anniversary of the introduction of the IBM PC. The first IBM PC was apparently priced at USD 1,565, had 16K of RAM, used audio cassettes for storage (a floppy drive was optional) and featured “green phosphor characters for reading comfort” (i.e. text-only, no graphics). It wasn't until Lotus 1-2-3 was introduced about 1.5 years later that the PC really took off. These days you are overwhelmingly more likely to see a PC than an Apple Macintosh or any other kind of personal computer.

I first got to work on an (8086-based) IBM PC in 1990. It struck me as rather ugly and severely lacking. I was used to the excellent BBC Micro and the primitive CGA display of the IBM PC and the PC speaker were nothing compared to what was available on the Beeb. As a novice programmer, it was also very irritating to find how different BASICA was from BBC BASIC. All the "VDU" (graphics) and "ENVELOPE" (sound) tricks I had learnt on the Beeb were also useless on the PC.

It was not until I got to work on the 80386-based IBM PCs and play Prince of Persia and Wolfenstein 3D that I really began to enjoy working on the PC. Borland's Turbo Pascal and Turbo C/C++ were excellent tools that made programming on the PC much easier. After the advent of Linux, there was no question about what my first personal computer was going to be.


Another River Crossing Puzzle

Most of us would have seen the standard river crossing puzzle. However, Prasadini recently sent me another river crossing puzzle (Flash animation) that I think is far more challenging.

A father and his two sons, a mother and her two daughters, a thief and a policeman are on one side of a river. There is a boat by the river bank, but it can only take two people at a time. Only the father, the mother and the policeman know how to operate the boat. The father can not be with any of the girls without their mother around. The mother can not be with any of the boys without their father around. The thief can not be with anyone else without the policeman around. How can you get everyone across to the other side of the river?

Start the game by clicking on the big round blue button. Click on a person to get him or her on or off the boat. Click on the levers to get the boat to move.

It took me a fair bit of time to crack it and here is my solution (obfuscated using rot-13):
  1. Gur Guvrs naq gur Cbyvprzna pebff bire.
  2. Gur Cbyvprzna pbzrf onpx (Gur Guvrs qbrf abg eha njnl jura yrsg nybar!).
  3. Gur Cbyvprzna naq n obl pebff bire.
  4. Gur Cbyvprzna naq gur Guvrs pbzr onpx.
  5. Gur Sngure naq gur bgure obl pebff bire.
  6. Gur Sngure pbzrf onpx.
  7. Gur Sngure naq gur Zbgure pebff bire.
  8. Gur Zbgure pbzrf onpx.
  9. Gur Guvrs naq gur Cbyvprzna pebff bire.
  10. Gur Sngure pbzrf onpx.
  11. Gur Sngure naq gur Zbgure pebff bire.
  12. Gur Zbgure pbzrf onpx.
  13. Gur Zbgure naq n qnhtugre pebff bire.
  14. Gur Guvrs naq gur Cbyvprzna pbzr onpx.
  15. Gur Cbyvprzna naq gur bgure qnhtugre pebff bire.
  16. Gur Cbyvprzna pbzrf onpx.
  17. Gur Cbyvprzna naq gur Guvrs pebff bire.
See if you can come up with a better solution.


Optimising Linker Load Times

Last week's LWN.net Weekly Edition had a nice article on optimising linker load times by John Richard Moser. It was based on some recent features added to the linker in GNU binutils. It explains the kind of things that most of us never bother to learn about, but which can affect the loading times of our applications and shared libraries. As someone noted in the comments, an informative read even by LWN.net's usually high standards.