IIT Madras MS Question Paper | Written Test

Hello Friends, I am Madhav Purohit. I got a call from IITM for MS. Here are my experience and IIT Madras MS question paper with a solution.

IIT Madras MS Question Paper with Solution

To enroll in (IITM) IIT Madras MS, you have to go through a two-phase written test. It is an objective plus subjective test.

Written Test Format: They have given 90 minutes for each subjective and objective. There were 15 questions and have to solve them in 90 minutes.

If you complete objective test early, you will get more time for subjective test.

Objective Questions | Written Test

Some of the objective question that I am able to remember are as follows.

1) What is Tim Berners Lee famous for?

Answer: He was the inventor of WWW (World Wide Web).

2) 12 dice rolled. What is the probability of getting six different outcomes exactly every outcome comes twice?

Answer: ((12!)/(2!^6))/6^12

This is question from aptitude test. Practice solving aptitude questions.

3) Write down the name of the algorithm that is used to find the language accepted by DFA is empty or not?

Answer: Reachability of the final state.

If the final stage is reachable from the start state then there is at least a single string of language for which simulating the DFA would take us to the final stage which is part of language and language would not be empty then.

Check this similar DFA example.

4) Name of the algorithm to find out the disjointed path in graph?

Answer: Suurballe’s algorithm

5) This question was from COA (Computer Organization and Architecture). There are six stages of the pipeline. Each stage requires time needed for each stage given like opcode fetching – 2ns, Instruction decoding – 1.8 ns, operand fetching – 2.6ns Execution stage 1 -1.6 ns. Execution stage 2 – 1.9 ns, write – 3ns, Clock freq read so as to avoid any timing clashes.

6) What does the following code snippet do?

int c=31, n;
scanf("%d", &n);
int k=n<<c;
if(k&1) return 1;
return 0;

Answer: It would return “1” if number is odd else it would return “0”.

7) Find the number of surjective function possible from the relation <1,2,3,4…,n> to <1,2,3,4…,n>?

Answer:  n!

8) A POS expression was given. You have to convert it to SOP.

10) Some question on partial order and their topological sorting

11) Minimum possible number of multiplications for x^3 + x^2 + x + 1

Answer: 3

After completion of this test, they will provide a subjective question paper. There were four questions each having five marks. You have to finish it within 90 minutes.

Subjective Questions | Written Test

12) If the degree of each vertex of a simple undirected graph of n nodes is at least n/2, then show that the graph is connected.

Answer: We can prove this by induction hypothsis.

Induction:

Let the number of nodes be 2 in the graph i.e each node would be of degree 1 at least.

As the graph is simple, Loop is not allowed the only option for degree one for both graphs is an edge between both nodes.

Hypothesis:

Let’s consider the graph with n nodes each of at least degree n/2 be connected. We need to prove it is also connected for a graph with n+1 nodes.

Consider adding a new node to the connected graph of degree n with each node having at least n/2 degree. Now adding this node would also have at least degree n/2, means n/2 edges so it would be connected to at least n/2 nodes in the graph which is already connected. So, this whole graph with n+1 nodes will be connected.

13) Given an array of length n numbers and access to a function “total” which can compute and return the sum of any sub-array of the given array in O(1) time. The array has n-1 elements identical, and “1” element different.

Write an algorithm using the divide and conquer rule to find and return the distinct element in the least possible time.

Answer:

findTheUnique(A,i,j)
{
  if(i==j)
    return i;
  else if(total(A,i,(i+j)/2)!= 2*total(A,i,(i+j)/4))
    findTheUnique(A, i, (i+j)/2);
  else
    findTheUnique(A, (i+j)/2+1, j);
}

To solve these types of coding questions, you have to understand recursion very well. There are six types of recursion.

14) Question on reversing a linked list recursively.

A statement was missing, which was required to be filled in and explained it.

Answer:

static void reverse(struct node** head_ref)
{
  struct node* prev   = NULL;
  struct node* current = *head_ref;
  struct node* next;
  while (current != NULL)
  {
    next  = current->next;
    current->next = prev;
    prev = current;
    current = next;
  }
  *head_ref = prev;
}

For explanation, refer reverse linked list tutorial.

15) Design a sequence detector that detects the pattern 011 and outputs a “1”; otherwise, it outputs “0”.

If you crack these written tests, you will be asked for an interview. Read interview experience shared by the candidate. You are just one step away from getting admission into IIT Madras for MS.

If you have any questions or doubts about IIT Madras MS admission, ask me in the comment section.

All the best!

Editors’ Note: This experience and IIT Madras MS question paper are shared by Madhav Purohit. He is alumni of IIT, Kanpur. We wish him all the best.