Department of CSE, IIT Guwahati 
M. Tech (Non-Regular/IIT graduates) 

Admission (July 2020): Syllabus for the Written Test

Discrete Mathematics: Propositional Logic; Probability -Conditional Probability; Mean, Median, Mode and Standard Deviation;

Random Variables; Distributions-Uniform, Normal, Exponential, Poisson, Binomial. Set Theory -Sets; Relations; Functions; Groups;

Partial Orders; Lattice; Boolean algebra. Combinatorics -Permutations; Combinations; Counting; Summation; Generating functions;

Recurrence relations; Graph Theory -Connectivity; Spanning trees; Cut vertices and edges; Covering; Matching; Independent sets;

Coloring; Planarity; Isomorphism.

Programming and Data Structures: Programming in C; Structures, Pointers, Functions, Recursion, Parameter passing, Scope,

Binding; Abstract data types, Arrays, Stacks, Queues, Linked Lists, Trees, Binary search trees, Binary heaps, Graphs.

Algorithms: Analysis of algorithms, Asymptotic notation, Notions of space and time complexity, Worst and average case analysis;

Design: Greedy approach, Dynamic programming, Divide-and-conquer; Tree and graph traversals, Connected components, Spanning

trees, Shortest paths; Hashing, Sorting, Searching. Asymptotic analysis of upper and lower bounds, Basic concepts of complexity

classes P, NP, NP-hard, NP-complete.

Formal Languages and Automata Theory: Alphabets, languages,grammars; Finite automata; Regular languages, Regular expressions;

Context-free languages: Pushdown automata, Context sensitive languages: Linear bounded automata; Turing machines: recursively

enumerable languages; Undecidability; Operations on formal languages and their properties; Chomsky hierarchy; Decision questions

on languages.

Computer Organization and Architecture: Logic functions, Minimization, Combinational and sequential circuits; Representation

of fixed and floating point numbers; Computer arithmetic. Machine instructions and addressing modes, RISC and CISC paradigms,

Instruction pipelining; Memory interface; Memory hierarchy -Cache memory, main memory, secondary storage; I/O transfer techniques:

Program controlled, Interrupt controlled, DMA transfer.

Operating Systems: Processes, Threads, Inter-process communication, Concurrency: Mutual exclusion; Synchronization; Semaphores,

Deadlock management, CPU scheduling, Memory Management: Allocation, Protection, Paging, Segmentation; Virtual Memory concepts.

File Management, File Systems: Allocation, Free space management, Directory management, I/O Management: Device drivers, Disk

scheduling algorithms.

Computer Network: Basics of digital communications, Guided and unguided media, ISO/OSI stack, LAN technologies (Ethernet,

Token ring), Flow and error control techniques, Routing algorithms, Congestion control, TCP/UDP and sockets, IPv4 and IPv6,

Interconnection devices -Hubs, Switches, Gateways, and Routers; Application layer protocols.