Department of Computer Science & Engineering, IIT Guwahati

Ph.D Admission( July 2020): Syllabus


  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. Computer Networks: 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, IPv4and IPv6, Interconnection

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