'(The Blog) With No Name', perhaps best described as a stream of notes and thoughts - 'remembered, recovered and (sometimes) invented'.

Monday, May 30, 2005

Jasraj and Panini - 'Devotional Linguistics'?

I recently bought what appeared to be a cassete of Bhajans dedicated to Lord Shiva - the artist, Pt. Jasraj. The blurb said it also contained '108 Maheshwara Sutras'. At home, I found that there were bhajans only on one side of the cassette (and they were impressively composed and rendered) - the other side was filled with what seemed to be a strange ramble - a sequence sounds repeated over and over by a chorus; clearly, the 'Maheshwara Sutra' was being chanted 108 times. I went over the blurb again and it gave the 'text' of it: 'ai-un-rl-rk-e-o-ai-ouch-....' it went. It made no sense to me; listening to it was no musical experience, nor much of a devotional one either.

Now, wikipedia has revealed to me that the mysterious chant was Panini's celebrated phonological 'sutra' -tradition holds it was revealed to the Master by Maheshwara (Shiva) - a legend grand enough to be associated with a piece of cerebral work done in pre-Christian India and which inspires awe even among modern exponents of linguistics. The word 'sutra' has no real devotional connotation; a probable translation would be 'formula'; the Shiva legend is only supreme praise for supreme work.

So, what Pandit Jasraj has done is something akin to repeating a Mathematical formula or equation as a devotional chant, an act that does not strike me as particularly meaningful. Is chanting "E equals mc2" of any help with special relativity (hope nobody would object to putting Panini and Einstein on the same pedestal - or thereabouts)? Perhaps one could take Jasraj's version of the sutra (with the chorus and the accompanying pakhawaj sounding like thunder rolling in the distance - the 'da' connection?) as music (or muzak?) for meditation.

Saturday, May 21, 2005

Sudoku - Yet Another Puzzle!

Anand has a nice introduction to this newly famous class of puzzles at his blog 'Locana'. He has also kept a sample puzzle and its solution as well.

A few observations:
I took over an hour to solve the instance of Sudoku featured at Locana. Finding the basic pattern was simple enough but implementing it fully was somewhat laborious (this indicates a possible relevance for programming; it could also mean I missed something!). Anand says there are other harder instances of this puzzle which could take more time.

With the limited experience of having seen only one instance of this puzzle, one wonders what is the minimum number of small squares in the grid that ought to be filled so that the rest of the layout is uniquely determined (in the example Anand gives 30 squares are filled initially) - the distribution(s) of these squares to be filled and the frequencies of the numbers from the set (1-9) used (the starting arrangement need not have all the numbers in equal numbers; how to quantify their relative frequencies?) could be important as well. Indeed, trying to create instances of Sudoku, generalizing to larger grids etc.. could perhaps present worthwhile challenges.

I have yet to figure out how many valid final configurations there oculd be - those configs which have nos. 1-9 in every row, column and 3X3 square. Then come the questions of whether for every such configuration, the minimum number of numbers to be provided initially is the same, what symmetries could a valid initial configuration have etc..

In short, Sudoku appears to raise plenty of questions, and some of these might have interesting answers.

Note Added On 23rd May 05:
Here is more info on Sudoku from wikipedia. It says some of the questions posed above are still open. Links to related (and interesting) topics such as 'Latin Squares' are also available there.

Friday, May 20, 2005

By Goad, It Is Note Fair!

This is 'the plaint of a 'Mallu''

English appears to have a range of long ('deergha') vowel prononciations from 'ah' (as in 'card') to 'oh' (as in 'court'). The obvious intermediate vowel sound is 'aw' as in 'broad'. There seem to be further subtleties at the 'oh' end of the above 'spectrum' with 'code', 'pour, and 'toad' all *probably* having slightly different vowel sounds in 'Queen's (?)' English (we wont worry about these rather extreme subtleties here).

All Indian languages, on the other hand, basically have only the two extreme sounds from this range - the 'card' and 'court' ones. Anything in the middle and finer distinctions of the code-court variety are not part of their phonetics (the 'oo' sound of say 'boot' is there in Indian languages but here we look at only about the above-mentioned spectrum of vowel sounds and 'boot' lies beyond that).

The distinction between the 'aw' and 'oh' in English pronunciation is very subtly inconsistent - 'road' and 'broad' have very different vowel sounds and so have 'toll' and 'doll'. And there is no obvious rule or pattern. This should really have created massive confusion to most Indians who learn the intricacies of English pronunciation as an add-on to the sound structure of their respective mother tongues - they basically lack the 'aw' sound of 'broad' and even after adding this sound to their 'phonetic repertoire', one has to learn where to employ it - as distinct from the 'road' sound. But, almost incredibly, the huge majority of Indian learners of English are seldom troubled by this and almost invariably get things right!

