GATE is not the only gate ...

Gate results coming out shortly. Every one who gave a valuable attempt will be having their heart in there mouth, few will be nervous and few may faint too.  Year back i too had the same situation. I gave up my job, time and many more things for gate, putting every effort that i can. Am bit emotional as doing masters in a reputed college is the only dream i had and remaining all are just goals. Later the scene is quiet different, I ended up with a reasonable score but it cant take me to the place i want to be.

So i am not having any other alternatives. Many questions,

Cannot join in some random college
Cannot go to a job again giving up my dream.
Cannot waste another year
Cannot be sure if i hit the deck even if i waste another year
Cannot...cannot ...cannot...


So these are the chaos many of the students face in india. Let me say one thing guys getting a seat in IIT or NIT or some reputed college is really tough (some say its easy) . To prove this let me take some statistics

Gate 2013 CS applicants : 2,25.000 (around)
To get a call/seat in IIT/NIT  you must be having a rank below 1500
(i never consider reservation quota!!)

so you must be in the top 0.6% of the applicants. so is it really easy??
(Stanford has 6.6% admit rate to there graduate school, stanford will be in top 3 places world wide and iits not even in top 100)

One must be practical and give an attempt to exam like gate by giving themself some backup or second thought.

So please dont be emotional if you are not there in that top 0.6% or what ever you thought on to.
There are many other options and many other things left to do! Plan properly and be practical. Dont think that this is the end.

Dont worry if you dont get into IITs you have every chance to get into stanford. which is better is left to your imagination :D

And to the IIT supporters, i am not blaming IIT, the problem is with the country and our planning in education. Please dont take it other way. Even i love IIT's

All the best pals !!

Hard disk structure and its addressing scheme

Almost every gate exam will have a question on hard disk addressing scheme which is very easy to understand if we know the physical structure of hard disk. You may have to look into this  few times to get a good understanding, so don't set back if you were confused by looking into this initially. consider the below picture

consider the top view of the hard disk.Hard disk will have multiple number of cylinders and as shown in the picture each cylinder will be placed one after the other in a row from inner circle to the outer circle. each cylinder will have multiple number of platters placed from top to bottom as shown in the right part of the picture. Each platter again will have two surfaces - surface 1 and surface 2 as shown. Each surface is divided into equal number of smaller parts called sectors.

so the division goes like this

cylinders - platters - surfaces/tracks - sectors. Sector is the smallest unit of division.

Addressing will be done in the sector level (Each sector will have an individual address). Each sector will be given an address like <cylinder no.,surface no.,sector no.>        

consider bottom part of the picture which shows one surface divided into 8 sectors - usually this is called as a track. Assuming the numbering of cylinders, surfaces,sectors start from zero, the first sector (present in the first cylinders first surface) will be addressed as  <0,0,0>. As here each track is divided into 8 sectors, each sector address can be seen in the picture marked from <0,0,0> to <0,0,7>

Following this addressing continues to surface2 of the first platter. there the addresses will be from <0,1,0> to <0,1,7> 

Like this all the surfaces/tracks of all the platters(here in the picture we have 3 platters and each platter has 2 surfaces) in the first cylinder will be addressed and then the addressing continues to the immediate outer cylinder that is cylinder 2. This pattern of addressing continues until all the cylinders are completed.      

Graph Theory - short notes

Graph theory is a very interesting as well as important subject. It is easy to understand and score in this subject. Graph theory by Narsingh deo is one good book that a gate aspirant can rely on.

Most of the students get confused while working on GT because of wide number of topics and formulas. The best thing is to split the subject in our own possible way and revisit the topics when ever possible.

Keep things simple while working on GT and do not get confused. It is very important to keep a short notes for this subject that helps in revisiting every now and then as well as before gate exam. Here is a short notes that might help you for a quick reference.

The notes is not well organised but it contains lot of useful content within. Soon we will try to create an organized version of the same.

Please Click here to download the notes

Entrance exams for MTech apart from GATE

IIIT - Hyderabad :

IIIT-H is definitely a very good college to get into. There are good professors, labs,industry relations etc, An exam will be conducted in several cities every year for MTech and research programs at IIITH. Mostly the applications will be open in march and the exam will be held in april. Exam contains aptitude part and technical part. The aptitude part will be relatively tougher than the technical part. Technical paper will be evaluated for only those who are qualified in aptitude paper. Selected students will be called for an interview that will be conducted at IIITH.

Give a try if you are very good in aptitutde, reasoning and mathematics.
Gate scholarships wont be available for IIITH students.

For more details click here.

Bits - pilani, hyderabad and goa :

Every year BITS conducts an online entrance exam for its various masters programs. Even though CS students are eligible for many branches in ME, the most competitive one's are ME in computer science and ME in software systems.

ME in computer science(cs) is available at BITS - Pilani, Hyderabad
ME in software systems(ss) is available at BITS - Pilani, Goa

Exam wont be tough but you should have patience to write the exam and also take care of negative marking.

if applied to both cs and ss, then you need to write three exams continuously.

