the sorted Array and the scanner problem continued…

Wherein the previous post gave the efficient step size for this problem, but there is still a scope of improvement.  Suppose the array size is 100, with our approach the maximum number of comparisons required would be 10+9 = 19. Could we beat this? Yes, I suppose. What if rather than having a fixed step size of sqrt(n) throughout the algorithm, we opt for dynamic step size. Let’s start with step size 18 and see if we could beat our previous answer of 19. The first comparison will happen at 18^th element and if the search element lies in this group then we need another 17 linear comparisons in worst case to find the element in that group making a total of 18 comparisons. Now if the search element is greater than 18^th element then we have to consider the next group. And here lies the secret.  We decide to shrink the next group size by 1, so that this group has 17 elements rather than 18. The reason for this is, we want the total comparisons to be strictly 18 in worst case and since we have already used up one comparison at 18^th element, we have only 17 remaining. Thus to search the element in the second group we need 16 more comparisons and hence making the total comparisons equal to 16+1+1=18 in worst case. Now what we really have to do is to continue this idea until all 100 elements are exhausted. So the group size continues to reduce by 1 at each stage. Hence the third group would have 16, fourth would have 15, fifth would have 14 and so on and so forth.

This algorithm makes sure that we won’t cross the count of 18 comparisons at any cost. But why is it only the number 18? Why not 17? Yes 17 would just do fine. Even the number 16 does remarkably well. But again, as with the previous post what’s the ideal value to start with, since we cannot go forever reducing the number. The only cue we have at this point is whatever count we start with, it should assure us that it covers all the 100 elements. Suppose we start with step size equal to 10 and at each successive group we reduce the group size by 1 to maintain the count. But all the groups so formed doesn’t cover all the 100 elements since the total elements covered in all groups is

10 + 9 + 8 + . . . . . . + 3 + 2  + 1 = (10*11)/2 = 55

So step size 10 covers only 55 elements. Though it failed to be an ideal answer it did give us an insight to find the one. If we start with step size equal to x then the total number of elements covered by the groups formed by x is

x + (x-1) + (x-2) + . . . . . . + 3 + 2 + 1

=∑ x 

Thus the only condition that makes x the ideal choice is that the above summation should cover all the n elements in the array. Hence we have a new equation –

∑ x ≥ n

(x*(x+1))/2 ≥ n

=>  x² + x ≥ 2n

i.e.  x² + x  - 2n ≥ 0

Since we are looking for least value of x,

x² + x  - 2n = 0

And the solution for this is

x = (-1 ± √ (–1 – 8n))/2

For integer value,

x = ceil ((√ (8n + 1) -1)/2)

Thus for n = 100, x comes to be 14 and I bet you can’t beat this!

That awesome feeling when IISc shortlists you!

That was the sweetest shock of my life. Life had never been so harsh before this shock. After deciding to study further in Computer Science, I had a rigorous schedule for nearly 4 months; mainly because I was from Electronics and Communication background. Though my 5+ year experience had helped me a bit, but its impact was almost negligible to be noticed, given the syllabus for GATE CS. Keeping my passion up and perseverance locked, I never gave up till the day of the exam. Obviously, so much pressure had made me feel nervous. All my effort for days, weeks and months was set up for evaluation in just three hours on that day. All that mattered were those three hours and nothing else. Voiding all the bumpy thoughts, I tried concentrating on the question paper. After the battle of three hours, I was completely shattered and discontented. It was the most hopeless paper I had ever given with such strong preparations. Even in mocks, I had performed way better. Bygones were bygones! I didn’t give a damn and went to Goa.

 

After 2 weeks, my curiosity arose. I started researching on internet only to find out that it was the most difficult paper ever. That pacified me. But the guilt feeling continued, as I had made several silly mistakes, which I shouldn’t have made even in dreams. But those got complemented with the questions that I had solved which were very tricky and tough. Keeping my feeling to myself, I waited for the results and when the site displayed AIR 273, I was on cloud nine. That was only but unbelievable.

Being in top 300 across the country, I was completely sure of getting into at least one IIT. Checking with previous year trend, all IITs except B, M and IISc had open heart to accept me. But destiny had something else to say. Things turned very different. This year scores were very low compared to last year’s. With my score, last year students had got AIR around 400-450. And those students spoiled my dessert. Then a day came where I was waitlisted for IITG and R. And worse more, it was not sure whether I could make it to any of them! And the next best option was NITs, which I despised. And there were few private universities like IIITH which lacked ‘the tag’.  Disappointed with all the happenings around me, I had no option to take a seat in NIT Surathkal otherwise I would also be debarred from NIT counseling. After taking admission, I set my journey back to home. 