...Except, of course, those who grew up with Malayalam! In some very typical cases, one can have a 'Mallu' named 'Tom' say his own name as 'Tome' (rhyming with 'dome'), 'Tony' and 'tawny' having identical pronunciations and a quite decent school student getting confused whether 'coat' (articulated, not written) was an object to be put on or to be slept on. It is not that Mallus do not know the 'aw' sound of 'broad' - they do know it exists and do pronounce it, but they employ it arbitrarily in confusion with the 'road' sound.

Indeed, what really puzzles me is how the rest of India gets it right almost always although they do not start off with any phonetic advantage over Malayalis. A typical Mallu can take several years to get over this severe confusion; many never make the cut and some truly blessed souls never even know they are messing up!

Well, one might say Tamil speakers say the open 'ah' for the 'aw' - but they never are CONFUSED. They would say 'saart' for 'sort' (almost like an American would put it, so it is cool!) but they will not pronounce 'port' as 'part' or 'fort' as .... To be more precise, although the hard-core 'Tam' makes only the two extreme sounds, - 'ah' as in 'part' and 'oh' as in 'court' - he knows, with uncanny precision, which words have an 'aw' ('broad') sound and pulls them back to 'ah's; those with 'oh'('court') sounds are pronounced as such - no trace of the 'coat vs cot' confusion.

On the other hand, the hapless Mallu (poor soul, even 'Goad' is indifferent to his plight) would conjure up spurious rhymes and miss the real ones. Unlike the Tam, he uses the 'aw' ('broad') sound in addition to the 'extreme' sounds; and uses it indiscriminately to create havoc - pronouncing 'code' as 'cod' and coke' as, well, one can go on and on... Get a Mallu to 'roam in Rome' and he will get lost, although he might very well enjoy 'Pope music'!. ..!

I conclude with this assertion, it simply ain't fair: why do ONLY Mallus have to suffer so much from this deeply devious feature of English??

Note added on May 30th-05:
1. Here is a link on the so-called 'cot-caught merger'; amazing that in 'proper' English, 'cot' and 'caught' actually have different and distinguishable pronunciations! This also suggests a technical name for the Mallu's confusion: the 'cot-coat merger'.

2. The Malayali is not entirely alone in his confusion. It has been brought to my attention that some North Indians, especially Gujaratis make the 'road-broad' mess.

3. Further, the assertion that no Indian is basically equipped with the 'broad' vowel is not entirely accurate; Modern Hindi-Urdu has a somewhat similar sound in 'koun' (who). This is almost certainly a distortion from the original sanskrit pronunciation which would have been like 'kown' (same as in 'owl').

Update (July 2016): There is a huge ongoing confusion among Keralan netizens as to whether 'trolling' is a usually nasty cyber activity or a sometimes controversial maritime one. The reason, of course, is 'trawling', performed by mechanized fishing craft (it eats into the catch of more traditional fishermen). There are 4 distinct ways to pronounce the 'troll'-'trawl' pair - to make both 'trawl', to make both 'troll', to get both words right and to get both wrong. My informed guess is that a survey among Mallus will yield the first 3 possibilities with roughly equal frequency and the last with slightly less but considerable frequency. This guess would, of course, imply that the clear majority of respondents would pronounce both words just the same(Note: Intriguingly, even 'trolling' has maritime connotations - it literally means to fish with a hook and line)!

Friday, May 13, 2005

More On Prisoners and Switches...

The previous post here was on this puzzle.

One would like to say a bit more on the spokesman based protocol itself, given in the solution available online and its generalization to cases where there are MORE THAN 2 SWITCHES.

One obvious thought is: let there be 5 switches. The prisoners divide themselves into two equal groups; each group elects a spokesman. Group A works with switches 1 and 2. Group B with switches 3 and 4. Each group runs the same protcol as given in the online solution. Switch 5 is used by spokesman of either group (once) to indicate that his group has finished. And once he has toggled switch 5, the spokesmen wait for switch 5 to be toggled again - on his subsequent visits, he toggles some other switch not 5. Thus, the spokesman of the group which finishes first can know that the other group has also finished and can give the answer - we have applied a straightforward recursion to the already known 'base' solution.

Let us revisit the solution to the original puzzle (2 switches A and B): there, B is a dummy or 'noise' switch used only when prisoners have to necessarily toggle a switch - the information transfer from each prisoner is thru switch A (we could call this the 'info' switch). This implies two groups of prisoners can share their 'noise switch'. Thus we readily see that the above simple recursion works just as well with 4 rather than 5 switches - group A uses switches 1 and 2, group B uses 1 and 3 (1 being the shared noise switch); switch 4 can be used by the spokesmen to indicate the respective groups are done.

A question suggests itself: Is this the best that can be done with 4 switches (switch 4 seems seriously underutilized above!)? And if only 3 switches are there can one improve upon the 'base' 2-switch method?

