Information on the M.Tech/MS/PhD admission Test

Following are 3 groups of topics. In the admissions test, each candidate will be asked to answer questions from at least 2 groups of topics. Candidates who want to work in theoretical computer science must choose Group 1, candidates interested to work in Systems/Networks/Cyber Security must choose Group 2, and candidates interested in data mining, machine learning and data sciences must choose Group 3. Other group(s) can be chosen freely.

Group 1: Theory List

1. Discrete Mathematics:

Basic counting techniques (permutation and combination), pigeon-hole principle, simple recurrence relations, generating functions, principle of inclusion and exclusion (set cardinality related problems)

2. Graph Theory:

Graphs, Directed Graphs, Trees, Connectivity, Cycles, Paths, Hamiltonian and Eulerian cycles, subgraphs, cliques, graph coloring, planarity

3. Basic Number Theory:

Modular Arithmetic, Fermat’s Little Theorem, principles of RSA (discrete logarithm problem, primality, integer factorization)

4. Logic:

propositional logic, tautologies, axiom systems, deduction, soundness and completeness, quantification

5. Algebra:

Simple Group theory -- groups, subgroups, cosets, Lagrange’s theorem, fields, finite fields

6. Data Structures and Algorithms:

Elementary data structures -- arrays, lists, queues, stacks, and their applications, algorithms for various manipulations of these data structures (sort, search, insert, delete, computing size), basic paradigms of designing algorithms (greedy algorithms, divide-and-conquer approaches, dynamic programming), analyzing time and space complexity of algorithms (O(n) vs O(logn) vs. O(nlogn) vs. O(n^2) etc.)

7. Computability and Complexity:

P vs. NP, NP-Completeness, simple polynomial time reductions, Turing machines, undecidability.

Group 2: Systems List

1. Architecture :

Instruction Set architecture, pipelined implementation of instruction set architecture, caches, cache organization, cache replacement, virtual memory, demand paging, page replacement

2. Operating System:

Unix/Linux operating system structure, processes, threads, process scheduling, concurrent processes and threads, virtual memory management, unix/linux process memory layout (memory segmentation), program stack, and heap and their roles in program run-time, file system permissions, basic unix/linux commands, system calls, kernel vs. user space programs, shared libraries (static vs. dynamically linked). Familiarity with virtual machines, cloud based computing.

3. Networking:

OSI seven layer reference model, TCP/IP protocol stack, division of functionalities in various layers, basic functionalities of TCP and IP, DNS, some protocols (OSPF, BGP, ARP)

4. Compilers:

Lexical analysis (Deterministic Finite State Automata), Parsing (LALR, LL(1)), peephole optimization, code motion.

5. Databases:

Basic SQL queries, relations and relational database

6. Programming:

Good knowledge of C or C++ or Java, client/server systems, simple socket based programming, knowledge of GDB or any debugging tool. Web: http vs. https, cookies, functionalities of web client (browser) vs. web servers

Some good resources for studying:

• Computer Organization and Design, Fourth Edition (or any edition) : The Hardware/Software Interface (The Morgan Kaufmann Series in Computer Architecture and Design) 4th Edition by David A. Patterson and John L. Hennessy.

• Modern Operating Systems (4th Edition): Andrew S. Tanenbaum, Herbert Bos (any Edition)

• Computer Networks, Andrew S. Tanenbaum, 4th Edition (or any edition), Prentice Hall.

Group 3: Statistics and Data Sciences

1. Linear Algebra:

vector spaces, dot products and their properties, orthogonality, norms and their properties, Cauchy-Schwartz inequality, hyperplanes, halfspaces, balls, ellipsoids.

2. Matrix Algebra:

determinants, eigenvalues-eigenvectors, matrix norms (Frobenius, spectral).

3. Convex Analysis:

linear combination of vectors (convex combination, conic combination, affine combination), notion of gradient for multivariate functions, convex sets and convex functions (definitions only).

4. Probability theory:

event spaces and their properties, probability measure, cumulative distribution, random variables, marginal and joint distributions, expectation, variance, independence of events and random variables, linearity of expectation. Statistics: distributions and their properties (Bernoulli, Binomial, Multinomial, Poisson, Gaussian).

Some good resources for studying:

The following scribed notes cover 1), 3), 4), 5) in a succinct manner with examples. 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.

1. http://www.cse.iitk.ac.in/users/purushot/courses/olo/2015-16-w/material/lec2.pdf
2. http://www.cse.iitk.ac.in/users/purushot/courses/olo/2015-16-w/material/lec3.pdf
3. http://www.cse.iitk.ac.in/users/piyush/courses/pml_winter16/slides_lec2.pdf

Programming List

1. Iterators, loops, nesting
2. Recursion
3. Memoization techniques
4. Encapsulation primitives (structures, classes - depending on language)
5. Threads, Mutex, semaphores
6. Proficiency in programming in general