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)

Selection sort

Selection sort is one of the simple sorting techniques. The basic idea behind this technique is, in each iteration the smallest element in the list is picked up and placed in its exact position. This works as follows,

For a list of n items, we have to iterate through the list for n times.

In first iteration consider the n items, scan the list and find the smallest item. Place this item in the first position. (This will be its exact position)

Now in the second iteration, scan the list except the first item  and find the smallest

Item in the list. Place this item in the second position of the list. (This will be its exact position)

Similarly continue for n iterations.

Given below is an example c code that sorts the input list of 5 items in ascending order using selection sort technique.

#include<stdio.h>

void main()

{

int i,a[5],j,small,loc,k;

clrscr();

printf("\nEnter 5 numbers to sort ::\n");

for(i=0;i<5;i++)

scanf("%d",&a[i]);

printf("\nElements before sort : ");

for(i=0;i<5;i++)

printf("%d\t",a[i]);

for(i=0;i<4;i++)

{

small=a[i];

loc=i;

                for(j=i+1;j<5;j++)

                {

                                if(a[j]<small)

                                {

                                small=a[j];

                                loc=j;

                                }

                }

a[loc]=a[i];

a[i]=small;

}

printf("\n\nElements after sort : ");

for(i=0;i<5;i++)

printf("\t%d",a[i]);

getch();

}

Selection sort reduces the total number of swaps when compared to bubble sort. The  worst case running time will be O(n2).

• Minimum number of swaps 0 ( if the list is already sorted)
• Maximum swaps n-1
• Minimum comparisions n(n-1)/2
• Maximum comparisions n(n-1)/2

For comparison of various sorting algorithms click here

Bubble sort

Bubble sort is one of the simplest sorting techniques. It works as follows,

Assuming a list with n elements.
Compare the FIRST element with the SECOND element. If  the first element is greater than the second element then swap them.

Now, Compare the SECOND element with the THIRD element.If the second element is greater than the third element then swap them.

Continue the same procedure till the last element in the list. By doing in this way at  the end of one iteration through the list, the biggest element will be moved to the last position.

Now in the second iteration repeat the same process with first n-1 elements. This ensure the second biggest element in the (n-1)th position.
later in the third iteration repeat the same process with first n-2 elements. This ensures the third biggest element in the (n-2)th position.

like this after n iterations the list gets sorted.

One can imagine this like, in each iteration the biggest element gets bubbled up the list to occupy its correct position in the list.

Example:

Consider the list

3 2 5 1 4

Iteration 1 :

compare 3 with 2, as 3>2 swap them. result 2 3 5 1 4
compare 3 with 5, as 3<5 do not swap
compare 5 with 1, as 5>1 swap them. result 2 3 1 5 4
compare 5 with 4, as 5>4 swap them. result 2 3 1 4 5

End of iteration 1. Now observe that the biggest element is placed in the n th position.
Now for second iteration consider only n-1 elements. no need to worry about the n th postion as it is already placed in its exact position.

Iteration 2 :

2 3 1 4 5


compare 2 with 3, as 2<3 do not swap
compare 3 with 1, as 3>1 swap them. result 2 1 3 4 5
compare 3 with 4, as 3<4 do not swap
End of Iteration 2.
Now consider n-2 elements.

2 1 3 4 5 and continue the same process.



Below is an example c code that takes 5 elements as input and outputs a sorted list (using bubble sort approach).

#include<stdio.h>

void main()

{

int i,a[5],j,temp,k;

clrscr();

printf("\nEnter 5 numbers to sort ::\n");

for(i=0;i<5;i++)

scanf("%d",&a[i]);

printf("\nElements before sort : ");

for(i=0;i<5;i++)

printf("%d\t",a[i]);

printf("\n====Bubble sort====\n");

for(i=0;i<5;i++)

{

 for(j=0;j<5-i;j++)

 {

  if(a[j]>a[j+1])

  {

   temp=a[j];

   a[j]=a[j+1];

   a[j+1]=temp;

  }

 }

printf("\nElements after round %d : ",i+1 );

for(k=0;k<5;k++)

printf("%d\t",a[k]);

}

printf("\n\nFinal List: ");

for(i=0;i<5;i++)

printf("%d\t",a[i]);

getch();

}

In the above example observe the code highlighted. This gives the core logic.

There are two loops that run n times. Therefore the  worst case running time will be O(n2).

• Minimum number of swaps 0 ( if the list is already sorted)
• Maximum swaps n(n-1)/2 ( if the list is in descending order)
• Minimum comparisions n(n-1)/2
• Maximum comparisions n(n-1)/2

For comparison of various sorting algorithms click here