GATE Computer Science and Information Technology (CS) Syllabus

Computer Science and Information Technology (CS) syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Computer Science and Information Technology (CS) in GATE, not a summary of it.

1. 1

   Digital Logic and Computer Architecture

   4 topics

   • Boolean Algebra and Logic Gates
     • Minimization using K-maps
     • Combinational circuits
   • Sequential Circuits
     • Flip-flops and registers
     • Counters and state machines
   • Number Representation
     • Fixed and floating point arithmetic
   • Processor Organization
     • Instruction pipelining and hazards
     • Memory hierarchy and cache
     • I/O and interrupts
2. 2

   Programming, Data Structures and Algorithms

   4 topics

   • Programming in C
     • Recursion and pointers
     • Parameter passing and scope
   • Data Structures
     • Arrays, stacks, queues and linked lists
     • Trees, BSTs and heaps
     • Graphs and hashing
   • Algorithm Design and Analysis
     • Asymptotic complexity and recurrences
     • Greedy, divide-and-conquer and dynamic programming
   • Searching, Sorting and Graph Algorithms
     • Sorting algorithms and lower bounds
     • BFS, DFS, shortest paths and MST
3. 3

   Theory of Computation and Compiler Design

   4 topics

   • Regular Languages and Finite Automata
     • DFA, NFA and regular expressions
     • Pumping lemma for regular languages
   • Context-Free Languages and Pushdown Automata
   • Turing Machines and Undecidability
     • Decidability and recursive enumerability
   • Compiler Phases
     • Lexical and syntax analysis
     • Syntax-directed translation
     • Intermediate code and optimization
4. 4

   Operating Systems and Databases

   5 topics

   • Process and Thread Management
     • CPU scheduling
     • Synchronization and deadlocks
   • Memory Management
     • Paging, segmentation and virtual memory
   • File Systems and Disk Scheduling
   • Relational Model and SQL
     • Relational algebra and SQL queries
     • Integrity constraints
   • Database Design and Transactions
     • Normalization and functional dependencies
     • Transactions and concurrency control
     • File organization and indexing (B and B+ trees)
5. 5

   Computer Networks

   5 topics

   • Network Models and Layers
     • OSI and TCP/IP reference models
   • Data Link and MAC Layer
     • Error detection and flow control
     • Switching and Ethernet
   • Network Layer
     • IPv4 addressing and subnetting
     • Routing algorithms
   • Transport and Application Layer
     • TCP and UDP
     • DNS, HTTP, SMTP and FTP
   • Network Security Basics
     • Symmetric and public-key cryptography

Computer Science and Information Technology (CS) flashcards for GATE

20 of 53 cards from the Computer Science and Information Technology (CS) deck — real questions with worked answers.

1. State De Morgan's theorems in Boolean algebra.

   $\overline{A + B} = \bar{A} \cdot \bar{B}$ and $\overline{A \cdot B} = \bar{A} + \bar{B}$. The complement of a sum equals the product of complements, and the complement of a product equals the sum of complements.

2. What is the difference between minterms and maxterms?

   A minterm is a product (AND) term in which every variable appears once (complemented or not) and equals $1$ for exactly one input combination. A maxterm is a sum (OR) term that equals $0$ for exactly one combination. SOP uses minterms; POS uses maxterms.

3. Why is the XOR gate called the 'inequality detector,' and what is its Boolean expression?

   XOR outputs $1$ only when its inputs differ. For two inputs: $A \oplus B = A\bar{B} + \bar{A}B$. It outputs $0$ when inputs are equal.

4. List the basic Boolean identities for absorption and complementarity.

   Absorption: $A + AB = A$ and $A(A+B) = A$. Complement: $A + \bar{A} = 1$ and $A \cdot \bar{A} = 0$. Identity: $A + 0 = A$, $A \cdot 1 = A$.

5. In a Karnaugh map, what are the two rules for forming valid groups?

   Groups must contain a power of two cells ($1, 2, 4, 8, \dots$) and must be rectangular. Adjacent cells differ by exactly one variable (Gray-code ordering), wrapping around edges/corners is allowed, and larger groups eliminate more variables.

