## Syllabus for MS Comprehensive Viva-voce

The MS comprehensive viva-voce will test the student's competency in:

The six basic areas tested and their syllabus are given below. The syllabus for the subjects taken by the students will follow the published syllabus of the individual subjects.

- Six basic areas of CSE, and
- Specific subjects the student has undertaken during his/her studies for the MS degree.

## A. Discrete Mathematics

Proof Techniques- Direct proofs, proof by contraposition, proof by contradiction, proof by cases, existence proofs, Proofs by mathematical induction.
Sets- Subsets, set equality, set operations: complement, union, intersection, set difference, Powersets.
Functions- injective, surjective, bijective functions, Composition of functions, Inverse of a function.
Relations- Relations and their properties, Equivalence relations, Partial Orderings.
Combinatorics- Counting, Principle of inclusion-exclusion, Pigeonhole principle, Permutations and Combinations.
Recurrence Relations- Linear recurrence relations, divide and conquer recurrence relations.
Probability- Discrete probability, Probability of combinations of events, Conditional probability, Independence, Bayes Theorem, Expected values.
Graph Theory- Basic terminologies, degree, connected components, trees.
## B. Algorithms

Introduction- The order notations, worst-case and average-case performance of algorithms, notions of lower bounds on problem complexity and optimality of algorithms.
Data structures- Stacks, queues, trees, graphs, binary search trees, height balancing -- red-black trees, heaps and priority queues, hash tables.
Searching and sorting- Linear and binary search. Bubble sort, insertion sort, selection sort, merge sort, quick sort, heap sort, counting sort.
Algorithm design techniques- Divide-and-conquer, greedy and dynamic-programming algorithms. Lower bounds and optimal algorithms.
Graph algorithms- Preorder, inorder and postorder traversal of trees, BFS and DFS, topological sort. Minimum spanning trees (Kruskal's and Prim's algorithms), Shortest path (Dijkstra and Floyd-Warshal) algorithms.
NP-completeness- The complexity classes P and NP, polynomial-time reductions, NP-Hard and NP-Complete problems.
## C. Formal Languages and Automata Theory

Introduction- Alphabets, Strings, Languages, Grammars and Recognizers, Decision problems over languages.
Regular Languages and Finite Automata- Regular languages (RLs), Regular Grammars and Regular Expressions, DFAs, NFAs and their equivalence with Regular Grammars and Regular Expressions, Converting NFA to DFA, Proving Languages not to be Regular -- pumping lemma for RLs, Closure of RLs under Boolean operations.
Context-Free Languages and Pushdown Automata- Context-free languages and grammars, Parse trees, Ambiguities in Grammars and Languages, Pushdown Automata (PDAs).
Turing Machines- Basic machine, Universal Turing machine and notions of undecidability.
## D. Computer Organization and Architecture

Instruction set architecture- Instruction types, Instruction formats, addressing modes.
Arithmetic- Representation of fixed and floating-point numbers, 2's complement arithmetic.
Control unit- Organization of a CPU, control and data paths, micro-operations, register-transfer level specifications.
Memory system- Typical signal lines in a ROM and RAM, building memory subsystems using smaller modules. Concept of memory hierarchy, cache memory, cache performance, cache-main memory mapping.
Input-output systems- Programmed I/O, Interrupt-driven I/O, polling and vectored interrupt, basic concept of DMA transfer.
Pipelining- Basic concepts of pipeline.
## E. Operating Systems

Basic components of an operating systemProcesses and Interprocess communication- Basic concepts, process state transition diagram, context switch, process synchronization problem, semaphores - definition and implementation.
Process scheduling- Preemptive and non-preemptive scheduling, FCFS, SJF and round-robin scheduling.
Memory management- Logical and physical addresses, paging and virtual memory, page table, TLB.
Hardware requirements- Privileged mode and privileged instructions, handling of hardware and software interrupts.
## F. Programming

C programming- Datatypes, variables, assignment statements, iteration and control statements, arrays, structures, functions and recursion, pointers.
User-defined data types- Stack, queue, binary tree, binary search tree.
Representation of graphs