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.

the Space Odyssey

These are unique kind of problems trying to find the number of ways of travelling from one point to another in n-dimension space. Here n could be anything, from 1 dimension to 2 dimension or 3 dimension et al. I initially encountered these problems during my GATE exam preparation and till the exam I couldn’t find a way to deal with them. In short, I went to the exam without solving such problems, even though being aware of the fact that these questions had repeated themselves in disguise. Fortunately enough, paper setters didn’t mind to test me on these! But then I was destined to understand and solve them only after the exam. And little did I know that even though these problems sounded weird related to geometry or astronomy, but they were the easiest to crack once I had clear understanding of permutations and combinations. Thanks to Kenneth Rosen!

A typical problem sounds like –

“Given a 2 dimensional space how many paths exist from point (0,0) to point (x,y) with the condition that we are allowed to move either up or right and no other direction?”

Here usually (x,y) is specified, for example  (3,2) or (5,6) and both of them are completely random, no correlation whatsoever.

Indeed it sounds scary enough to give goose bumps. But let’s start with simple 1 dimension space. The number of paths from point 0 to x is 1. C’mon that’s lame. No matter what is x, the number of paths remain still 1. And the condition is irrelevant.

Ok, having cracked 1 dimension space, let’s move on to 2 dimensions. Here the condition matters. In fact this condition suggests us a cue to reach the solution. We are restricted in our movement, only two choices are available at any point. So let’s model the path from point (0,0) to point (x,y) as combinations of rights and/or ups. Let’s further encode right as 0 and up as 1. Thus any path between the above points is string containing 0s and 1s and its length exactly is x+y. Since any path to point (x,y) should exactly contain x rights and y ups, we find that our string denoting the path contains preciously x 0s and y 1s.

So we have morphed the original problem to familiar field of permutation and combinations. What only remains is finding the number of strings of length x+y which had preciously x 0s and y 1s. And that would reflect the required number of paths and the answer. Now, a simple solution for the new transformed problem is from permutation perspective which has few objects of each type. A typical problem of such type would be finding the number of distinct words possible from the word – “SUCCESS”.  And it’s quite simple (I’m refraining from technicalities here)-

= 7!/(2!2!)

So our problem reduces to finding the number of distinct strings that are possible from the string that contains x 0s and y 1s. So that’s just a cakewalk now –

= (x+y)!/(x!y!)

And this preciously is the solution for the above 2 dimension problem. For example, the number paths between the points (0,0) and (3,2) is

=(3+2)!/(3!2!)

=5!/(3!2!)  = 10

And you could verify this by enumerating all the paths. Another perspective to solve such problem is to think as number of ways of arranging x 0s (or y 1s) in a string of length x+y i.e.

= (x+y)Cx = (x+y)Cy

Using the same example, the solution now would be 

=5C3 = 5C2 = 10 

Wow! I liked the thing when permutations and combinations converge to give the same solution. Both in fact attack the same problem from their perspective to drive the solution out of the box!

Ok, take a long breath as we move on to 3 dimensions. But that should also be another cakewalk. Isn’t it? Any point (x,y,z) would exactly contain x rights, y ups and z inwards(if restriction is on going outwards). So modeling on similar lines we get a string of length x+y+z containing x 0s, y 1s and z 2s. So the solution on the similar lines is

=(x+y+z)!/(x!y!z!)

Going through the combinations way, we find the same answer too. However it’s bit tricky now. First we find the number of ways to arrange x 0s in the string of length x+y+z and then number of ways to arrange y 1s in the remaining string of length y+z i.e.

= (x+y+z)Cx * (y+z)Cy

Verifying that both the formulae have same destination is simple matter of substituting values of x,y and z.

And similarly, an n dimensions problem could be attacked and morphed into a simple permutation or combination problem of grade 10. But the initial problem could be tweaked to raise the difficulty level. For example, instead of having point(0,0) as the origin, any arbitrary point could be selected (does that really matter?) or putting a roadblock between two points on the way from source to destination like putting a constraint that there is only one path between point(3,2) to point (4,3) which lie on the midway between the source or destination. And similarly, restrictions and tweaks could go on to design more fascinating and intriguing problems!

The Dream Exam

Ever thought of an exam that has passing probability of 0.9 or greater? It indeed sounds cool to attend one!  But not so cool, when it boils down to design one. There was a similar problem of designing a question paper in my MSc(Engg.) SERC test at IISc.

 

“The probability of answering a question correctly is ½. A candidate is required to attempt 2 questions correctly in order to pass the exam. What are the minimum number of questions required in the exam so that the probability of passing is at least 0.9?”

