GATE 2009 Question Paper - Part 1
1. Which one of the following is NOT necessarily a property of a group?
a. Commutativity
b. Associativity
c. Existence of inverse for every element
d. Existence of identity
2. What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n>= 2
a. 2
b. 3
c. N-1
d. N
3. Which one of the following is true for any simple connected undirected graph with more than 2 vertices?
a. No two vertices have same degree
b. At least two vertices have the same degree
c. At least three vertices have the same degree
d. All vertices have same degree
4. Consider the binary relation R = {(x,y),(x,z),(z,x),(z,y)} on the set {x,y,z}. Which one of the following is true?
a. R is symmetric but not antisymmetric
b. R is not symmetric but antisymmetric
c. R is both symmetric and antisymmetric
d. R is neither symmetric nor antisymmetric
5. (1217)8 is equivalent to
a. (1217)16
b. (028F)16
c. (2297)10
d. (0B17)16
6. What is the minimum number of gates required to implement the boolean function (AB+C) if we have to use only 2-input NOR gates?
a. 2
b. 3
c. 4
d. 5
7. How many 32K X 1 RAM chips are needed to provide a memory capacity of 256K bytes?
a. 8
b. 32
c. 64
d. 128
8. A CPU generally handles an interrupt by executing an interrupt service routine
a. As soon as an interrupt is raised.
b. By checking the interrupt register at the end of the fetch cycle
c. By checking the interrupt register after finishing execution of the current execution
d. By checking interrupt register at fixed time intervals
9. In which one of the following page replacement policies, Belady’s anomaly may occur?
a. FIFO
b. Optimal
c. LRU
d. MRU
10. The essential content(s) in each entry of a page table is/are
a. Virtual page number
b. Page frame number
c. Both
d. Access right information
11. What is the number of swaps required to sort n elements using selection sort, in the worst case?
a. Ѳ(n)
b. Ѳ(n log n)
c. Ѳ(n2)
d. Ѳ(n2 log n)
12. S -> aSa bSb a b
The language generated by the above grammar over the alphabet {a,b} is the set of
a. All palindromes
b. All odd length palindromes
c. Strings that begin and end with the same symbol
d. All even length palindromes
13. Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm?
P:always finds a negative weighted cycle, if one exists.
Q:finds whether any negative weighted cycle is reachable from the source
a. P only
b. Q only
c. Both P and Q
d. Neither P nor Q
14. Let πA be a problem that belongs to the class NP. Then which one of the following is TRUE?
a. There is no polynomial time algorithm for πA
b. If πA can be solved deterministically in polynomial time, then P=NP
c. If πA is NP-hard, then it is NP-complete
d. πA may be undecidable
15. Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
a. The set of all strings containing the substring 00.
b. The set of all strings containing at most two 0’s.
c. The set of all strings containing at least two 0’s.
d. The set of all strings that begin and end with either 0 or 1.
16. Which one of the following is false?
a. There is a unique minimal DFA for every regular language.
b. Every NFA can be converted to an equivalent PDA.
c. Complement of every context-free language is recursive.
d. Every non deterministic PDA can be converted to an equivalent deterministic PDA.
17. Match all items in Group 1 with correct options from those given in Group 2
Group 1 Group 2
P. Regular expression 1. Syntax analysis
Q. Pushdown automata 2. Code generation
R. Dataflow analysis 3. Lexical analysis
S. Register allocation 4. Code optimization
a. P – 4, Q – 1, R – 2, S – 3
b. P – 3, Q – 1, R – 4, S – 2
c. P – 3, Q – 4, R – 1, S – 2
d. P – 2, Q – 1, R – 4, S – 3
18. Consider the program below
#include
int fun(int n, int *f_p)
{
int t,f;
if(n<=1) {
*f_p=1;
return 1;
}
t=fun(n-1,f_p);
f=t+ *f_p;
*f_p=t;
return f;
}
int main() {
int x=15;
printf ("%d", fun(5, &x));
return 0;
}
The value printed is:
b. 8
c. 14
d. 15
19. The coupling between different modules of a software is categorized as follows:
I. Content Coupling
II. Common Coupling
III. Control Coupling
IV. Stamp Coupling
V. Data Coupling
Coupling between modules can be ranked in the order of strongest (least desirable) to weakest (most desirable) as follows:
a. I – II – III – IV – V
b. V – IV – III – II – I
c. I – III – V – II – IV
d. IV – II V – III – I
20. Consider the HTML table definition given below:
ab
cd
ef
gh
ik
The number of rows in each column and the number of columns in each row are:
a. <2,2,3> and <2,3,2>
b. <2,2,3> and <2,2,3>
c. <2,3,2> and <2,3,2>
d. <2,3,2> and <2,2,3>
21. An unbalanced dice (with 6 faces, numbered from 1 to 6) is thrown. The probability that the face value is odd is 90% of the probability that the face value is even. The probability of getting any even numbered face is the same. If the probability that the face is even given that it is greater than 3 is 0.75, which one of the following options is closest to the probability that the face value exceeds 3?
a. 0.453
b. 0.468
c. 0.485
d. 0.492
22. For the composition table of a cyclic group shown below
* a b c d
------------
a a b c d
b b a d c
c c d b a
d d c a b
Which one of the following choices is correct?
a. a, b are generators
b. b, c are generators
c. c, d are generators
d. d, a are generators
23. Which one of the following is the most appropriate logical formula to represent the statement : “Gold and silver ornaments are precious”. The following notations are used:
G(x):x is a gold ornament
S(x):x is a silver ornament
P(x):x is precious
a. For all x (P(x) -> (G(x) ^ S(x)))
b. For all x ((G(x) ^ S(x)) -> P(x))
c. There exists x ((G(x) ^ S(x)) -> p(x))
d. For all x ((G(x) v S(x)) -> P(x)
24. The binary operation o is defined as follows
P Q P o Q
T T T
T F T
F T F
F F T
a. ¬ Q o ¬ P
b. P o ¬ Q
c. ¬ P o Q
d. ¬ P o ¬ Q
25. ∫0 π/4 ((1-tan x)/(1+tan x)dx ) evaluates to
a. 0
b. 1
c. ln 2
d. ½ ln 2
26. Consider the following well-formed formula:
I. not for all x (P(x))
II. not there exists x (P(x))
III. not there exists x (not P(x))
IV. there exists x(not P(x))
a. I and III
b. I and IV
c. II and III
d. II and IV
27. Given the following state table of FSM with two states A and B, one input and one output:
Present State A Present State B Input Next State A Next State B Output
0 0 0 0 0 1
0 1 0 1 0 0 1
1 0 0 0 1 0
1 1 0 1 0 0
0 0 1 0 1 0
0 1 1 0 0 1
1 0 1 0 1 1
1 1 1 0 0 1
If the initial state is A=0, B=0, what is the minimum length of an input string which will take the machine to the state A=0, B=1 with Output =1?
a. 3
b. 4
c. 5
d. 6
28. Consider a 4-stage pipeline processor. The number of cycles needed by the four instructions I1, I2, I3, I4 in stages S1 ,S2 ,S3 ,S4 is shown below:
S1 S2 S3 S4
I1 2 1 1 1
I2 1 3 2 2
I3 2 1 1 3
I4 1 2 2 2
What is the number of cycles needed to execute the following loop:
For (i=1 to 2) { I1; I2; I3; I4; }
a. 16
b. 23
c. 28
d. 30
29. Consider a 4-way set associative cache (initially empty) with total 16 cache blocks. The main memory consists of 256 blocks and the request for memory blocks is in the following order:
0, 255, 1, 4, 3, 8, 133, 159, 216, 129, 63, 8, 48, 32, 73, 92, 155
Which one of the following memory block will not be in cache if LRU is used?
a. 3
b. 8
c. 129
d. 216
30. Consider a system with 4 types of resources R1 (3 units). R2 (2 units), R3 (3 units), R4 (2 units). A non-preemptive resource allocation policy is used. At any given instance, a request is not entertained if it cannot be completely satisfied. Three processes P1, P2, P3 request the resources as follows if executed independently.
Process P1:
T=0: requests 2 units of R2
T=1: requests 1 unit of R3
T=3: requests 2 units of R1
T=5: releases 1 unit of R2 and 1 unit of R1
T=7: requests 1 unit of R3
T=8: requests 2 units of R4
T=10: finishes
Process P2:
T=0: requests 2 units of R3
T=2: requests 1 unit of R4
T=4: requests 1 unit of R1
T=6: releases 1 unit of R3
T=8: finishes
Process P3:
T=0: requests 1 unit of R4
T=2: requests 2 units of R1
T=5: releases 2 units of R1
T=7: requests 1 unit of R2
T=8: requests 1 unit of R3
T=9: finishes
Which one of the following statements is true if all 3 processes run concurrently starting at time t=0?
a. All processes will finish without any deadlock
b. Only P1 and P2 will be in deadlock
c. Only P1 and P3 will be in deadlock
d. All 3 processes will be in deadlock
31. Consider a disk system with 100 cylinders. The request to access the cylinders occur in following sequence:
4, 34, 10, 7, 19, 73, 2, 15, 6, 20
Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all requests if it takes 1 ms to move from one cylinder to adjacent one and shortest seek time first policy is used?
a. 95ms
b. 119ms
c. 233ms
d. 276ms
32. In the following process transition diagram for a uniprocessor system, assume that there are always some processes in the ready state:
Now consider:
I. If a process makes transitions D, it would result in another process making transition A immediately
II. A process P2 in blocked state can make transition E while another process P1 is in running state
III. The OS uses preemptive scheduling
IV. The OS uses non-preemptive scheduling
Which of the above are TRUE?
a. I and II
b. I and III
c. II and III
d. II and IV
Connect your Pen Drive or USB drive to your computer .
Now a dialogue window will popup asking you to choose among the options as shown in the figure.
*Now go to Start--> Run and type cmd to open the Command Prompt window .
*Now go to My Computer and Check the Drive letter of your USB drive or Pen Drive. ( E.g. If it is written Kingston (I:) , then I: will be the drive letter .)
*In the Command Window ( cmd ) , type the drive letter: and Hit Enter .
*Now type dir/w/o/a/p and Hit Enter
*You will get a list of files . In the list , search if anyone of the following do exist
1. Autorun.inf
2. New Folder.exe
3. Bha.vbs
4. Iexplore.vbs
5. Info.exe
6. New_Folder.exe
7. Ravmon.exe
8. RVHost.exe or any other files with .exe Extension .
If you find any one of the files above , Run the command attrib -h -r -s -a *.* and Hit Enter.
Now Delete each File using the following Command del filename ( E.g del autorun.inf ) .
That's it . Now just scan your USB drive with the anti virus you have to ensure that you made your Pen Drive free of Virus .
This virus is very very common now...To know whether ur system is infected just type C:\heap41a in the address bar...if there is a folder named heap41a, then ur system is infected...
Hanging Heart 
Materials required:
* Tracing Paper
* Pencil
* Salt dough
* Roller
* Rolling Pin
* Craft knife
* Acrylic or fabric paint
* Paintbrushes
* Gold paperclips
* Polyurethane matt varnish
* Glue
Procedure to make heart:
First prepare the salt dough to make the decoration. Mix together 2 cups of flour and 1 cup of salt. Add 1 cup of water gradually to the mixture until it is stiff but not sticky. Knead the dough for about ten minutes until it is smooth and manageable.
Roll the dough out on a roller or a flat surface with a rolling pin in 1cm thickness.
Draw or trace out a heart shaped design. Place the design over the rolled dough and mark the squares with a needle or a pin. Then cut out the heart carefully from the rolled dough. Smoothen and round the edges with a moistened finger. Alternatively you can cut out the design from the rolled dough on your own, with a knife without the help of the design 
With a knife carefully deepen the lines of the squares without going too deep so that the squares are not cut off. You can either fill the heart with squares or leave both sides free as in the figure.
Cut a paperclip in half and insert into the top of the heart. Make as many hearts as you need. Allow to dry thoroughly for a few days OR Bake in a warm oven at 120o C/250oF for a short time, but take care not to cook them or they will yellow. 
Paint with acrylic emulsion (latex), then paint in the colour of your choice, leaving alternate squares plain. Allow to dry. Apply five coats of varnish. Thread some ribbon through the loop made by the paper clip and tie in a bow. You can hang your hearts from the wall.
BASIC MATHEMATICS:Elements of probability, matrix algebra, numerical methods: interpolation, root finding, differentiation and integration. Discrete mathematics: sets, relations, functions, mathematical induction, counting, groups, graphs, partial orders, lattices and boolean algebra, propostional logic.
THEORY OF COMPUTATION:Regular and context free languages, finite state machines and push down automata, turing machines and undecidability.
COMPUTER HARDWARE:Logic function, minimization techniques, design of combinational and sequential circuits using gates and flip-flops, design with integrated circuts incuding ROM and multiplexers, microprocessor architecture: programming, interfacing with memory and I/O devices(modes of data transfer and their implementation, serial and parallel communication interface). Detailed knowledge of 8085 microprocessor will be assumed.
COMPUTER ORGANIZATION:Number representation and airthmetic, functional organization, machine instructions and addressing modes, ALU, hardwired and microprogrammed control, instrucation pipelining, memory organization, input/output.
PROGRAMMING AND DATA STRUCTURE:structured programmming with pascal/C including recursion; arrays, stacks, strings, queues, lists, trees, sets and graphs; algorithm for tree and graphs traversals, connected component, spanning trees, shortest paths; hashing, sorting and searching algorithm design and analysis techniques, big 'oh' notation, solution of sample recurrence relations.
LANGUAGE PROCESSOR:Assembler, loader, linker, macroprocessors, text editors, programming languages, scope rules and parameter passing mechanism; compilers lexical analysis, parsing, syntax, directed translation, run time environment, machine code generation; interpreters.
OPERATING SYSTEM:Batch, multi-programming and time-sharing systems; processsor, memory, device and file management, virtual memory, process scheduling, interprocess communication, process synchoronization and concurrency, deadlocks, protection.
DATABASE SYSTEM:File organization techniques; indexing,B-trees, B-plus trees; relational and network datat models; normal forms; query language: SQL.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
When we honestly ask ourselves which person in our lives means the most to us, we often find that it is those who, instead of giving much advice, solutions, or cures, have chosen rather to share our pain and touch our wounds with a gentle and tender hand. The friend who can be silent with us in a moment of despair or confusion, who can stay with us in an hour of grief and bereavement, who can tolerate not knowing, not curing, not healing, and face with us the reality of our powerlessness, that is a friend who cares.
- Henri Nouwen, Out of Solitude