GATE CSE
First time here? Checkout the FAQ!
x
7,213 views

This post is a recollection of questions asked at IIT Kanpur Admission Test Mtech (CSE) 2016. (NOT COMPLETE, but quite many) Thanks Govind Gopakumar :)

Date of Exam: 7th May
Duration: 2 hours Objective + 2 hours Programming Test + 2 hours Subjective (Syllabus at the end)

When you clear first 2 tests, you get called for last. Some 120 people cleared from about 250 for subjective test (AFAIR)


Objective consisted of:  Fill in the gaps, MCQ, one liners (MCQs had negative marking, multiple choices could be right)


Objective:

  1. Theory
     
    1. Height of balanced tree, given the number of nodes.
       
    2. Number of distinct BFS, DFS trees in a graph where any pair of vertices is connected.
       
    3. Solution of $T(n) = T \left ( \sqrt n \right ) + 1$
       
    4. Expression for reachability matrix, given original matrix $A$ and initial reachability matrix $R$
      Also complexity of algorithm it will require.
       
    5. Find remainder: $2^{202} \mod 101$
       
    6. Which of following sets is bijection to set of natural numbers (or Integers maybe)
      $\Bigl ( \mathbb{Z}^{101} \Bigr ),  \Bigl ( \mathbb{Z} \times \mathbb{Q} \Bigr ), \Bigl ( \mathbb{Z} \times \mathbb{R} \Bigr ), \Bigl ( \mathbb{R}^2 \Bigr )$
       
    7. $\begin{align}S &\to aS \mid B \\ B &\to bB \mid \varepsilon \end{align}$
      Which of the following languages is generated?
      (Don't expect me to remember options too eh :D )
       
    8. Which of following languages doesn't have consecutive $b$'s?
      (4 or 5 regular language descriptions were given)
       
    9. Problem related to finding cycle in directed graph (Doubtful)
       
    10. A problem on randomized algorithms (Doubtful, didn't understand)
       
  2. Systems (Some taken from Govind Gopakumar's fb post):
     
    1. UNIX Commands were asked: Searching for file name (kind of)
      Linux command to list all files with a particular keyword in a directory above the current one.
       
    2. DBMS:  Question on performing joins efficiently - best join order - Number of intermediate Queries in best option
       
    3. $32$-bit signed integers - range of integers representable.
       
    4. Diffie-Hellman Key Exchange based on which abstract algebra problem.
       
    5. Problem related to representation of polynomials in Galois Fields (polynomial sum or something)
       
    6. A question on operator forwarding in pipelining (damn it was long, leave for last types :D)
       
    7. A question on operator forwarding in dual issue processors.
       
    8. Virtual Address $\to$ Cache Mapping Question
       
    9. Basic True/False Questions on Virtual Memory.
       
    10. Which segment in Linux process in memory contains information about dynamically linked libraries (something like that)
       
    11. DBMS: $R \Bigl ( \underline{P},  T, U \Bigr )$
      If an index is created on $T$, what will it be called?
      If a further index is created on $U$, what will it be called?
       
    12. Name of function used for integrity in symmetric-key environment.
       
  3. Data Science/ Applications (Didn't attempt this part. Completely ripped off from this post by Govind fb post)
     
    1. Probability question : There are different slots in a day. Batman and Robin can choose at most one slot each to guard (can be same). Different villains choose to attack on different slots (Bane could be defeated only if both Batman and Robin chose this slot). We had to find the probability that 0 villains were defeated, 1 was defeated etc. It had a few tricky cases here and there.
       
    2. Given a channel with one input (0 or 1), and a transition matrix which accounts for error in these inputs, find the entropy of the output. (This was out of syllabus AFAIK)
       
    3. The applications part had really nice questions on probability and linear algebra, mostly logic puzzle kind.

 


Programming Test:

(Partly taken from Govind Gopakumar's Post)

1. Finding number of inversions (find pairs such that i>j but a[i] < a[j].)

2. Checking if row_sum = column_sum for each position in a matrix (Given a grid with coins placed on it, you can take coins from a grid point only if the sum of coins in the point's row matches the sum of coins in the point's column. Find how many coins you can thus obtain. )

3. Calculating Distance values in Edit Distance Problem (Recurrence was provided. Allowed operations: Insert + Delete + Substitution) (Given two strings, find the edit distance between them)

---------------------------   ---------------------------   ---------------------------

Subjective Test:

Again lots of content provided by Govind Gopakumar. The entire Applications part specially :)

I. Theory:

1.  Prove/Disprove:

a) If a graph has k-independent components, it it n-k+1 colorable

b) converse of (a)

c) If a graph is not n-1 colorable, it's a clique

 

2. a) Write O(n) time algorithm to find any cycles in a graph. Print NONE otherwise

