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:
- Theory
- Height of balanced tree, given the number of nodes.
- Number of distinct BFS, DFS trees in a graph where any pair of vertices is connected.
- Solution of $T(n) = T \left ( \sqrt n \right ) + 1$
- Expression for reachability matrix, given original matrix $A$ and initial reachability matrix $R$
Also complexity of algorithm it will require.
- Find remainder: $2^{202} \mod 101$
- 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 )$
- $\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 )
- Which of following languages doesn't have consecutive $b$'s?
(4 or 5 regular language descriptions were given)
- Problem related to finding cycle in directed graph (Doubtful)
- A problem on randomized algorithms (Doubtful, didn't understand)
- Systems (Some taken from Govind Gopakumar's fb post):
- 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.
- DBMS: Question on performing joins efficiently - best join order - Number of intermediate Queries in best option
- $32$-bit signed integers - range of integers representable.
- Diffie-Hellman Key Exchange based on which abstract algebra problem.
- Problem related to representation of polynomials in Galois Fields (polynomial sum or something)
- A question on operator forwarding in pipelining (damn it was long, leave for last types :D)
- A question on operator forwarding in dual issue processors.
- Virtual Address $\to$ Cache Mapping Question
- Basic True/False Questions on Virtual Memory.
- Which segment in Linux process in memory contains information about dynamically linked libraries (something like that)
- 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?
- Name of function used for integrity in symmetric-key environment.
- Data Science/ Applications (Didn't attempt this part. Completely ripped off from this post by Govind fb post)
- 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.
- 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)
- 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:
