Course Code: CS700
Course Name: Comprehensive Exam
Prerequisites:

#### General points:

The new comprehensive examination format and syllabi are applicable to all those PhD students who join the program in or after January, 2019. The examination consists of FOUR papers, out of which THREE are common to all and ONE will be on the chosen research domain of a particular candidate.

The common papers are:
1. Discrete mathematics (Mode of examination: written)
2. Data structure and algorithm (Mode of examination: written)
3. Programing (Mode of examination: Lab)

For the fourth research-domain specific paper (mode of examination: written), the following five domains are considered.
1. Machine learning and data mining
2. Man-machine interface
3. Computer architecture and embedded systems
4. Computer networks and distributed systems
5. Theoretical computer science

The pass mark for each subject shall be 40%.
Syllabus:

### Discrete Mathematics (Common for all)

Module 1: Set theory: sets, relations, functions, partial orders, equivalence relations, cardinality, countability; Module 2: Logic: propositional and first-order formulas, equivalence, satisfiability and validity; Module 3: Number theory: divisibility, greatest common divisor, Euclid's algorithm, fundamental theorem of arithmetic, modular arithmetic, arithmetic with a prime and arbitrary modulus; Module 4: Discrete Probability; Module 5: Combinatorics: permutations, combinations, recurrences, generating functions; Module 6: Graph Theory: paths, connectivity, subgraphs, isomorphism, trees, complete graphs, bipartite graphs, matchings, colourability, planarity, digraphs.

### Data Structure and Algorithm (Common for all)

Module 1: Space and time complexity, NP-completeness; Module2: Elementary Data structure: linked lists, arrays, matrices, stacks, queues, binary trees, tree traversals, heaps, disjoint-set data structure; Module 3: Algorithms for sorting and searching: linear search, binary search, insertion-sort, selection sort, bubble sort, quick sort, merge sort, heap sort, shell sort, Analysis of sorting algorithms; lower bound for sorting; Module 4: Search Trees: binary, AVL, B-trees; Hashing: chaining, linear probing, quadratic probing; Module 5: Graph algorithms: DSF, BSF traversal, topological sorting, connectivity, shortest path algorithms, spanning tree;
Modules 6: Design techniques: greedy, divide and conquer, dynamic programming;

### Programming Lab (Common for all)

Basic features of programming (Using C++): data types, variables, operators, expressions, statements, control structures, functions;

Advanced programming features: arrays and pointers, recursion, records (structures), memory management, files, input/output, standard library functions, programming tools, testing and debugging;

Fundamental operations on data: insert, delete, search, traverse and modify; Fundamental data structures: arrays, stacks, queues, linked lists;

Searching and sorting: linear search, binary search, insertion-sort, bubble-sort, selection-sort, radix-sort, counting-sort;

Introduction to object-oriented programming;

### Research domain: Machine Learning and Data Mining

Module 1 (Linear algebra): Vector Spaces, Orthogonality, Eigenvalues and Eigenvectors Module 2 (Multi-variable functions and partial derivatives): Functions of several variables, Limits and Continuity, Partial Derivatives, Differentiability, Linearization, and Differentials, The Chain Rule, Extreme values and saddle point, Lagrangian Multipliers Module 3 (Optimization): Classical Optimization Techniques, Non-linear Programming II: Unconstrained Optimization Techniques Module 4: The concept of random variable.

### Research Domain: Man-Machine Interface

Module 1 (Software engineering): life cycle, DFD, UML and class diagrams, evaluation (basic concepts); User interface fundamentals: usability, usability metrics, interaction paradigms; Module 2 (Empirical research basics): basic statistics (random variables, population and sampling, mean, median, mode, variance, confidence interval), statistical significance testing (t-test, ANOVA) Module 3 (Sensors & Actuators): Interfacing hardware, ADC/DAC, Motors - DC, AC, Steppers, Servos and associated drivers Module 4 (Intelligent Robotics): Mobile & Networked robots, Navigation, Behaviour Based Robotics, Swarm Robotics Module 5 (Nature-inspired Algorithms): Optimization algorithms, Population based algorithms including Evolutionary algorithms, PSO, ACO, Artificial Immune Systems, Artificial Neural Networks, Fuzzy Systems Module 6 (Signal processing): Basic concepts, Speech signals Module 7: Clustering and temporal data modelling techniques.

### Research Domain: Computer Architecture and Embedded Systems

Module 1: Gate level minimization Module 2: Combinational logic Module 3: Synchronous sequential logic Module 4: Registers and counters Module 5: Memory and programmable logic Module 6: Register transfer level Module 7: Arithmetic for computers Module 8: Processor design including pipelining Module 9: Memory hierarchy Module 10: Storage and I/O

### Research Domain: Computer Networks and Distributed Systems