What about improvements to the protocol if more switches, say M are available? Again an obvious thought is: Keep 1 switch aside, keep one more switch as a noise switch and divide the prisoners into as many groups as there are switches remaining - ie M-2 groups; each group has a spokesman. There could also be a 'grand spokesman' elected among these spokesmen. One could have an info switch for each group of prisoners, all groups share the same noise switch (kept aside above). Further, we could play the base version of the game only among spokesmen of the groups at a higher level -using the 1 switch kept aside at the beginning as the info switch and the common noise switch remains the noise switch at this level as well.The 'grand spokesman' answers finally.

Question: How to improve upon this?

One more thought: as each spokesman joins the higher level game, he also can bring with him the 'info' switch of his former group (his ex-teammates will only play with the common noise switch for the rest of the game; their job is done; moreover, they dont need to be informed that their group has decided; this is crucial) which can possibly be used to speed up the decision making among spokesmen (how this could be done is not clear; switches being added at 'runtime'could be difficult). Probably a key difficulty here is that spokesmen graduate to the higher level NOT simultaneously. Still, in this protocol, once a spokesmen has started playing the higher level game, the info switch of his original group remains idle for the rest of the show - that is probably wasteful :)

Monday, May 09, 2005

Of Prisoners And Switches - A Puzzle

is a nice puzzle featured on the 'Ponder This' column at IBM Research, long back. It is about a group of prisoners, isolated from one another (they can have one preliminary discussion and they will be in cells thereafter), and are randomly and repeatedly made to toggle one of two switches, alone. They have to devise a protocol to work the switches and figure out whether all of them have actually been to the room with the switches at least once.

The solution to the puzzle provided at the same place involves the prisoners electing a spokesman and this spokesman following a different protocol from the others - and only he can actually decide the answer. What follows should hopefully make some sense (and provide some extra fun) if you have gone thru the abovementioned pages.

I have been wondering whether any protocol that solves the problem has to be necessarily a spokesman-based protocol. The present guess is that a protocol where no prisoner among N prisoners is special and everyone of them can potentially answer the question CANNOT be found if there are only two switches as in the original problem.

A simple case: There are two prisoners, two switches. Neither prisoner is special. Both follow similar protocols. Can this work?
The answer apparently is 'yes'. Both prisoners and switches could be numbered 1 and 2. Each prisoner toggles 'the other' switch on the first visit. Then, on every subsequent visit, each toggles only 'his' switch - both keep note the position of both switches throughout. Then, one of them (the prisoner who actually made the FIRST visit) is bound to see 'his' switch toggled by the other prisoner from the state he saw it last. Then he can announce that both guys have been to the switch room.

Assuming this is correct, one could try more cases ( the case of 3 prisoners +3 switches, it appears can be solved by a straightforward extension of the above method; beyond that it is less clear...)and explore underlying patterns and deeper facts. One could also worry about how to improve the spokesman protocol given at IBM if there are more than 2 switches available for the N prisoners to play with.

Wednesday, May 04, 2005

Cutting a Polygonal Cake

This post is NOT on the 'Cake Cutting Algorithms', which have had a history of development starting with Steinhaus et al in the '40s - and still continuing...

We (Ramana Rao and self) have spent some time looking at the following different optimization problem: Given a polygon (which could be arbitrarily complex although for the time being, we assume it has no holes). We are interested in cutting it into two equal area sets of polygonal pieces using the least number of straight line cuts (a cut is that portion of a line interescting the polygon between an entry into the polygon and the next exit. so there could be multiple cuts along the same line, they all count as different cuts).

It may be remarked upfront that if the polygon is sufficiently complex it cannot be cut into two equal area pieces with a single straight cut. For example, let the polygon have 3 wavy and winding 'arms' all of equal area, meeting at a small central 'node' (we could call this polygon a 'triopus'). This cannot be cut into two equal area pieces by ANY line. It can be cut with two lines into one set of two pieces and another set with a single piece, both having same area.

Indeed, applying this triopus idea recursively, we could think of polygons which require arbitraily large numbers of straight line cuts to break into a a set of pieces and leaving a single piece so that the single piece exactly equals in area the set of pieces ie both are half of the total area of the original polygon.

As far as I know, not much work has been done on such equipartition of polygons using the least number of straight line cuts. There has been work on reducing the total LENGTH of the straight line cuts used (and on using arcs instead of straight lines to cut the polygon and minimizing the sum of arc lengths) but not on optimizing their NUMBER.

It appears that one needs some data structure to represent how the polygon's area is distributed. This data structure should support some equipartition algorithm....

A (hopefully simpler) subproblem: Given a polygon, decide if it can be cut with SOME single line into two pieces of the same area. Solving this could provide some insight into the main problem above.

Even this subproblem in general does not seem to be a discrete problem - the area of the polygon is continuously distributed;and it is probably not possible for this distribution to be captured by a discrete data structure like a 'standard' tree or graph. Moreover thru any point in the interior of the polygon there is an infinity of cuts that could possibly be made.