Information on Online Interviews
The MS-PhD entrance examination will be conducted offline at Indian Institute of Technology Kanpur. There will be three parts of the examination: a) Written Test, b) Coding Test, c) Interview. A candidate should aim to be familiar with the syllabus listed below for the written and coding test. Moreover, the coding test will be conducted in C language. More detailed questions could be asked to the candidate during the interview depending on his/her area of interest.
Syllabus for Written Test
-
Section 1: Engineering Mathematics
Discrete Mathematics: Propositional and first order logic. Sets, relations, functions, partial orders and lattices. Monoids, Groups. Graphs: connectivity, matching, coloring. Combinatorics: counting, recurrence relations, generating functions.
Linear Algebra: Matrices, determinants, system of linear equations, eigenvalues and eigenvectors, LU decomposition, Trace of a matrix, Hessian, Gradient, Jacobian; Symmetric Matrices; Orthogonal Matrices.
Calculus: Limits, continuity and differentiability. Maxima and minima. Mean value theorem. Integration. Chain Rule. Taylor Series.
Probability and Statistics: Random variables; Function of Random Variables; PDF; CDF; Expectation of Random Variable; Expectation of a function of a random variable; Uniform, normal, exponential, poisson and binomial distributions. Mean, median, mode and standard deviation. Conditional probability and Bayes theorem;
-
Section 2: Digital Logic
Boolean algebra. Combinational and sequential circuits. Minimization. Number representations and computer arithmetic (fixed and floating point).
-
Section 3: Computer Organization and Architecture
Machine instructions and addressing modes. ALU, data‐path and control unit. Instruction pipelining, pipeline hazards.
Memory hierarchy: cache, main memory and secondary storage; I/O interface (interrupt and DMA mode).
-
Section 4: Programming and Data Structures
Programming in C. Recursion. Arrays, stacks, queues, linked lists, trees, binary search trees, binary heaps, graphs.
-
Section 5: Algorithms
Searching, sorting, hashing. Asymptotic worst case time and space complexity.
Algorithm design techniques: greedy, dynamic programming and divide‐and‐conquer. Graph traversals, minimum spanning trees, shortest paths.
-
Section 6: Theory of Computation
Regular expressions and finite automata. Context-free grammars and push-down automata. Regular and context-free languages, pumping lemma. Turing machines and Undecidability.
-
Section 7: Compiler Design
Lexical analysis, parsing, syntax-directed translation. Runtime environments. Intermediate code generation. Local optimisation, Data flow analyses: constant propagation, liveness analysis, common subexpression elimination.
-
Section 8: Operating System
System calls, processes, threads, inter‐process communication, concurrency and synchronization. Deadlock. CPU and I/O scheduling. Memory management and virtual memory. File systems.
-
Section 9: Databases
ER‐model.
Relational model: relational algebra, tuple calculus, SQL. Integrity constraints, normal forms. File organization, indexing (e.g., B and B+ trees). Transactions and concurrency control.
-
Section 10: Computer Networks
Concept of layering: OSI and TCP/IP Protocol Stacks; Basics of packet,circuit and virtual circuit- switching;
Data link layer: framing, error detection, Medium Access Control, Ethernet bridging;
Routing protocols: shortest path, flooding, distance vector and link state routing; Fragmentation and IP addressing, IPv4, CIDR notation, Basics of IP support protocols (ARP, DHCP, ICMP), Network Address Translation (NAT);
Transport layer: flow control and congestion control, UDP, TCP, sockets;
Application layer protocols: DNS, SMTP, HTTP, FTP, Email.
-
Section 11: Basics of Machine Learning and Deep Learning
Backprop (Application of Chain Rule); Linear Regression; Basics of Feedforward Neural Networks, Logistic Regression.
Syllabus for Programming Test
Expressions, Operators (unary, binary, ternary), Conditionals (if, else, nested conditionals), Loops (for, while, do-while, notion of loop invariants, nested loops; notions of precondition and postcondition), Arrays (numerical arrays, strings, searching in arrays), Sorting (such as bubble sort, merge sort).
Functions and return values, arguments, pass by value, the effect of passing pointers (like pass by reference).
**Please note that the Programming test will be conducted in C or Python language.
Sample Questions
Good Resources:
-
Discrete Mathematics by Kenneth Rosen
-
-
-
-
-
Computer Organization and Design: The Hardware/Software Interface by David A. Patterson and John L. Hennessy
-
Computer Architecture: A Quantitative Approach by Hennessy and Patterson
-
-
Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau
-
Modern Operating Systems by Andrew S. Tanenbaum and Herbert Bos
-
Computer Networks by Andrew S. Tanenbaum
-
Compiler Design: Principles, Techniques and Tools by AV Aho, MS Lam, R Sethi and JD Ullman
-
Database System Concepts and A Silberschatz, H Korth and S Sudarshan
**Please note that few scribed notes have been provided for reference. However, these notes are merely indicative of the topics and not to be treated as the sole or even recommended sources for these topics. Students are advised to refer to more elaborate treatments of these topics from textbooks as well.
