An approach for GATE preparation

Preparing for GATE is not like studying for a regular exam. It is almost like doing a research in all the fields of Computer Science. Every topic in every subject has to be studied in great detail, possibly from multiple sources. A key skill required for doing well in an exam like GATE is Problem Solving Ability. Engineering, after all, is about the ability to apply your knowledge to solve real world problems. But most engineering colleges do not emphasize on problem solving, only on rote learning.

A suggested approach

Once the study of GATE syllabus is over, one should focus on learning problem solving. A very good way to do this is to try and solve some of the problems in previous GATE papers "completely". The focus should be not  just on finding the right answer, but making sure that you understand how the answer is derived. Take some problems and spend as much time as you want, refer as many resources as you want, but find (and understand) the answer. Working like this will immensely increase your understanding of CS concepts. Not only you will learn the concepts, you will also learn the intuition behind those concepts, which is a more important learning.

To illustrate the point, I will take a problem in some previous GATE paper and solve it. I will try to explain or provide references to theory that is required to understand the solution. I will begin with a simple problem today and analyze more interesting problems in subsequent posts.

Example

I will take a simple example from GATE 2015, Paper 1.

What we need to know? 

What we need to understand to solve this problem is that when two functions are executed concurrently by the OS, they are not actually being executed concurrently, since there is only one processor which can execute only one instruction at a time. So when the above to functions are executed "concurrently",  the OS is just interleaving the statements of these two functions. The final value of B will depend on the actual order in which the statements get executed.

There are multiple ways in which the statements of P1 and P2 can be interleaved, one of them is:

//Initial Value of B is given to be 2

C = B - 1;                 //Value of C = 1

B = 2 * C;                 //Value of B = 2

              D = 2 * B;   //Value of D = 4

              B = D - 1;   //Value of B = 3

//Final value of B is 3

How I would have solved it? 

What we could do is try out all possible inter-leavings of these statements and manually find out what is the value of B for each of these cases. One possible interleaving I have shown above, another is: 

//Initial Value of B is given to be 2

C = B - 1;                 //Value of C = 1

              D = 2 * B;   //Value of D = 4

              B = D - 1;   //Value of B = 3

B = 2 * C;                 //Value of B = 2

//Final value of B is 2

Note that the OS can only interleave the statements of P1 and P2, it cannot change the order of statements within a function. By analyzing all possible inter-leavings, we can find that the values that B can take are 2, 3, and 4. Hence the answer is 3

PS: If you feel there is any inaccuracy in the explanation or feel that I have missed something, please feel free to point out. I will definitely improve my solution with everybody's suggestions.