b) Prove it's O(n)

 

II. Systems:

1. S is a semaphore.

AddAtomic(Queue* Q1, Queue* Q2)

{

Q1 -> S.wait();

Q2 -> S.wait();

E = Q1 -> dequeue();

Q2 -> enqueue(E);

Q2 ->s.signal();

Q1 -> S.signal();

}

 

This is ought to be a code to atomically dequeue an element from Q1, and add to Q2.

a) Find problem with the implementation

b) Implement a correct solution.

 

2. Give one reason why hierarchical multilevel paging is useful

 

3. Page Table Entry => 8B

Page Size => 4 KB

4-level page table

What is the maximum virtual address space possible?

 

III. Data Science/Applications:


1)

a) Define what a convex set is.
b)Consider two sets A and B of elements from a vector space. Define C = A+B as {x+y | for all x in A and y in B, + here denotes vector addition} Prove C is convex or not. (I think a rigorous definition of this is called the minkowski sum)
c) Define C = A-B similarly, prove if convex or not.

2) a) Consider a discrete sample space {L1, L2...}. Write the expression for expected value of this random variable.
b) Consider two random variables X and Y, which are independent. Prove or provide counterexample for E(X and Y) = E(X)*E(Y) (Where E is expected value)

3) Consider a symmetric matrix A. Prove that the eigenvectors corresponding to distinct eigenvalues of this matrix are orthogonal.

4) a)Consider |u| = 5 and |v| = 6 for two vectors u and v. For the matrix u*v', find the matrix norm (show all steps in computation).
b)prove that |A^t| ≤ |A|^t where A is a matrix and the notation denotes matrix norm.

 

-------------------------- ----------------------------------- --------------------------

Other Stuff:

1. Needed to do atleast 2/3 parts in objective and subjective part.

2. I think programming part had good weightage (as neither of my objective or subjective were great, though in programming did all of them ;) )

3. You get lots of time, manage it well.

4. Read questions properly.

5. Programming part was in C, take care of string processing, took me lots of time, as I had forgotten :P  ( Long time :D )

6. Don't ask me for answers or clarifications, as (a) I'm out of practice (b) I had written these in a copy after-exam, so don't remember much now. Ask other members or in the group

7. Don't send me an instant friend request as a token of appreciation :D . If you have stuff to ask, you're  welcome though ;)

Everyone who gave the test, is welcome to add/edit/suggest content to this post :)

To Everyone else, Open to Suggestions

-------------------------- ----------------------------------- --------------------------

EDIT: Here's another experience  and this one adds some questions in Data Science/Application Part by jagadeesha_kanihal

-------------------------- ----------------------------------- --------------------------

Syllabus below:

 

posted Jul 2, 2016 in Interview Experience by Junior (875 points)  
edited Jul 8, 2016 by | 7,213 views

9 Comments

Thanks Arindam again :)
Anyone here going for it? May be we can have some discussion next week for it.
how many u attempted in all these sections???

...n plz provide soln too
@Arjun Learning from you guys :)
@schaturbedi try to solve them. If you get stuck, ask on this forum or gatecse group on fb.
Thanks..
Could someone clarify as to weather the test dates are flexible?....because apparently with increasing number of competitive exams held around the year its very hard to attend them ......

For instance this written test by IITK seems to have been held on May 7th 2016, and there was written test for M.Tech(CSE) for ISI Kolkatta on May 8th 2016.

1) What is the option for a candidate who has to write both these exams?

2) Are there direct admission for M.Tech in IITK based on gate rank?

Please clarify.

Thanks
1) You can mail the people involved, but usually they will not be able to move either test, as there are a lot of factors that make them decide the dates and it's not convenient to move once decided.

 

2) Yes, the last rank that was offered direct admit was 95, I think.
In programming test is there any option to choose language (like java or c++) or it is fixed as C?
It was fixed as C.
Top Users Sep 2017
  1. Habibkhan

    7166 Points

  2. Warrior

    2640 Points

  3. Arjun

    2574 Points

  4. rishu_darkshadow

    2520 Points

  5. A_i_$_h

    2280 Points

  6. nikunj

    1980 Points

  7. manu00x

    1846 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,144 questions
33,728 answers
79,957 comments
31,117 users