Rick Riordan at the National Book Festival

I was at the National Book Festival yesterday in Washington DC where several authors including Rick Riordan, John Grisham, Jodi Picoult and the like did book signings and talked to their fans. The event by itself was sort of poorly managed because the management probably did not expect a crowd on such a big scale (the Smithsonian metro station was closed in the afternoon due to too much crowd!).

But all that apart, people who went with the intention of meeting their favourite authors had a successful day, and that was perhaps the only worthy reason to go to the festival because the book festival did not have any book stalls (other than a jam packed Borders tent selling only very specific books).

Anyway, so I wen't to catch a glimpse of  Rick Riordan since I am an insane Percy Jackson fan.I got to the pavilion atleast 15 minutes in advance while the previous author was still speaking. After some pushing and jostling I finally edged into the tent and escaped the rain outside. There was hardly any place to stand but I positioned myself so that I could operate my camera.

His talk was quite funny in general and he gave his eager fans a glimpse of what is in store for them in the upcoming months:

1. There will a second Camp Half Blood series of books (yes you heard it right!) coming up soon. I forget if he mentioned when it will be out, but he mentioned that there will be more of Percy and Annabeth to come although Percy will not be the main character in the new series and there will be a new generation of demigods. The new series will probably be based on the next big prophecy that we encountered in "the last olympian".

2. May next year is going to be about Riordan's next novel that is based on Egyptian mythology. Now that is something that sounds really exciting. Riordan even read the first few lines from this upcoming book that he says is currently with his editor now!

3. Finally he talked about the Lightning Thief movie that is set to release in February next year. He mentioned that the role of Chiron will be played by Pierce Brosnan and that of Medusa will be played by Uma Thurman. Now that is some interesting cast.

Since I am travelling currently, I will upload pictures soon.

Using multiple applications with ASPNETDB

As a web developer, I have used ASPNETDB several times to manage the membership and role information for my applications. It has been a while since I have done software development in ASP.NET. So when I try things now, I realize there are several small things that I knew at my fingertips back then, come with a little more effort right now. I hooked up a new application to use the ASPNETDB, and tried to create a new login. I got the error that the username already exists.

This was surprising, because it was a new application. I realized that the application was actually pointing to the same instance of ASPNETDB on my DB server. I knew that there was some way of isolating multiple applications in the same membership database. After a bit of research I recalled out to do it:

In the web.config file, look for the following section:

<membership>
<providers>
<clear/>
<add name="AspNetSqlMembershipProvider"
type="System.Web.Security.SqlMembershipProvider, System.Web, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a"
connectionStringName="ApplicationServices"
enablePasswordRetrieval="false"
enablePasswordReset="true"
requiresQuestionAndAnswer="false"
requiresUniqueEmail="false"
passwordFormat="Hashed"
maxInvalidPasswordAttempts="5"
minRequiredPasswordLength="6"
minRequiredNonalphanumericCharacters="0"
passwordAttemptWindow="10"
passwordStrengthRegularExpression=""
applicationName="/"
/>
</providers>
</membership>

Change the value of the applicationName attribute inside the providers element to then name of your application, and you are good to go!

Free Internet?

This is a short post from the Greater Rochester International Airport as I wait for my flight. No other service at an airport makes me happier than free internet. The first time I saw this was when my flight to Memphis was delayed by a couple of hours and I was stuck waiting at Charlotte Douglas Int'l airport. I saw an unusually high number of people using their laptops and somehow got the feeling that there might be internet connectivity. I booted up my machine and to my pleasant surprise, I was right. I was able to establish a secure connection to my school network and get some work done while I waited. For internet savvy people like us, there isn't really much you can do if you are stuck waiting at an airport, and a free connection just saves your day.

But I was wondering what is it that allows an airport to host a free wifi connection. Large and prestigious airports like the O'Hare Int'l airport at Chicago do not have a free wifi connection. What is it that prevents them from doing so? What is the business model followed at the lesser known airports that lets them provide this service to travellers?

Shuffle shuffle