Test 1 - 60 mins - 60 questions - Maths, physics, English, core programming
Test 2 - 120 mins - 100 questions - CS syllabus (similar to gate)
Test 3 -  60 mins - 50 questions - Special test for software systems

You will be called for interview based on the cutoff decided. For CS they will consider Test1+Test2 marks
and for SS they will consider Test1+Test3 marks.

One should not worry about physics because it wont be that tough. If you are good at intermediate maths and programming you can score high in test1. Even if you leave all the physics questions you can score high if you are good at maths.

Generally applications open in the month of april and exam will be conducted in the month of may/june.
College Fees will be high and BITS will give TA of Rs.8800 per months for selected candidates.

Job sequencing with dead line

Job sequencing with dead line is yet another greedy approach.

Given a set of jobs with their profits and deadlines, the idea is to find the subset of jobs that will produce maximum profit.

Let us take an example to easily understand how it works. Assume each job takes one unit time for execution.

Consider 4 jobs, with profits 100,10,15,27 respectively and deadline 2,1,2,1 respectively.

Job	1	2	3	4
Profit	100	10	15	27
Deadline	2	1	2	1

job 2 or 4 if taken should be completed in unit time 1. so only one can be taken among them. let us take job 4 as it gives more profit. Now in the unit time 2 we have to take job 1 as it gives more profit.Therefore we can take the best sequence as Maximum deadline in the given set is 2. so within 2 units of time we should identify the jobs if taken,will produce the maximum profit. In 2 units of time only 2 jobs can be completed. So which two jobs?

0               1               2        <-- Time

Job 4

Job 1

Consider one more example for the same problem.

Job	1	2	3	4	5
Profit	20	15	10	5	1
Deadline	2	2	1	3	3

So within 3 units of time we can complete 3 jobs. The best sequence will be

0               1               2                3    <-- Time

Job 1

Job 2

Job 4

and the profit will be 45. If more number of jobs are given then it may be a good idea to arrange the jobs in non increasing order of their profits and then identify the sequence.

Fractional Knapsack

Greedy approach is to try all possible combinations in a sequence to find a optimal solution.

You can imagine the knapsack problem like

"a thief having a bag which can hold up to a certain weight W. He found some N items in a house with each having some value V and weight W. So in order to gain maximum value by accumulating items up to the maximum weight he can carry in his bag, he should identify which item should be taken in which quantity"

Here he can go for a greedy approach by trying all possible sequences. we say this as fractional knapsack because any item can be taken in fractional quantity instead of taking as a whole.

The below example shows how such problems can be solved.

consider maximum weight  of the sack is w=15. There are 5 items (n=5). The weights of the 5 items are 12,1,2,1,4 respectively. Their values are 4,2,2,1,10 respectively. The maximum profit that can be obtained is?

Answer : The idea is to calculate the profit/weight value for each item

Item	1	2	3	4	5
Weight	12	1	2	1	4
Value (profit)	4	2	2	1	10
Profit/weight	0.3	2	1	1	2.5

Now sort according to the profit/weight values in descending order.

this gives

Item	5	2	3	4	1
weight	4	1	2	1	12
P/w	2.5	2	1	1	0.3

This tell us we will get maximum profit if we add items to the sack in the above order until we reach the maximum weight

So now we take each item in the above sorted order until the weight is 15(Maximum)

This goes like this

                    item 5 + item 2 + item 3 + item 4 

weight ->      4       +    1     +    2     +    1     = 8

still we can accumulate a weight of 15-8 = 7. so from last item in the list i.e item 1 we cannot add the whole item as it weighs 12. so,we will take a fraction that weighs 7.

item 1 actual weight is 12. we take 0.58 fractional part of item 1 that weights as 7

so the profit we get will be 0.58 * 4 

  

Therefore, the total profit we get is

10+2+2+1+0.58*4 = 17.32

The maximum profit that can be achieved is 17.32.

To sum up, the idea here is to find the profit by wight ratio that helps in finding how much profit we will get for that weight. so we will add a unit quantity of items until we reach maximum weight or nearer to maximum weight, so that the last item we add will be taken in fraction upto which we can accommodate in the bag.

Dont be wondered after seeing a book dedicated for knapsack solutions. You can find it here

Best,Worst and average case comparisions for Sorting algorithms

Below table gives a quick idea of running times, number of comparisions and swaps in various sorting algorithms. For insertion sort rather than swaps they can be considered as moves. Will update the table with linked list, stack and queue operation details.

Algorithm	Best	Worst	Average	Comparisons		Swaps
				Min	Max	Min	Max
Bubble	Ω(n2)	Θ(n2)	Ο(n2)	n(n-)/2	n(n-)/2	0	n(n-)/2
Selection	Ω(n2)	Θ(n2)	Ο(n2)	n(n-)/2	n(n-)/2	0	(n-1)
Insertion	Ω(n)	Θ(n2)	Ο(n2)	n(n-)/2	(n-1)	0	n(n-)/2
Quick	Θ(nlogn)	Θ(nlogn)	Ο(n2)
Merge		Θ(nlogn)