Module 1: Processes and threads, inter-process communication, classical IPC problems, process scheduling algorithms. Module 2: Clock synchronization, logical clocks, mutual exclusion, synchronization primitives and implementation, deadlock detection algorithms. Module 3: Memory management basics, demand paging and virtual memory implementation, page replacement algorithms. Module 4: Basic concepts of distributed systems: client-server and peer-to-peer applications, naming; flat and structured, DNS, HTTP-based systems, basics of caching. Module 5: Principles of reliable data delivery; Flow and congestion control, TCP Module 6: Internetwork addressing, CIDR notation, Routing in Internet: link state and distance vector routing. Module 7: Basics of multiple access control protocols, ALOHA, CSMA/CD and CSMA/CA protocols.

### Research Domain: Theoretical Computer Science

Note: There will be two parts, A and B. Depending on the research area, a candidate needs to clear any one of the two.

#### Part A - Advanced Algorithms

Module 1 (Discrete Mathematics): Proof techniques: elementary logic (propositions, predicates, quantifiers), direct proof, proving the contrapositive, proof by contradiction, proof by cases, constructive proof, proof of existence, proof of uniqueness, well-ordered induction, mathematical induction, proof by counterexample, combinatorial arguments; Sets, relations, functions: cardinality based set classification, countability, element relation based set classification, partial orders, equivalence relations, asymptotic growth of functions; Number theory: divisibility, greatest common divisor, prime numbers, modular arithmetic, linear congruences; Sequences and series: summations, binomial coefficients, setting up recurrence relations, Master theorem, generating functions; Combinatorics: permutations, combinations, pigeonhole principle, principle of inclusion-exclusion, occupancy problems, counting with generating functions; Graph theory: degree sequences, handshaking lemma, bipartite graphs, trees, paths, cycles, connectivity (Whitney's theorem, Whitney's ear de-composition, Menger's theorem), tours (Eulerian tour characterization, Ore's sufficient condition for HAM cycle existence), vertex cover, edge cover, independent set, dominating set, matching (Gallai's theorem, Konig's theorem, Hall's theorem), planar graphs (Euler's formula), coloring (4-colorability of planar graphs, Brook's theorem for vertex coloring, Vizing's theorem for edge coloring); Discrete probability: sample space, events, conditional probability, stochastic independence, random variables, expectation, variance, popular distributions (Bernoulli, binomial, Poisson, geometric, negative binomial, hypergeometric, multinomial), Markov's tail inequality, Chebyshev's tail inequality. Module 2 Data Structures: Elementary data structures: array, linked list, stack, queue, tree, graph, dynamic array; Analysis techniques: worst-case, average-case, expected, amortized; Search trees: binary search tree, B-tree, 2-3-4 tree, red-black tree, AVL tree, splay tree; Priority queues: binary heap, leftist heap, skew heap, binomial heap, Fibonacci heap; Hashing: chaining, universal, perfect, open; Digital search: trie, suffix tree, suffix array, LCP array; Set representation: disjoint-set forest and its analysis with union by rank and path compression. Module 3 (Algorithms): Sorting: binary search, comparison-based (bubble, insertion, merge, quick-sort, heapsort, selection sort), distribution-based (counting, radix, bucket); Selection: tournament trees, selection in expected linear time, selection in worst-case linear time; Design techniques: divide-and-conquer, greedy, dynamic programming, prune and search, local search, incremental, plane sweep; Graph algorithms: breadth-first search, depth-first search, connected components, topological ordering, minimum spanning tree (Prim's, Kruskal's, Reverse Delete), shortest paths (Lawler's, Dijkstra's, Bellman-Ford, Floyd-Warshall, Johnson's,Warshall's), cardinality matching in bipartite graphs, stable matching; Network Flows: Ford-Fulkerson algorithm, max-flow min-cut theorem, Edmonds Karp algorithm, circulations, applications of network flows and minimum cuts; Numerical: Euclid's algorithm for greatest common divisor, modular exponentiation, fast Fourier transform; String matching: Rabin-Karp algorithm, string matching with finite automata, Knuth-Morris-Pratt algorithm; Worst-case lower bounds: decision trees, adversary arguments, P, NP, coNP, polynomial time reductions; Miscellaneous: formulating linear programs, Las Vegas randomized algorithms (selection, quicksort), Monte Carlo randomized algorithms (global minimum cut, max 3-SAT), introduction to approximation algorithms (vertex cover, traveling salesman problem, set cover).

#### Part B - Automata Theory, Computability and Logic

Module 1 (Automata Theory): Alphabets, languages, grammars; Finite automata: regular languages, regular expressions; Context-free languages: pushdown automata, DCFLs. Module 2 (Computability): Turing machines, recursive and recursively enumerable languages, undecidability, Rice's Theorem, Post Correspondence Problem Module 3 (Logic): Propositional Logic: Syntax, Proof Systems, Semantics, Soundness and completeness, Compactness, Normal Forms, Propositional satisfiability solvers. First Order Logic: Syntax, Proof Systems, Semantics, Soundness and Completeness, Compactness.
Texts:

### Discrete Mathematics (Common for all)

1. Kenneth Rosen, Discrete Mathematics and its Applications, McGrawHill 1999.
2. Mathematics for Computer Science by Eric Lehman, F Thomson Leighton and Albert R Meyer (available online).