Several weeks ago, I found myself thinking, how I could shuffle a list/array given to me in a random order. This is a typically commonplace thing to do in several applications: online card games, your favourite music player etc.

The interesting thing about this problem is how some naive approaches, even though easy to code and efficient enough, do not achieve the desired randomness.

Lets define the problem: You have an input array which has elements in positions 1 through n. The objective is to produce a random permutation of the array. By a random permutation, we mean to say that each permutation of the array is equally likely. So a truly randomized algorithm will generate each permutation with a probability of 1/n!

The first approach that comes to mind is the naive approach of generating a random number between 1 and n for each element in the array and placing the element at the position indicated by the random number. This could be accomplished by using another auxillary array and placing elements into the new positions generated. The pseudocode could look something like the following:

NaiveShuffle(A[1...n], B[1....n])            //randomly permutes the elements in array A
for i from 1 to n
random <- RandomNumber(1,n)
B[random] <- A[i]
for i from 1 to n
A[i] <- B[i]



The above approach is very crude in the sense it uses an auxillary array and also parses through the array twice instead of just once. Still, the worst case running time of the above algorithm is O(n).

Random(1, n) generates a random number 1 and n (both inclusive). We assume that the random number generator generates truly random numbers in the interval specified. Also, we assume some kind of collision resolution mechanism. We are assuming that this method returns a random number in O(1) time.