Flashback:

All this while, there was an interview whose result was yet to come. And I never had hopes on it. The reason was simple – IITs were reluctant to accept me; why would, their god father, IISc would be in mood. That was the interview for MSc (Engg) aka MS for Computer Science I had given in IISc. And there was a big reason why I attended that interview. Being in top 300, I didn’t opt for any MS course in any IIT. Though I had applied everywhere, I didn’t take the pain to attend them. But this one was lucky. I had my flight to New Delhi for IIT Roorkee from Bangalore on 6^th June and luckily IISc had scheduled my interview on 4^th June. So I thought of giving it a try since what I had to do was just reach Bangalore one day before and that was not too much to ask for. Facing disappointments one after another, I went to IISc without any thorough preparation. I just revised the 10-page concise notes that I had prepared for GATE. I knew I had lost half war before entering IISc itself. Another disappointment from SERC pushed me down to depression zone. I couldn’t even clear SERC written test that was scheduled on the same day but in morning session. To keep me fresh for CSA interview that was in the afternoon session, I started solving few questions from SERC test which I couldn’t solve.

After having a Dosa for lunch I went to the CSA department for the test. This was the time I was at my lowest since I started preparing for GATE. It was all but GATE success I had with me to flaunt and nothing else. And destiny had screwed up that also. Hopelessly I sat for the written. And for a change it was a good attempt. I could solve as much problems I could and without any silly mistakes. It all made sure that I was shortlisted for interview. With feeling of nothing-to-lose anymore, I faced the interview. The affair lasted for around 40 minutes before they allowed me to leave. By that time, I was sure that it wasn’t a smooth affair. I knew I had enough talent to answer them for all their questions, but the feeling of nervousness kept popping off sporadically. Trying to justify my talent, I asked them for one more chance to a question to which I had responded haphazardly. But they didn’t allow, I guess they had predefined time for each student. But the reply they gave was inspiring and motivating. It was indeed my silver lining. They said that they were already happy with my performance and I had done very well. Gosh! I was again on cloud nine with silver lining. I left the hall hurriedly and so did I leave IISc. Finally, after a fortnight SERC published their results. That indicated CSA was also on the way. But having no worthy offer in my hand, I had no option but to accept NIT Surathkal VLSI offer. CSA site only mentioned, they would announce the results soon. But that soon never came soon. I took the admission and set my journey back to home.

Back to present:

During the journey I kept refreshing CSA webpage repeatedly on my cellphone to find out if they had realized that their soon had overshot the deadline allotted to the term ‘soon’. But all in vain, they preferred their own definition of ‘soon’. Disappointedly, I switched off my cellphone and went into a deep sleep. Finally when I opened my eyes, I was still more than an hour away from my hometown.  My heart requested my brain to check CSA website but my brain turned it down rudely.  With request turned down, I had nothing but to gaze the serenity outside the bus. After a long journey with open eyes and nothing to do, I reached my hometown. I caught a local bus to my home. Finally, during that time I got permission from my brain to check the site. Actually, the curiosity had turned into formality. With no hopes, I opened the CSA page and was shocked; they had declared the shortlisted candidate names. Desperately, I clicked the link as if it opened the door of some mummy’s cave that had treasures. Indeed they had declared the results. They first mentioned PhD students and I failed to find my name there. I had applied for both PhD and MS. With shattered dreams, I scrolled down to the list of MS students. As soon as it showed the caption MSc (Engg) students, my browser crashed. Wow, what else I could expect at such a low point in life. Few things, which were close to my heart, also betrayed me at such stage. Not succumbing to pressure, I gathered all courage in the world to open the browser again. It took time to load the CSA web page and all that seemed like years. And then again it took years to open the shortlisted site. Finally I was on the same page which I was years ago. Thanks to technology; time travel to past was possible now. 

With all the gathered courage, I scrolled down to the MSc (Engg) list and there, stood my name written in golden words. It was as if destiny had written it. It did indeed open the doors of my destiny. My eyes refused to move away and brain did hundreds of parallel calculations to ensure that it was but my name. I was still for few seconds or perhaps for minutes which seemed like seconds. That was the moment of my life. It’s difficult if I could face any such moment in future because it was rarest of the rare. Immediately I opened my laptop and rechecked on CSA site. My name was still sparkling there. That feeling took time to sink in. I took a print screen of that page and preserved it for coming years. Yes! it was a life time achievement. Even in my farthest dreams I had not dreamt of getting into IISc. All the way, I always thought of IITs and never thought beyond them. To me, IISc was always special and meant for few specially gifted students. And luckily, I was one of them; I was an IIScian now. As they say, destiny gives you what you deserve, not what you want. True it is.