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
Basic counting techniques (permutation and combination), pigeon-hole principle, simple recurrence relations, generating functions,
principle of inclusion and exclusion (set cardinality related problems)
Graphs, Directed Graphs, Trees, Connectivity, Cycles, Paths, Hamiltonian and Eulerian cycles, subgraphs, cliques, graph coloring,
Modular Arithmetic, Fermatís Little Theorem, principles of RSA (discrete logarithm problem, primality, integer factorization)
Basic Number Theory:
propositional logic, tautologies, axiom systems, deduction, soundness and completeness, quantification
Simple Group theory -- groups, subgroups, cosets, Lagrangeís theorem, fields, finite fields
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.)
Data Structures and Algorithms:
P vs. NP, NP-Completeness, simple polynomial time reductions, Turing machines, undecidability.
Computability and Complexity:
Group 2: Systems List
Instruction Set architecture, pipelined implementation of instruction set architecture, caches, cache organization, cache replacement,
virtual memory, demand paging, page replacement
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.
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)
Lexical analysis (Deterministic Finite State Automata), Parsing (LALR, LL(1)), peephole optimization, code motion.
Basic SQL queries, relations and relational database
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
vector spaces, dot products and their properties, orthogonality, norms and their properties, Cauchy-Schwartz inequality, hyperplanes,
halfspaces, balls, ellipsoids.
determinants, eigenvalues-eigenvectors, matrix norms (Frobenius, spectral).
linear combination of vectors (convex combination, conic combination, affine combination), notion of gradient for multivariate functions,
convex sets and convex functions (definitions only).
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.
- Iterators, loops, nesting
- Memoization techniques
- Encapsulation primitives (structures, classes - depending on language)
- Threads, Mutex, semaphores
- Proficiency in programming in general