Though the question looks very straight forward but when I started solving it using tree diagram, I started facing lot of issues and it took lot of time. Indeed, it is not a straight forward question but reverse version of a usually asked question. Suppose, had the question asked – “What is the probability of passing when there are, say 5 questions?” This one is pretty straight forward and lame. Since the total search space or the possible number of response combinations for a 5 question exam is 2⁵=32. Now out of these we are interested in responses that have at least 2 correct answers. So total number of such responses would be –

 = Number of responses with 2 correct answers +

   Number of responses with 3 correct answers +

   Number of responses with 4 correct answers +

   Number of responses with 5 correct answers

= 5C2 + 5C3 + 5C4 + 5C5

= 10 + 10 + 5 +1

= 26

Thus Probability of passing is 26/32 = 0.81 (approx.)

Aah, so close to our required probability of 0.9! Now instead of calculating so many combinations, a direct option would be –

Probability of passing = Probability of at least 2 correct answers

         = 1 – Probability of at most 1 correct answer

         = 1 – (5C0 + 5C1)/32

                                 = 1 – (1+ 5)/32

                                 = 26/32 = 0.81

Here 5C0 indicates number of responses with 0 correct answers or all 5 wrong answers and there is only one possibility – all wrong answers. And 5C1 indicates the other part, where only one answer is correct and hence 5 possible responses i.e. any of the 5 questions is answered correctly.

But our task is exactly the reverse. We need to find out the minimum number of questions required such that the passing probability is at least 0.9. Though I couldn’t find the straight forward solution but I could attack it from reverse direction and keep on calculating the probabilities for each number until we find the required probability. Hence probability of passing when the number of questions, N = 6,

                                    = 1 – (6C0 + 6C1)/2⁶ 

                                    =57/64 = .89

Similarly for N = 7,

                                   = 1 – (7C0 + 7C1)/2⁷

                                   = 120/128 = 0.93

That’s it. We have the required probability and hence the answer, equal to 7. The exam needs to have at least 7 questions so that the passing probability is at least 0.9. Wow, how good it would be if everyone designed such exam!

Though, this is not the way it should be solved. But I found only this! So let me delve more into it until I find one, if any, or I faint!

the sorted Array and the scanner problem

I came across this puzzle during my Msc(Engg) interview in IISc Bangalore. The puzzle was simple and stated as -

"You are given a sorted array of length n and a pointer that points to the first element in the array. This is a special pointer that can be reversed in direction only once. That means if it was moving to right and then it decides to move towards left then it keeps on moving to left. It cannot change its direction again."

The problem is to come up with an efficient algorithm to search a number in the array.

While it took me fews seconds to put all the conditions and situations together, my first response was to do a linear search. And that was accepted quite generously. Of course, the next question as anticipated was "Can you do better?"

This algorithm had a running time of n. So I decided to divide the array into two parts. I suggested directly compare the middle element with the search element and depending upon the outcome, we move into either of the half. This reduced the running time to n/2. That too was accepted cordially and followed by the same question!

Instead of targeting the middle element, we could target, say n/3^th element. So running time is down to n/3 from my first response of n. Next question was a bouncer.

"So what's the appropriate step size that gives the best efficiency?"

He meant, we could go endlessly by choosing n/5 ^th, n/10 ^th, n/20 ^th and so on. Which one of them would be the best?

Suddenly I recalled a similar problem that I had read long back on 20bits.com, which tries to find similar solution. But I couldn’t recollect the way he had solved, probably because four IIsc professors were continuously gazing me. I tried recollecting and gave up. But I gave them a brief idea how could we find the solution. They looked satisfied with my broken answer and asked me to ponder upon it after the interview.

Soon, I was heading back home in a BMTC bus. My mind was completely occupied with calculations and trying to find the solution for that problem. But I did it! I found it in BMTC!!

It was not that difficult as it sounded in the interview room. We wanted to find the step size that would lead best efficiency. So If I choose n/3 step size, then once finding the appropriate partition I had to do a linear search for remaining 2 elements in the partition. The explanation being, since each partition had 3 elements and one of them gets compared at each step size, I had to check the remaining 2 using linear search. What if I take step size n/10? I needed to check another 9 elements using linear search in the partition.

So, mathematically put, the total number of comparisons required –

n/s + (s-1)

where

n -> array length and s -> step size.

This equation preciously defines the number of comparisons required for a generic step size s. The first part of the equation: n/s, indicates the number of partitions that are formed due to step size s and these were the number of comparisons required on the step size in worst case, as the search element could be in the last partition. The other part: (s-1), indicates the number of linear comparisons required once we found our partition. Since each partition had s elements and one of them was already compared during partition searching, we required only s-1 more comparisons.

Now we have a mathematical representation of the problem we are dealing with and we just needed to find the step size that resulted into minimum comparisons. Hence we simply needed to find the value of s where the above equation had a minima. And that’s typical differentiation stuff. We differentiate the above equation wrt s and equate it to zero to get the required value of s.

Thus on differentiating and equating the above equation to zero,

-n/s² +1 =0

=> n = s²

Or s = √n

 i.e. s = sqrt(n)

And that’s it!

continued...