### Data Structure and Algorithm (Common for all)

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed, MIT Press, 2009.

### Programming Lab (Common for all)

1. S B Lippman, C++ Primer, 5th Ed., Addison-Wesley, 2013.

### Research domain: Machine Learning and Data Mining

1. D. Poole, Linear Algebra: A Modern Introduction, 2nd Edn., Brooks/Cole, 2005. (Chapters 4-6)
2. G. B. Thomas, Jr. and R. L. Finney, Calculus and Analytic Geometry, 9th Edn., Pearson Education India, 1996. (Chapter 12)
3. S. S. Rao, Engineering Optimization - Theory and Practice, Fourth edition, John Wiley and Sons, 2009. (Chapter 2 & 6)
4. Probability, random variables and stochastic processes Athanasios Papoulis & S. Unnikrishna Pillai, Fourth edition, Tata McGraw-Hill Edition. (Chapter 4)

### Research Domain: Man-Machine Interface

1. Fundamentals of Software Engineering, Rajib Mall, PHI, 2015
2. Designing the User Interface, Ben Shneiderman and Catherine Plaisant, Pearson, 2009 (Chapter 1)
3. Research Methods in HCI, J Lazar, J. H. Feng and H Hochheiser, Wiley, 2010. (Chapter 1-4)
4. Sensors & Actuators - Engineering Systems Instrumentation, 2n Ed. 2016, CRC Press (Taylor & Francis Group)
5. Introduction to AI Robotics, Robin Murphy, 2000, A Bradford Book, MIT Press
6. Mobile Robotics - A Practical Introduction, Ulrich Nehmzow, 2nd Ed., Springer
7. Swarm Intelligence, James Kennedy, Russel C. Eberhart, 2001, Maughan Kaufman Publishers
8. Rabiner and Schafer, Digital Processing of Speech Signals, Pearson Education, 2004.
9. Khalid Sayood, Introduction to Data Compression, Third edition, Morgan Kaufmann Publishers Inc., San Francisco, 2006, ISBN: 9780132136037.
10. Lawrence Rabiner and Biing-Hwang Juang, Fundamentals of Speech Recognition, Pearson Education Signal Processing Series, 2003, ISBN: 978-0130151575.
11. Chin-Hui Lee, Frank K. Soong, Kuldip K. Paliwal, Automatic Speech and Speaker Recognition: Advanced Topics, Kluwer Academic Publishers, 1996, ISBN 978-1-4613-1367-0.

### Research Domain: Computer Architecture and Embedded Systems

1. Digital Design, by Morris Mano
2. Computer Organization and Design: The Hardware/Software Interface, 5th Ed. MIPS, Hennessy and Patterson

### Research Domain: Computer Networks and Distributed Systems

1. A.S. Tanenbaum and H. Bos, “Modern Operating Systems”, 4th Edition, Pearson India, 2016.
2. J. F. Kurose and K. W. Ross, “Computer Networking: A Top Down Approach, 6th Edition, Pearson India, 2017.
3. S. Tanenbaum and M. van Steen, “Distributed Systems: Principles and Paradigms”, 2nd Edition, Pearson India, 2015.

### Research Domain: Theoretical Computer Science

#### Part A - Advanced Algorithms

##### Module 1 (Discrete Mathematics)
1. Discrete Mathematics and its Applications by Kenneth Rosen, Seventh (Indian) Edition, McGraw Hill Education.
2. Mathematics for Computer Science by Eric Lehman, F Thomson Leighton, Albert R Meyer.
##### Module 2 (Data Structures)
1. Introduction to Algorithms by Thomas Cormen, Charles E. Leiserson, Ronald L. Riverst, and Clifford Stein, Third Edition, PHI Learning Pvt. Ltd.
2. Fundamentals of Data Structures in C by Horowitz, Sahni, and Anderson-Freed, Second Edition, Universities Press.
##### Module 3 (Algorithms)
1. Introduction to Algorithms by Thomas Cormen, Charles E. Leiserson, Ronald L. Riverst, and Clifford Stein, Third Edition, PHI Learning Pvt. Ltd.
2. Algorithm Design by Jon Kleinberg and Eva Tardos, First Edition, Pearson Education India.
3. Fundamentals of Data Structures in C by Horowitz, Sahni, and Anderson-Freed, Second Edition, Universities Press.

### Part B - Automata Theory, Computability and Logic

1. J. E. Hopcroft, R. Motwani and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, 2nd Ed., Pearson Education, 2000.
2. M. Ben-Ari, Mathematical Logic for Computer Science, Springer 2012.
References:

### Research Domain: Theoretical Computer Science

#### Part A - Advanced Algorithms

##### Module 1 (Discrete Mathematics)
1. Elementary Number Theory by David Burton, Seventh Edition, Mc-Graw Hill Education.
2. Graph Theory by Reinhard Diestel, Fifth Edition, Springer.
3. An Introduction to Probability Vol 1, William Feller, Third Edition, Wiley.