The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

My GATE 2017 rank is 101 and I was targeting IIT Kanpur and IIT Delhi for admission. So in this blog I am writing about my tests experience at IIT Kanpur.

This year they called around 400 people for the test. They conducted 3 tests(Objective, Programming and Subjective). They conducted Objective and Programming test on 13^{th} May. On the basis of these 2 tests, they shortlisted around 180 people for Subjective test which was conducted on 14^{th} May. Among all these 3 tests, Objective test was the easiest one.

**Objective Test**

Objective test consist of 3 sections(Theory, Systems and Statistics & Data science). Each section was of 50 marks and we have to attempt any 2 sections in 3 hours. There were some fill in the blanks and one line answer questions too and for the questions with options, more than one option can be correct. There was no negative marking. Some of the questions asked in this test are :

**1) Theory**

i) 8a + 19b = 1. So find out the possible values of a and b.

ii) one dfa was given and we have to choose the correct regular expression for it from the options given

iii) DFA was given and the probability of each link in DFA was also given. So we have to find the probability to reach a particular state using the given 2 strings.

**2) Systems**

i) A question on semaphore to find initial value of semaphore variable

ii) To find number of hosts in a network given the subnet mask

iii) Difference between clustered and non-clustered indexes

iv) Number of clustered and non-clustered indexes

v) A query is given with EXIST clause and we have to rewrite it without using EXIST

vi) A question on finding accuracy of Branch prediction. A DFA was given for it and program sequence was also given telling whether it will take the branch or not

**Programming Test**

I am not able to recall questions from Statistics & Data science because I attempted only theory and Systems section. Next was the programming test. There were 4 programs to solve in 3 hours. Marks of each program were 30, 40, 60 and 75. The questions asked where :

1) Question to check anagram ( 40 marks )

2) Starting index of leaves and value of leaves of complete binary tree where given, with the property that parent will have min(left child, right child). We have to return the the contents of indices asked for the tree. ( 30 marks )

for example,

starting index = 3 and

leaves values are 1, 9, 5 and 2

above 2 information will be given, So the tree will be like

min(1,2)=1

/ \ 1

min(1,9) min(5,2) => / \

= 1 = 2 1 2

/ \ / \ / \ / \

1 9 5 2 1 9 5 2

3) There are p prisoners and c ( > p) cell blocks. c and p will be given as input. Also a sorted list of c integers will be given. You are required to choose p integers from c integers such that the minimum distance between adjacent prisoners is maximized. You have to output this minimum distance. ( 60 marks )

4) We have to find addition factors of a number in lexicographic order for n<15. ( 75 marks )

for example if n=4 then output will be

1 1 1 1

1 1 2

1 3

2 2

**Subjective Test**

Finally there was a subjective test similar to objective one. We have to attempt questions from any 2 sections in 3 hours. There were 3 questions from theory and 3 questions from Systems. Questions asked where :

**1) Theory**

i)

a) if degree of vertices < 3, then prove that the graph will be union of vertex disjoint path and cycle.

b) Graph Matching was explained. Let S and R be the matching graph, then a new graph G=(S-R) ∪ (R-S), will be union of vertex disjoint path and cycle. Also prove that the cycle obtained will be of even length.

ii) Consider a grammar G with productions P. Let INIT(G) be the grammar with production P' such that

P' = P ∪ ( A->B | such that A->BC belongs to P ) ∪ ( A->epsilon | such that A->b belongs to P )

prove that:

a) Prefix(G) is subset of INIT(G)

b) INIT(G) is subset of Prefix(G)

iii) Algorithm to find strongly connected components in the graph

**2) Systems**

i) Question on semaphore. A program was given which was incrementing variable y. 8 processes where allowed to execute the program. Initial value of y was given. We have to find possible values of y after all 8 processes complete their execution.

ii) Information about main memory and cache was given. We have to find number of bits for tag and index for direct mapped, set associative and fully associative cache. We also have to find cache capacity including tag overhead for each cache. Also explain the working of each cache mechanism.

iii) I didn't understood this question.

I have written as many questions that I recall. If you guys remember any more questions especially for objective one, write in the comment, I will add it.

Verdict :- Selected :)

Thank you for the info,but don't you get direct admission in IIT-k at this rank?

This year there was no direct admission for people applying via GATE. But 2 people got direct admission via their undergraduate CPI

Thanks for sharing ur experience. From the kind of questions that u have faced, it seems what was asked was more of conceptual and application part. Thanks again. :)

Congratulations!

For me, the subjective proving questions would be the hardest to solve. What if we do really badly in that section? How did you prepare for it? How did it go?

For me, the subjective proving questions would be the hardest to solve. What if we do really badly in that section? How did you prepare for it? How did it go?

I think final selection was based on subjective only. So if it goes bad then it will be hard to get selected.

For this kanpur tests I only revised my notes. But during GATE preparation, I have watched Kosaraju's algorithm for strongly connected component by Tushar Roy and that helped me a lot. ( Direct question was there ).

So for me the preparation that I did for GATE helped me a lot. Do prepare seriously and don't skip the proofs, Because that will be helpful in not only solving tricky questions in GATE but also during interviews and such tests.

For this kanpur tests I only revised my notes. But during GATE preparation, I have watched Kosaraju's algorithm for strongly connected component by Tushar Roy and that helped me a lot. ( Direct question was there ).

So for me the preparation that I did for GATE helped me a lot. Do prepare seriously and don't skip the proofs, Because that will be helpful in not only solving tricky questions in GATE but also during interviews and such tests.

I am repeater and I did self study. Although my first try was casual and got rank around 7k, but this time I prepared seriously.

The fact is to improve the maximum distance using binary search.

similar problem: http://www.spoj.com/problems/AGGRCOW/

Topcoder has a nice tutorial for modified binary search.

In this problem we need to choose p integers from c integers such that the minimum distance between adjacent prisoners is maximized

Does this mean that these p integers has to be in adjacent indexes?

Say 1,2,3,4 is a valid index to choose 4 integer but 1,4,7,9 is nto valid since these are not adjacent.Can you help me in understanding this question?

Does this mean that these p integers has to be in adjacent indexes?

Say 1,2,3,4 is a valid index to choose 4 integer but 1,4,7,9 is nto valid since these are not adjacent.Can you help me in understanding this question?

Let's say |c| = 5 and |p| = 3

c sequence -> 1, 3, 7, 8, 9 (As far as i think the c sequence can be considered as point distances in a straight line)

Now, where can we place 3 prisoners such that the distance between them is maximum.

Let's say we put them as **1**, 3, 7, **8**, **9** , here min distance between any two adjacent prisoners is 1 (9-8 = 1).

Let's try another possibility **1**, 3, **5**, 7, **8, **here the min distance between any two adjacent prisoners is (8-5 = 3).

We wan't such placements such that minimum distance between any two prisoner is maximized.

4th programming question:-https://www.geeksforgeeks.org/generate-unique-partitions-of-an-integer/

- All categories
- Testimonials 48
- Numerical Ability 0
- Verbal Ability 1
- Engineering Mathematics 7
- Algorithms 2
- Databases 2
- Digital Logic 3
- CO & Architecture 2
- Computer Networks 3
- Compiler Design 2
- Programming & Data Structures 6
- Motivation 18
- Preparation Advice 59
- Theory of Computation 2
- Preparation Experience 31
- Useful Links 11
- Study Materials 16
- Others 169
- Interview Experience 30
- Announcements 57

35,535 questions

42,875 answers

121,904 comments

42,216 users