6. What is a 'don't care' condition in K-map minimization and how is it used?

   A don't-care (marked $X$ or $d$) is an input combination that never occurs or whose output is irrelevant. It can be treated as either $0$ or $1$—whichever yields larger groupings and thus a simpler minimized expression.

7. How many variables does a group of $2^k$ cells eliminate in a K-map?

   A group of $2^k$ adjacent cells eliminates $k$ variables, leaving the variables that remain constant across the group in the resulting product term.

8. Define prime implicant and essential prime implicant.

   A prime implicant is an implicant (group of 1s) that cannot be combined into a larger group. An essential prime implicant is a prime implicant that covers at least one minterm not covered by any other prime implicant, so it must appear in the minimal cover.

9. What distinguishes a combinational circuit from a sequential circuit?

   A combinational circuit's output depends only on the current inputs (no memory), e.g., adders, multiplexers. A sequential circuit's output depends on current inputs and stored state (it has memory via flip-flops), e.g., counters, registers.

10. Give the sum and carry expressions for a full adder.

    For inputs $A$, $B$, and carry-in $C_{in}$: $\text{Sum} = A \oplus B \oplus C_{in}$ and $\text{Carry} = AB + C_{in}(A \oplus B)$.

11. What does an $n$-to-$2^n$ decoder do, and a $2^n$-to-$1$ multiplexer?

    An $n$-to-$2^n$ decoder activates exactly one of $2^n$ outputs based on the $n$-bit input. A $2^n$-to-$1$ multiplexer selects one of $2^n$ data inputs using $n$ select lines and routes it to a single output.

12. How many select lines are needed for an $8\text{-to-}1$ multiplexer, and why?

    Three select lines, because $2^3 = 8$. In general, a $2^n\text{-to-}1$ MUX needs $n$ select lines to address all inputs.

13. What is the characteristic (excitation) equation of an SR latch, and its forbidden condition?

    Next state $Q_{next} = S + \bar{R}Q$, with the constraint $SR = 0$. The condition $S = R = 1$ is forbidden because it produces an indeterminate/invalid output.

14. Give the characteristic equation of a JK flip-flop.

    $Q_{next} = J\bar{Q} + \bar{K}Q$. When $J=K=1$ the output toggles; $J=K=0$ holds; $J=1,K=0$ sets; $J=0,K=1$ resets.

15. What is the characteristic equation of a D flip-flop and a T flip-flop?

    D flip-flop: $Q_{next} = D$ (output follows input). T flip-flop: $Q_{next} = T \oplus Q$, so $T=1$ toggles and $T=0$ holds the state.

16. Differentiate a latch from a flip-flop.

    A latch is level-triggered (transparent while the enable/clock level is active). A flip-flop is edge-triggered (changes state only on the rising or falling clock edge), making it more suitable for synchronous design.

17. What is the race-around condition in a JK flip-flop and how is it solved?

    When $J=K=1$ and the clock pulse width exceeds the propagation delay, the output toggles multiple times during one pulse. It is solved using a master-slave (or edge-triggered) configuration.

18. Compare SISO, SIPO, PISO, and PIPO shift registers by data movement.

    SISO: serial-in serial-out. SIPO: serial-in parallel-out (serial-to-parallel converter). PISO: parallel-in serial-out (parallel-to-serial converter). PIPO: parallel-in parallel-out (temporary storage).

19. What is the maximum modulus (count) of an $n$-bit binary counter?

    An $n$-bit counter has a maximum modulus of $2^n$, counting from $0$ to $2^n - 1$ before rolling over.

20. How many flip-flops are required to build a mod-$N$ counter?

    The minimum number of flip-flops is $\lceil \log_2 N \rceil$, i.e., the smallest integer $n$ such that $2^n \geq N$.

See more Computer Science and Information Technology (CS) flashcards →

Planning Computer Science and Information Technology (CS) for GATE

Computer Science and Information Technology (CS) (GATE) FAQ