# Syllabus for written exam

The admission process involves online Moodle-based (MCQ) examination in the Institute. The syllabus for the examination is presented below,

Probability and Random Variables: Axioms of probability, random variable (continuous and discrete), probability density (mass) function, probability distribution function, joint probability, conditional probability, Bayes theorem, functions of random variables, expectation of a function of random variables, Markov chain, Random Process (discrete and continuous), Stationarity, power spectral density

Linear Algebra: Vector Space, Linear Independence of Vectors, Basis, Linear Transformation, Four fundamental Subspaces associated with a linear transformation, Rank of a matrix, determinant of a matrix, Rank Nullity theorem, Eigen value and Eigen Vector, Similarity transformation and change of basis, Singular Value Decomposition, Solving a system of linear equations

Discrete Mathematics : Set, function, relation, cardinality of sets, countable and uncountable sets, injective and surjective functions, principle of mathematical induction (weak and strong induction), well ordering principle, equivalence relation, partially ordered sets, Hasse diagram, Lattice, algebra using join and meet operations, Boolean lattice, morphism (homo/ iso), relations as graphs, directed-undirected graphs, Hamiltonian path/ circuit, max flow - min cut, finite groups, subgroups and Lagrange’s theorem, order of an element, generator of a group, product of groups, normal subgroup, finite fields, rings, polynomials, First order logic, quantifiers, deductive reasoning, rules of inference, counting with polynomials and finite difference methods for solving recurrence.

Computer Programming: INTRODUCTION TO PROGRAMMING: Programming methods, paradigms, problem solving techniques, algorithm development, flow charts. LINUX ENVIRONMENT: Editor, compiler, debugger. BASICS OF PROCEDURAL PROGRAMMING: Constants, variables, expressions, operators, assignment, basic input and output, built-in functions, program debugging. VARIABLES AND OPERATORS: Basic data types, precedence and order of evaluation, pointers, memory allocation of variables. CONTROL STRUCTURES: Selection statements, iteration statements. FUNCTIONS AND PROGRAM STRUCTURE: Return values, actual and formal parameters, parameter passing: call by value versus call by reference, external variables, scope rules, header files, and recursion. ARRAYS: Character arrays, one and two dimensional arrays; pointer arrays, command-line arguments. I/O: ASCII data files, file pointers, end-of-file. BASIC DATA STRUCTURES: Structures, defining new types, enumerations, dynamic memory allocation, dynamic arrays, linked lists and other pointer-based structures.

Data Structures and Algorithms: Representation of data on a computer, data types & array and linked list representations ways of representing programs and associated data on computers, Algorithms Foundations: Asymptotic notation, Divide and Conquer Techniques, Solving Recurrences, Probabilistic Analysis and Randomized Algorithms Sorting and Order Statistics: Heapsort, Quicksort, Sorting in Linear Time, Median Order Statistics, DICTIONARY OPERATIONS: Find, max, min, successor, predecessor (query operations); insert, delete (modify operations) LIST DATA: Stacks, queues, variants implementation using arrays and linked lists SORTING: Comparison based sorting algorithms, other sorting algorithms, lower bounds for comparison-based sorting algorithms best-case, worst-case and average-case running times; quicksort, heap Sort, insertion sort, bubble sort etc. ORDER STATISTICS: Maximum and minimum elements of a set, Finding median, searching for an element of a given rank, finding the rank of a given element, ranks of a subset of elements, maintaining rank information for a dynamic set. TREES: heaps, Binary search trees (BST), heights of BST, BALANCED BSTs: Red Black trees, AVL Trees, 2,3,4-trees, B Trees, GRAPHS: Representation using adjacency matrices and adjacency lists, Graph searching algorithms BFS and DFS. Advanced Design and Analysis Techniques: Dynamic Programming, Greedy Algorithms and Amortized Analysis Graph Algorithms: Depth First search, Breadth First Search, Bi-connectivity and Strong Connectivity, Topological Sort, Minimum Spanning Trees, Shortest Paths and Maximum Flow, String Matching: Rabin-Karp and Knuth-Morris-Pratt’s string matching algorithms

Operating Systems: Introduction: overview and history, multiprogramming, functions of an OS, device drivers, I/O interrupts, and system call interface. Process management: the process abstraction, process states, implementing processes (PCB), CPU scheduling algorithms, real-time scheduling, inter-process communication, threads. Resource allocation: classical synchronization problems; synchronization primitives; semaphores; monitors; Deadlocks, deadlock avoidance. Virtual memory management: segmentation, demand paging, hardware support, page fault handling; page replacement algorithms; shared memory. Files systems: logical disks, file organization, buffer cache, file descriptor, directory structure, blocks and fragments, directory tree, inodes, implementation of file system, file protection and access control.

Computer Networks: Introduction: Overview of an internet, internet as a service, internet architecture, circuit switching, packet switching, network performance metrics (delay, packet loss and throughput), layered approach (TCP/IP and OSI models), Link layer: multiple access protocols (channel partitioning protocols, random access protocols and CSMA protocols), Ethernet – IEEE 802.3, Token ring – IEEE 802.5, WiFi – IEEE 802.11, reliable link layer protocols (stop and wait, sliding window protocols), switches and bridges. Network layer: IP addressing: IPv4, IPv6 and ICMP header formats; intradomain routing: distance vector and link state routing protocols; interdomain routing: BGP; routing for multicasting and broadcasting. Transport layer: principles of reliable data transfer; connection oriented transport: TCP connection establishment, TCP timeout estimation, TCP RTT estimation, TCP congestion control; connectionless transport: UDP. Application layer: network applications, hypertext transfer protocol, domain name system, simple mail transfer protocol, socket interface, client-server programming.

Digital Design: Introduction to Digital Design, Number Systems & Codes, Boolean Algebra and Minimization Techniques, Digital CMOS Logic, Combinatorial Circuits & Systems, Sequential Circuits & Systems, Finite State Machines.

Signals and Systems: Linear time invariant (LTI) systems: Discrete and continuous, Fourier representation of periodic signals, Fourier Transform of aperiodic signals, Laplace and z-transform, Linear Feedback Systems.

Digital Signal Processing: Transform analysis of LTI systems, Structures for Discrete Time systems, FIR Filter Design Techniques, The Discrete Fourier Transform and Computational Aspects