# IIT Madras MS paper with solution

Hello Friends,

I am Madhav Purohit. I got call call from IITM for MS. Here is my experience and IIT Madras MS paper with solution.

## IIT Madras MS paper with solution

To enroll in (IITM) IIT Madras MS, you have to go through two phase. It is objective plus subjective test. They have given 90 min for each subjective and objective. There were 15 question and have to solve in 90 minute. If you complete it early you will get more time for subjective test.

### 1) Objective question:

Some of the Objective question that I am able to remember are…

**1)** What is Tim Berners Lee famous for?

**Ans:** He was the inventor of WWW(Wordl Wide Web)

**2)** 12 dice rolled, what is the probability of getting 6 different outcomes exactly every outcome comes twice ?

**Ans:** ((12!)/(2!^6))/6^12

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

Ans: Reachability of final state.

(If the final stage is reachable from 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.)

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

**Ans:** Suurballe’s algorithm

**5)** 6 stage pipeline, diff 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;

**Ans:** It would return 1 if number is odd else it would return 0.

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

**Ans:** n!

**8)**A POS expression was given, convert to SOP

**10)**Some question on partial order and their topological sorting

**11)** Min possible no: of multiplications for x^3 + x^2 + x + 1

**Ans:** 3

After completion of this test they will provide subjective question paper. There were 4 question each having 5 marks. You have to finish it within 90 min.

### 2)Subjective questions:

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

**Ans:**

We can prove this by induction hypothsis.

Induction:

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

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

Hypothesis:

Let Graph with n nodes each of at least degree n/2 be connected, we need to prove it is also connected for graph with n+1 nodes,|

Consider adding a new node to 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 degree, means n/2 edges so it would be connected to at least n/2 nodes in graph which is already connected so this whole graph with n+1 nodes will be connected.

**13)**Given an array of length n of 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 Divide and conquer rule to find and return the distinct element in the least possible time.

–

**Ans:**

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);

}

**14)** Question on reversing a linked list recursively. [A statement was missing, which was required to be filled in and explained for.]

Ans:

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;

}

**15)** Design a sequence detector which detects the pattern 011 and outputs a 1; otherwise it outputs 0.

All the best !!

Such clever work and

reporting! Keep up the awesome works guys