All that said, a O(n) algorithm is not bad at all for this purpose. There is only one problem, this algorithm is WRONG! (hah...fat chance, didn't we name it a naive algorithm?). Why is that? This is because in every iteration, we generate n possible choices. Since there are n such iterations, the total number of permutations generated is n.n.n.n.......n times = n^n

The  total number of permutations possible while shuffling an array is n!. Since n^n is not exactly divisible by n!, there have to be some permutations which appear more frequently than the others (basic pigeonhole principle). Thus this naive algorithm does not generate truly random permutations.

Lets try something else. We generate a random priority between 1 and n^3 the Random(1, n^3)  routine, and assign a it to each element in the array. Then sort the array based on these weights.

e.g. if the original array is A<1,2,3,4> and we generate priorities randomly as P<34,56,8,77>, then when we sort array A based on the increasing order of the priorities assigned using array P, then we get the shuffled array as <3, 1, 2, 4>.

We used the interval [1, n^3] to generate priorities so as to reduce collisions. I will not delve into the correctness of this algorithm. The running time of this shuffling by sorting algorithm depends on which sorting algorithm we use. Typically it is Big-Theta(n lg n).

Another approach to solve this problem, is to shuffle by swapping:
Shuffle[1...n]
for i from 2 to n
temp = Generate(x from 1 to i)
swap(i,temp)

Notice that the interval for generating random numbers keeps decreasing. For the first iteration, there are n choices. For the 2nd iteration, there are (n-1) choices and so on.

Hence the total number of choices generated by this algorithm is: n(n-1)(n-2).....3.2.1 = n!

which is exactly equal to the total number of possible permutations. Moreover, since we iterate over the array only once, this algorithm runs in O(n) time.

The White Tiger: Aravind Adiga

This novel, published in the year 2008 won the Man Booker Prize in the same year. I bought the book out of instinct, although I haven't had a very pleasant experience with a couple of other books that have won the same prize. Many people said that the books that won this award were difficult to read and not well accessible. One of my friends gave me a very bad review of the book, but I had no choice but to read it since I had already bought it. I approached the book without any pre-concieved  expectations and I was pleasantly surprised. While I did not bother asking my friend why she did not like the book, there are several reasons why I would recommend the book to any reader.
First of all, the book is an effortless read, and the story flows at a good pace. The story is narrated in first person by Balram Halwai, who is the protagonist. It is his account of his rise from lowly origins in a village in rural India amidst crushing poverty where even the basic amenities of life are hard to come by; to his current position as a successful entrepreneur in a big city. But the story is not one of inspiration as one would imagine from such an account. Instead it is a story full of intrigue, corruption and crime, but narrated with an innocent and brutally honest tone that makes you chuckle throughout. The story takes a swipe at the corrupt political system of the country and how the people are forced to play along with it if they want to survive. What moves you while reading this story is how the honest and hardworking village boy is transformed into a shrewd, scheming man who does not hesitate to take the law into his own hands.
Adiga has done a masterful job in this darkly comic debut novel of his with a sharp observation and sardonic voice.

Unaccustomed Earth: Jhumpa Lahiri

This is Jhumpa Lahiri's third piece of work (after Interpreter of Maladies and The Namesake). Sticking to her theme, this is also a set of short stories, based on the lives of expatriate Bengali parents and their american-raised children. I used to really want happy endings from books and stories I read. Jhumpa Lahiri is not someone who would give me that. Her stories are colorful, full of real characters that you would come to love; her writing is superlative and flows with an effortless pace; but the stories end abruptly at a crucial emotional juncture when the characters are at some kind of an emotional high point. I am always left wanting for more, but I end up accepting the stories for what they are.
One thing I noticed in her first two works is her brilliant descriptions of food and cooking, so much so that I used to be amazed at her culinary knowledge. I was looking forward to the same, but found that missing in Unaccustomed Earth.
There are two parts in the book: the first one has 4 stories, and the 2nd part has 3 stories. I did not realize till the middle of the last story that the 3 stories in the 2nd part are actually related: based on the same two protagonists. Each story in the trilogy are spaced apart by a number of years .You could call me dim for not figuring this out earlier, but these stories are just like the previous ones, and each one could be read without any bearing on the previous ones, and none of them give any direct indication of a connection, except for the names of the characters (which could have been anything in any of the stories without affecting the plot). The first two parts are narrated by the two individual characters, based around their separate lives. The third story is narrated by the author, linking the two characters together finally. Being a fan of different narrative styles, I loved this.
Finally, Jhumpa proves that she can write not only about life in the US, but also Europe, where a considerable portion of the final story is based.
Brilliant piece of writing. Highly recommended reading.

one flew east, one flew west….

I recently finished reading One Flew Over the Cukoo's Nest: by Ken Kesey. This novel has been included in TIME Magazine's 100 Best English-language Novels from 1923 to 2005.

The novel is based in the mental ward in a psychiatric hospital in Oregon. It is an allegory on the psychopathic obsession of that time (the 1960s). The story is narrated by a gigantic, half-Indian "Chief Bromden", a patient of the ward who suffers from hallucinations and delusions.The ward is controlled by a tyrannical nurse: Nurse Ratched who reigns over all the inhabitants of the ward, including the orderlies, the staff nurses, and even the doctor. He controls everyone with surgical precision, using underhanded tactics to render everyone helpless and submissive.

Things change with the arrival of Randal McMurphy, a Korean veteral who has a history of insubbordination and street brawls. McMurphy quickly realizes that several patients in the ward are sane and simply emasculated because of the nurse and her controlling tactics.

This novel is about the fight between authority and free spirit.

Pillars of the earth

I started reading this book by Ken Follet over 5 months ago. When I just had a couple of dozen pages left to finish the book, I went away to the US and for some reason I did not carry the book with me. Now that I am back in India for a while, I finished the book today. It is a really big book with over a thousand pages. There are several plots in the story, and like most really long stories, you feel that some of those could have been avoided for the sake of a smaller and crisper story.

The plot of the story revolves around the building of a cathedral in medieval England during the period of civil war and how the lives of several people around the cathedral is embroiled in politics and powerplay. The book spans several years and hence the author has been able to sketch the characters in great detail (no surprise there).

Several  reviews on amazon tout this book as a breakthrough in the historical fiction genre, which I think is a bunch of nonsense (no wonder since the book was a part of Oprah's book club). I don't really have good things to say about Oprah's book club and I would probably have not picked up this book had I known earlier, but the book did turn out to be entertaining, with a lot of gratuitous sex and violence thrown in. Sometimes it drags simply because the plot is very twisted and long.

I did learn a bit about medieval architecture, cathedrals, clergymen, nobles and the like. All in all, I recommend this book for a one time read. Entertaining, but long.