Gate Computer Science 1

Verbal Ability!
Syllabus - English grammar, sentence completion, verbal analogies, word groups,
instructions, critical reasoning and verbal deduction.

Types of Problems came in Previous Years:

1. Antonym, Synonym [English grammar part],

2. Given a sentence and i have to fill in with appropriate word [Sentence completion part ]

3. Same or different pairs of words [Verbal Analogy part ] ,

4. Analogy of words, Ordering of words/ ordering of sentences, Odd one out from a group of
words [ Word groups part ] ,

5. Summary or Logical meaning from a passage /sentence, Given a problem sequence you
have to satisfy a condition [instructions , critical reasoning part ]

6. A sentence is given in English and you have to select the logical meaning of this sentence
in a single word [ Verbal deduction part ]

Now it is better to practice Problems on these Types from previous Year Gate papers starting
from 2010 (this year Apti is introduced) .

GRE Barron book (lots of examples are there in this book for each of these types ) .

Numerical Ability!
Syllabus: Numerical computation, numerical estimation, numerical reasoning and data
interpretation.

Types of problems need to practice:

Problems on time and work, distance, Data Interpretation ( imp) , Number system,
percentages, clocks, coding and decoding, Venn Diagram, cubes, blood relation, Directions,
Number odd man out, Boats and pipes etc.

Book:

1. Quantitative Reasoning –By R.S. Agarwal

 Gate Computer Science 2

C Programming!
Syllabus : ( As per old syllabus)

Programming in C; Functions, Recursion, Parameter passing, Scope, Binding.

1 What Books To Read:
Book Name:
1 K N King : 2nd edition
Chapter - 1 to 14 , chapter 17 and 18
chapter 8, 9 , 10, 11, 12 are very important for gate exam purpose .
2 Dennis M Ritchie : 2nd edition
Chapter 1 to 6

Video: NPTEL MOOC IITK CS 101- programming in C

2. Important Topics for that subject to read along with Chapter Subparts :

Function K N King Chapter - 9 : 9.1, 9.2 / Dennis Ritchie : chapter 4 - 4.1, 4.2
Recursion K N King Chapter - 9.6 / Dennis Ritchie : chapter 4 -4.10
Parameter Passing K N King Chapter - 9.3 , 9.4, 9.5 / Dennis Ritchie : chapter 1- 1.8
Scope K N King Chapter - 10: 10.1 to 10.4 / Dennis Ritchie : chapter 4 -4.3 to 4.7
Binding K N King Chapter - 10.5 / Dennis Ritchie : chapter 4 - 4.8 , 4.9
Pointer K N King Chapter - 11: 11.1 to 11.5 , Chapter 17 : 17.1 to 17.8 / Dennis Ritchie :
chapter 5 - 5.1 to 5.5
Array - 1D array chapter 8 - 8.1 , 2 D Array 8.2 , 8.3
Pointers and Arrays K N King Chapter - 12: 12.1 to 12.5 / Dennis Ritchie : chapter 5 -
5.6 to 5.9
3 . Types of problems from where questions came in previous years :
C programming Questions are logical and mostly based on finding outputs which contain
some pointers, static variables, arrays, strings, functions etc.

Important Topics are:

 Pointer
 Array- 1D and 2D Array
 Array- row and column major order
 memory location sums
 1D, 2D array location sums
 moving no of memory locations based on given program
 pointers and arrays
 switch statement
 Gate Computer Science 3

 pass-by-value, pass-by-pointer/ reference

 global initialization
 typecasting
 short circuit rule
 array to pointer conversion on function call
 Register variable
 String literals
 Loop invariant
 scope : - static and dynamic scoping,
 Binding,
 Function ,
 Recursion,
 parameter passing .

Note:
A small NOTE for GATE Exam purpose ---> "C" is included in GATE syllabus as one
language for checking programming compatibility- not to see if a student is master in C. For
the same reason, GATE COMMITTEE don't ask questions related to C library functions or
anything too specific to C. So, GATE C portions are always from a small subset of C.
The best way to practice C programming question is take questions from previous year Gate
papers and try to solve them and try to do programming on Compiler.
It will increase your skills and accuracy.
 Gate Computer Science 4

Data Structure
Syllabus:
Arrays, stacks, queues, linked lists, trees, binary search trees, binary heaps, graphs.

Searching, sorting, hashing. Asymptotic worst case time and space complexity. Algorithm
design techniques: greedy, dynamic programming and divide-and-conquer. Graph search,
Minimum spanning trees, shortest paths.

1. What Books to read :

Book Name : Data Structures Using C - Aaron M. Tenenbaum [ Chapter 1 to 8, 9.3 ]

ch 1 , ch 2 completely
from chapter 3 - 3.1, 3.2, 3.3 recursion
chapter 4 - 4.1 to 4.5 queue and stacks
chapter 5- 5.1 to 5.5 tree
chapter 6 completely sorting 6.1 to 6.5
chapter 7 completely - 7.1 to 7.4 searching
chapter 8 completely - 8.1 to 8.4 graph and their applications
and from chapter 9-9.3 only to read dynamic memory management

2 Data Structures and Algorithm Analysis in C by Mark Allen Weiss [ Chapter - 2, 3 , 4, 5,

6, 7, 9, 10 ]

3 Fundamentals of Data Structures by Ellis Horowitz and Sartaj Sahni [ Chapter - 1 , 2, 3 ,

4, 5, 6, 7, 9 ]

4 Thomas H Cormen et.al ( covers both Data Structure and Algorithms ) - Chapter
1,2,3,4[excluding 4.4],6,7[excluding 7.3],8,10,11[excluding
11.5],12[excluding 12.4], 15.1, 15.2,15.4 , 16.1, 16.2, 16.3 , 18, 22,23, 24[excluding 24.4
and 24.5] , 25 .

Nptel web course by IIT G : http://nptel.ac.in/courses/106103069/32

2. From where to read ? Topics for that subject to read along with Chapter Subparts :

Data Structure

1 Array : Accessing Array using Pointers , Representation: 1 D Array and 2D Array

Mark Allen Weiss chapter 3.2.1 / Horowitz chapter 2
 Gate Computer Science 5

2 Stacks : Operations and Applications Mark Allen Weiss chapter 3 - 3.3 / CLRS 10.1 /
Horowitz chapter 3 / Tenenbaum Chapter 2

3 Queues : Operations and Applications , Priority queue, Circular Queues:

Operations and Applications
Mark Allen Weiss chapter 3 - 3.4 / CLRS 10.1 / Horowitz chapter 3 / Tenenbaum -
4.1 to 4.5

4 Linked lists : Singly Linked List , Doubly Linked List, Circular Linked List Operation
– Creations, insertion and Deletion of Nodes from a List Linked Implemented of ----->
Stacks , Queues , Priority queue ,Circular Lists,Doubly Linked List

Mark Allen Weiss chapter 3- 3.2 / CLRS 10.2 / Horowitz chapter 4

5 Trees - Binary Trees : 1 Representation: Array & Linked Representation of Binary Tree ,
2 Operations: Insert, Delete , 3 Traversal: Preorder, Inorder, Postorder
Mark Allen Weiss chapter 4 / CLRS 10.4 / Horowitz chapter 5 / Tenenbaum 5.1 to 5.5

6 Binary Search Trees

• AVI-trees : AVL Tree Insertion, Deletion, Rotation -- Mark Allen Weiss chapter 4.4
• B-tree CLRS chapter 18 [ 18.1, 18.2, 18.3]
• External Search
Mark Allen Weiss chapter 4 - 4.3 / CLRS chapter 12.1 to 12.3

7 Binary Heaps : Method and Complexity , Priority Queue

Mark Allen Weiss chapter 6 / CLRS 6.1, 6.2, 6.3, 6.5
8 Graphs : Representation and Traversal .
Representation: Matrix, Adjacency list
Traversal: Depth First Search, Breadth First Search
Mark Allen Weiss chapter 9.1.1 / CLRS chapter 22 / Tenenbaum chapter 8.1 to 8.4 /
Horowitz chapter 6
 Gate Computer Science 6

Algorithms

1 Searching : Binary Search , Selection

CLRS - Linear Search, binary search. Chapter 12 of CLRS 12.1, 12.2, 12.3 / Tenenbaum
7.1 to 7.4

2 Sorting : Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Heap Sort, Quick Sort,
Radix Sort, Bucket Sort
CLRS - Chapter 1, 2, 6.4 , 7 [excluding 7.3] ,8 / Tenenbaum 6.1 to 6.5

3 Table based data Structure : Hashing : Hashing Techniques Direct Addressing , Properties
of hash function, Universal hashing Types of hashing -- a) Chaining b) Open addressing ,
Collision resolution schemes - a)Linear Probing b) Quadratic Probing c) Double Hashing
Demerits associated with linear and quadratic probing(Primary and Secondary Clustering
Problem )

Mark Allen Weiss chapter 5 / CLRS 11.1 to 11.4

4 Asymptotic worst case time and space complexity CLRS - Chapters 3,4. [excluding 4.4]

5 Algorithm design techniques: Greedy - CLRS Chapter 16 - 16.1, 16.2, 16.3 . Dynamic
programming - CLRS Chapter 15 - 15.1, 15.2, 15.3, 15.4 . Divide-and-conquer - CLRS
Covered by merge sort in Chapter 2.

6 Graph search CLRS BFS, DFS - covered in chapter 22- 22.1 to 22.5

7 Minimum spanning trees CLRS Chapter 23. Prim’s and Kruskal’s algorithms 23.1 , 23.2

8 Shortest paths Single Source Shortest Path - CLRS Chapter 24 [excluding 24.4 and 24.5]
, All Pairs Shortest Path - CLRS Chapter 25 [ 25.1, 25.2]
 Gate Computer Science 7

3. Types of problems from where questions came previous years :

Understand Different Problems on Stack, Queue, Link List. Generally they come in a C
program, But you can solve them only if you know the logic.
Properties of Heap. Deletion and insertion of items in the heap.

Practice Tree problems like no of leaf nodes, non leaf nodes, total nodes, height of the tree,
no of full nodes, mirror image, etc.
AVL tree and balancing them on insertion and Deletion.
Binary tree, Binary Search Tree, Inorder, Preorder, Postorder traversal. Spanning Trees,
Minimum Spanning Tree problems.

Finding Complexity : Sometimes direct question comes related to complexity like give
complexity of Heap sort. But mostly you are given a code or question. You need to find best
average case complexity of that problem. So try to find complexity of every algorithm or
program which you practice.
Also understand properties of complexity. Sometimes relation between them is asked.

Searching and Sorting Problems. Difference between Different Techniques and how to apply
them on different real life problems.

Questions on approach of dynamic programming, Divide and Conquer [ Merge Sort ] ,

Greedy [ Huffman code has been asked many times for GATE] and Brute Force.
Practice basic problems like quick sort, merge sort, knapsack problem, matrix chain
multiplication, LCS, Job sequencing, Compressing Mechanism.

Questions come from filling of hash tables with

1. linear probing,
2 . quadratic probing,
3. expected no. of empty slots after x insertions (application of probability),
4. load factor.
5 closed hashing
6. property of a hash function
7 Universal Hashing
 Gate Computer Science 8

Automata
Syllabus:

Regular expressions and finite automata. Context-free grammars and push-down automata.
Regular and contex-free languages, pumping lemma. Turing machines and undecidability.

1. What Books to read :

Book Name:
1 Peter Linz - An Introduction to Formal Languages and Automata : 3rd edition , chapter 1
to 12
2 Daniel I A Cohen - Introduction to Computer Theory , chapter 1 to 31
3 John C Martin - Introduction to Languages and The Theory of Computation: 4th Edition,
chapter - 1 to 9

Video : NPTEL IITK - https://www.youtube.com/playlist?

list=PLbMVogVj5nJSd25WnSU144ZyGmsqjuKr3

Sai Simonson - https://www.youtube.com/playlist?list=PL601FC994BDD963E4

2. What To read : Topics for that subject to read along with Chapter Subparts : ** marked
parts are important for problems
**1 Regular expressions Linz Chapter - 3 - 3.1, 3.2, 3.3 / Cohen - Chapter: 3 , 4 /
Martin - 3.1 to 3.5
**2 finite automata Linz Chapter - 2- 2.1, 2.2, 2.3,2.4 / Cohen - Chapter : 5, 6, 7,
8, 9 / Martin - 2.1 to 2.6
**3 Context-free grammars Linz Chapter - 5 : 5.1 , 5.2, 5.3 , Chapter 6 - 6.1, 6.2 /
Cohen - Chapter : 13 ,14,15,16 / Martin : 4.2
** 4 push-down automata Linz Chapter - 7 : 7.1, 7.2, 7.3 / Cohen - Chapter : 17 and
Chapter : 18 / Martin : 5.1 to 5.5
**5 Regular Language Linz Chapter - 4 : 4.1, 4.2, 4.3 / Cohen - Chapter : 10 , 11,
12 / Martin : 3.1, 4.3
6 contex-free languages Linz Chapter - 8.2/ Cohen - Chapter : 19 , Chapter : 21 , 22, 23
/ Martin 4.1, 4.2, 4.4, 4.5
7 pumping lemma Linz Chapter - 8.1 / Cohen - Chapter : 20 / Martin - 6.1 to 6.3
** 8 Turing machines Linz Chapter - 9 : 9.1 , 9.2, 9.3 , Chapter 10 , chapter 11 / Cohen -
Chapter : 24, 25, 26 , 27 / Martin 7.1 to 7.8 , 8.1 to 8.5
9 undecidability Linz Chapter - 12 : 12.1 to 12.4 / Cohen - Chapter : 28, 29, 30, 31 /
Martin 9.1 to 9.5

3. Types of problems from where questions came previous years:

 Gate Computer Science 9

RE and FA

Finite Automata covers approximately 50% questions from TOC. So give it more time then
others.

• Minimization of finite Automata , Closure Properties of finite automata .

• Finding minimum number of states, NFA to DFA conversion, Finding Regular

Expressions, mealy moore machine .

• Regular Expression identification.

• Construction of finite Automata from regular Expression

• Generation of regular expression from finite Automata

• Equivalence of regular Expression

CFG and PDA

• In Context free grammer practice more on simplification of CFG, pushdown automata,

closure properties etc.

Regular and Context Free Languages

• closure properties of regular language

• Decidability of regular Language

• Whether the given language is regular or not

• Do problems on finding category of any language or grammar.

• Concepts related to expressive power of different languages.

Turing Machine and Undecidability

• Basic problems related to NP-Completeness. Properties of Recursive and Recursive

Enumerable Languages.

• Turing Machine making and expressive power of different type of turing machine. (also
useful for interview ) .
 Gate Computer Science 10

Computer Organization and Architecture

This is your syllabus --
book- mano coa 3rd
zaki 5th
stalling international edition
fundamental of coa by mostafa

1. What to read ? Syllabus to cover for that particular subject .

Syllabus : Machine instructions and addressing modes, ALU and data-path, CPU control
design, Memory hierarchy, I/O interface (Interrupt and DMA mode), Instruction pipelining,
Cache and main memory, Secondary storage.

2. From where to read ? Chapter subparts to read from standard text book.

1 Instruction set architecture 2.4 and 2.5 zaki, / 8.4,8.5 , 5-1 to 5-5 mano 5-3and 5-5 is imp
Instruction types, Instruction formats, addressing modes.

2 Arithmetic 3.2,3.3,3.4 mano ,10-2,10-3 (booth),10-5 mano / 6.1,6.4 (booth's algo),

6.7(IEEE standards) zaki
Representation of fixed and floating-point numbers, 2's complement arithmetic.

3 Control unit ch - 7.1 , 7.2, 7.4, 7.5 zaki 411 / 4.1,4.2 , 7.4 mano
Organization of a CPU, control and data paths, micro-operations, register-transfer level
specifications. [rtl -37 page zaki] ( to read 2.1,2.2,2.3 zaki ) [ datapath- 414 zaki]

4 Memory system 5.1, 5.2.1, 5.2.2, 5.3, 5.4, 5.5, 5.6, 5.7 , 5.8,5.9 zaki / 12.1,12,2,
12.3,12.5,12.6(optional) from Mano coa
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.

5 Input-output systems 2.7, 4.1, 4.2,4.4,4.5,4.7 zaki / 11-2, 11-4,11-5[daisy chain] , 11-6
Mano
Programmed I/O, Interrupt-driven I/O, polling and vectored interrupt, basic concept of DMA
transfer.

6 Pipelining 8.1 to 8.5 and 8.8 zaki / 9-2, 9-3,9-4 mano

Basic concepts of pipeline. ---------- END ------------
 Gate Computer Science 11

Now Read Zaky and Hamacher chapter number 2,4, 5, 6, 7, 8 ---- i have 5 th edition,
What to read ? from zaky 5th edition second chapter- m/c instructions and programs (chapter
2 ) u have to read 2.1.1 to 2.1.4, 2.2 , 2.4, 2.5, 2.7, 2.9 these sub-parts.
Chapter 4 (I/O organization) 4.2, 4.4, 4.5, 4.7.
From chapter 5 ( The memory system ) 5.1 to 5.9.
Chapter 6 [ Arithmetic] -- 6.1, 6.3, 6.4(booth algo) , 6.6, 6.7 .
Chapter 7 ( basic processing unit ) 7.1, 7.2, 7.4, 7.5 .
Chapter 8 ( pipeline )--- 8.1 to 8.5 and 8.8 .

Among these topics cache [ access policy], pipeline and m/c instructions are very imp,

video - s raman , pkbiswas for pipeline

3 . Types of problems generally comes from that chapter.

Problem type:

• Addressing Modes : Theory and questions

• Numerical related to program counter after some instruction, no of one address-two

address instructions, Values after shift and rotate instructions, horizontal and vertical
programming related questions.

• Numerical Problems on Speed up of pipeline, time taken to complete instruction in

pipeline and non-pipeline architectures, Hazards in pipeline, hazards removal, branch
penalty etc.

• Numerical Problems on cache memory organization, mapping technique, multilevel

caches, write through and write back technique
 Gate Computer Science 12

Compiler
Syllabus:
Lexical analysis, parsing, syntax-directed translation. Runtime environments. Intermediate
code generation.

Book- Aho sethi Ullman

These are chapters from this book to read
chapter 1 complete
chapter 2 complete
chapter 3 - 3.1, 3.2, 3.3, 3.4 , 3.5
chapter 4 - 4.1, 4.2, 4.3, 4.4 to 4.9 - 4.4 first and follow - complete chapter to read
chapter 5 - 5.1, 5.2, 5.3 , 5.4, 5.5
chapter 6 - 6.1, 6.2, 6.6 , 6.7
chapter 7 - 7.2 ,7.3, 7.4

Types of problems comes in exam:

1 . 3 address code : [ minimum number of temporary variables ] constructing 3 address code

for an expression 6.2
2 Abstract Syntax tree - from syntax directed translation 5.3
3 Control flow graph no of nodes and edges from Intermediate code generation 6.6 [ CFG
not in syllabus ]
4. Finding First and Follow 4.4
5. Parsing : there is always a question related to parsing. You need to practice all parsing
technique because there is also chances for linked questions.
4.4- 4.9
6. lexical analysis
7. Finding internal node in syntax-directed translation 5.4, 5.5
8. finding first and follow,
9. Number of token generated 3.3 ,3.4
10. a grammer is given , you have to find : 4.4 - 4.7
LL(1)-LR(1)-SLR-LALR-CLR.
11. Precedence and Associativity of operators. 4.8, 4.9
12• Finding value from expression tree. 2.8 , 6.1
13• Ambiguous grammar 4.3

http://nptel.ac.in/courses/106104123
 Gate Computer Science 13

Compiler IITK:

By Prof S k Agarwal

For Gate lec no- 2, 4 to 27

Lecture 1 - History and Overview of the subject compiler design

Lecture 2 - Overview of Different Steps Lexical Analysis to Code Generation
Lecture 3 - Discussion about different phases and Issues related to compiler design
Lecture 4 - Lexical Analysis
Lecture 5 - LA: Generation and Recognition of tokens
Lecture 6 - Lex and Syntax analysis
Lecture 7 - SA - Parse Tree , Ambiguity
Lecture 8 - Top Down parsing- First & Follow
Lecture 9 - Bottom Up parsing , shift reduce parsing , Handle pruning
Lecture 10 - Intro to LR parsing, simple LR
Lecture 11 - construction of Simple LR parse table from grammar
Lecture 12 - Canonical LR parse (1), construction of LR(1) items , Canonical LR
Lecture 13 - Constract LALR Parsing table , parser generator
Lecture 14- Syntax directed Translation , Attribute grammar
Lecture 15 - L Attributed Definition
Lecture 16 - Application of syntax directed translation
Lecture 17 - syntax directed translation schemes
Lecture 18 - Elimination of left recursion from SDT
Lecture 19 - Type conversion in Intermediate code generation
Lecture 20 - Three Address Code
Lecture 21 - 3 address code, types and declaration
Lecture 22 - Declaration, storage layout
 Gate Computer Science 14

Database Management Systems

1 What Books To Read :

Book Name :

1 Database Management Systems by Raghu Ramakrishnan, Johannes Gehrke ~ 2nd edition

2 Database System Concepts by Abraham Silberschatz, Henry F. Korth, S. Sudarshan ~ 4th

edition
3 Fundamentals of Database Systems - By Ramez Elmasri, Shamkant B. Navathe ~ 4th
edition

2. Topics for that subject to read along with Chapter Subparts : ** marked parts are
important for Numerical problems

ER-model. Relational model: relational algebra **, tuple calculus **, SQL. Integrity
constraints, normal forms**. File organization, indexing (e.g., B and B+ trees**).
Transactions and concurrency control.

Syllabus:

Introduction - General introduction to database systems; Database - DBMS disctinction,

approaches to building a database, data models, database management system, three-schema
architecture of a database, challenges in building a DBMS, various components of a DBMS.

Raghuramakrishnan - 1.2,1.3, 1.5, 1.6,1.7 , 1.8,1.9 / Korth - ch1- 1.1, 1.2,

1.3,1.4,1.5,1.6 ,1.7,1.8,1.9

E/R Model - Conceptual data modeling - motivation, entities, entity types, various types of
attributes, relationships, relationship types, E/R diagram notation, examples.

Raghuramakrishnan - 2.1 to 2.5 ,

korth - 2.1 to 2.9

Relational Data Model - Concept of relations, schema-instance distinction, keys, referential

integrity and foreign keys, relational algebra operators: selection, projection, cross product,
various types of joins, division, example queries, tuple relation calculus, domain relational
calculus, converting the database specification in E/R notation to the relational schema***.

Raghuramakrishnan - 3.1,3.2,3.3,3.4,3.5 , 4.1, 4.2,4.3

 Gate Computer Science 15

korth - 3.1 to 3.6, {only tuple reln calc}

SQL - Introduction, data definition in SQL, table, key and foreign key definitions, update
behaviors. Querying in SQL - basic select-from-where block and its semantics, nested queries
- correlated and uncorrelated, notion of aggregation, aggregation functions group by and
having clauses, embedded SQL.

Raghuramakrishnan - 5.1, 5.2, 5.3, 5.4, 5.5, 5.6.2, 5.6.3, 5.6.4

korth - 4.1 to 4.7, 4.9

Dependencies and Normal forms - Importance of a good schema design, problems

encountered with bad schema designs, motivation for normal forms, dependency theory -
functional dependencies, Armstrong's axioms for FD's, closure of a set of FD's, minimal
covers, definitions of 1NF, 2NF, 3NF and BCNF, decompositions and desirable properties of
them, algorithms for 3NF and BCNF normalization, multi-valued dependencies and 4NF, join
dependencies and definition of 5NF.

Navathe - page 293 --> 10.1 to 10.5 , page 333 --> 11.1, 11.2, 11.3,11.4,
Raghuramakrishnan - 15.1 to 15.8

Data Storage and Indexes - file organizations, primary, secondary index structures, various
index structures - hash-based, dynamic hashing techniques, multi-level indexes, B+ trees.

Raghuramakrishnan - 8.1 to 8.4 , 9.1 to 9.7 , 10.1 to 10.3 ,

Korth - 12.1,12.2[imp, Multilevel -12.2.1.2] , 12.3,12.4[imp] , 12.5

Transaction processing and Error recovery - concepts of transaction processing, ACID

properties, concurrency control, locking based protocols for CC, error recovery and logging,
undo, redo, undo-redo logging and recovery methods.

Korth - 15.1,15.2,15.3,15.4,15.5[imp] ,15.6,15.7,15.8,15.9 [imp] , concurrency - 16.1,16.2

[imp],16.3 , 16.6, 16.7, 16.8
Raghuramakrishnan - 18.1 to 18.4 , 19.1, 19.2, 19.3.1

3. From where to read ?

1 Raghuramakrishnan - 10 chapters , chapter number 1, 2, 3 [3.1,3.2,3.3,3.4,3.5 ], 4

[4.1,4.2,4.3 ] , 5 [5.1, 5.2, 5.3, 5.4, 5.5, 5.6.2, 5.6.3, 5.6.4] ,8,9, 15, 18, 19 .

2 Korth - ch no- 2, 3, 4, 6, 7, 11, 12, 15,16

3 navathe - 11 chapters , ch 2,3, 5,6, 7.1,8,10,11,14,17,18

 Gate Computer Science 16

4 . Types of problems from where questions came previous years :

1 ER-model. Relational model: relational algebra, tuple calculus

er diagram - What is the minimum number of tables required 05 ,2008,

properties of er model 2012 ,
Meaning of given Tuple Relational Calculus query 2008, 2007 normal form 2016,
meaning of relational algebra-2007 ,2014 functional dependencies 2005 relation algebra
optimized version- 2014 , join 2004, 2014 , optimized form 2014, no of tuples 2012 ,
2013, meaning of query 2008

2 SQL

• SQL Queries . Practice select clause properly with properties of having,group by, any ,all,
exits.
Question may come with relational algebra in common data section.

3 Integrity constraints, normal forms.

Normalization. Questions are like Finding normal form ( 2016 ,09, 08 , 03), finding
candidate keys [ 2013,11,14,05] , decomposition of relation [2002] ,
loss less join and dependency preservation[2001] . minimal cover - 2014

4 Transactions and concurrency control

• Finding View and Conflict serializability [ 2014 ,2012,10,2003,2008] .

Finding Recoverable [2014, 2006 ,2015 ,2016] and Cascade schedule.
lock based[2004], Two phase, time stamp and graph based protocal with there properties
like deadlock freedom [2016 ] , starvation freedom.
Acid properties in real life situation in trandaction 2015 , 2016

5 File organization, indexing (e.g., B and B+ trees).

• formation and structure of B and B+ tress. primary and clustering index[2013, 08 , 2002,
2015 ] .
Numerical Questions from no of block required in indexing of different type,[IT 2005]
collision resolution,
minimum and maximum no of nodes in B,B+ trees [2010]. ordered indexing & hashing 2011

Video lectures:
https://www.youtube.com/playlist?list=PLyvBGMFYV3auVdxQ1-88ivNFpmUEy-U3M
Lectures by Partha Pratim Chakrabarti
 Gate Computer Science 17

Digital!
Book Name : Digital Design - M. MORRIS MANO and MICHAEL D. CILETTI,
3rd edition Chapter 1,2,3,4,5,6,7,9 have to read completely
Video Lectures - IITM S srinivasan [1 to 30 ]
https://www.youtube.com/playlist?list=PL803563859BF7ED8C

Nptel Mooc - IITM Shankar Balachandran

https://onlinecourses.nptel.ac.in/noc15_ec01/preview,
https://www.youtube.com/playlist?list=PLUtfVcb-iqn8ff92DJ0SZqwsX4W1s_oab

1. What to read ? Syllabus to cover for that particular subject.

Boolean algebra. Combinational and sequential circuits. Minimization. Number

representations and computer arithmetic (fixed and floating point).

2. From where to read ? Chapter subparts to read from standard text book.
Chapter Number
Morris M Mano
Boolean algebra :

Laws of Boolean algebra, Theorems of Boolean algebra, Switching functions, Methods for
specification of switching functions - chapter 2- 2.1 to 2.8

Truth tables and Algebraic forms, Realization of functions using logic gates.

Combinational and sequential circuits

1 Design of Combinational Logic Circuits: chapter 4 - 4.1 to 4.9

Gate level design of Small Scale Integration (SSI) circuits, Modular combinational logic
elements - Decoders, Encoders, Priority encoders, Multiplexers and Demultiplexers.

Design of Integer Arithmetic Circuits using Combinational Logic: (Application )

Integer adders - Ripple carry adder and Carry look ahead adder, Integer subtractors using
adders, chapter 5 - 5.1 to 5.9
Unsigned integer multipliers - Combinational array circuits,
 Gate Computer Science 18

Signed integer multipliers - Booth's coding, Bit-pair recoding, Carry save addition and
Wallace tree multiplier,
Signed integer division circuits - Combinational array circuits, Complexity and
propagation delay , analysis of circuits.

2 Sequential Circuit Elements:

Latches -RS latch and JK latch, Flip-flops-RS, JK, T and D flip flops, Master-slave flip
flops, Edge-triggered flip-flops.
chapter 6 - 6.1 to 6.8

Analysis and Design of Synchronous Sequential Circuits:

Models of sequential circuits - Moore machine and Mealy machine,
Flip-flops - Characteristic table, Characteristic equation and Excitation table,
Analysis of sequential circuits- Flipflop input expressions, Next state equations, Next
state maps, State table and State transition diagram,
Modular sequential logic circuits- Shift registers, Registers, Counters and Random access
memories,
chapter 7 - 7.1 to 7.9

Design of Arithmetic Circuits using Sequential Logic :

Serial adder for integers, Unsigned integer multiplier, Unsigned integer division circuits,
Signed integer division, Floating-point adder/subtractor - Design of control circuit, Floating -
point multiplier. : Introduction to digital computer :
chapter 9 - 9.1 to 9.8
Design of Arithmetic circuits – Adders, Multipliers
Design of Memory – ROM/RAM

Minimization: (Simplification of Boolean Expressions and Functions )

chapter 3 - 3.1 to 3.11

Algebraic methods, Canonical forms of Boolean functions, Minimization of functions

using Karnaugh maps, Minimization of functions using Quine-McClusky method.

Number representations and computer arithmetic (fixed and floating point)

Number systems and codes - ( Binary, octal and hexadecimal number systems; Methods of
base conversions; Binary, octal and hexadecimal arithmetic )
chapter 1 - 1.1 to 1.9

Representation of unsigned and signed integers, Fixed-point representation of real

numbers, Floating-point representation of real numbers,
 Gate Computer Science 19

3 . Types of problems generally come from that chapter.

“Practice K-Map minimization. SOP, POS , Don't care representation

• Practice Multiplexer, De-multiplexer, Encoder, Decoder questions.
• Understand concept of flip flop. They are given and modulas of counter is asked.
• Practice questions related to Floating Point representation, integer representation, ieee
format, range and precision."
A Truth table is given , what function does it represent
D typed flip-flop
4 input multiplexer 4 to 1 , determine the output F 2010,2014
J-k flip flop state sequence 2014 , 2015
Calculate the propagation delay in flip flops
minimum no of gates required to implement the given boolean function 2009, 2004
a sequence is given and you have to find out minimum number of j-k flip flip require to
implement the counter 2016 , 2015
counter - 2011, 2007, 2004, 2014
important flip flops - J-K , D, T , RS type of flip flops
propagation delay of adder 2004 [62] , 2015 set 1[47] ,set 2[65]
design of counter using flip flop 2015, 2016
determining-minimum-number-of- nand-nor-gates-required-to-realize-a-boolean
expression 2009, 04
 Gate Computer Science 20

Discrete Mathematics and Engineering

Mathematics!
Syllabus :

Propositional and first order logic. Sets, relations, functions, partial orders and lattices.
Groups. Graphs: connectivity, matching, coloring. Combinatorics: counting, recurrence
relations, generating functions.

Linear Algebra: Matrices, determinants, system of linear equations, eigenvalues and

eigenvectors, LU decomposition.

Calculus: Limits, continuity and differentiability. Maxima and minima. Mean value theorem.
Integration.

Probability: Random variables. Uniform, normal, exponential, poisson and binomial

distributions. Mean, median, mode and standard deviation. Conditional probability and Bayes
theorem.

1. What Books to read :

1 Kenneth H Rosen 7 th Ed. - Chapter 1,2 and 6 , 8, 9 , 10 ( 10.4, 10.5, 10.8)

2 Susanna S Epp - Discrete Mathematics with Applications : Chapter 2 , 3, 6,
7, 8 , 9
3 Erwin Kryszig - 9th edition Chapter 7.1 to 7.7 , 8.1 to 8.3 , 20.2
4 Narsingh Deo - Chapter 2-5, 2-6, 4-5, 8-1, 8-2, 8-4, 8-6
5 Sheldon Ross - Chapter 1,2,3, 4 [exclude 4.8] ,5 [ exclude 5.6 ]
"Optional :
6 Kolman-Busby-Ross - Group and Semigroup - 9.1 to 9.5
7 Ralph P Grimaldi - Discrete & Combinatorial Math - Ring : 14.1 and 14.2 "
Video : IITM Discrete - https://www.youtube.com/playlist?list=PL0862D1A947252D20

LU Decomposition - https://www.youtube.com/watch?v=gA7m5lttIcU , this is the first

video which need to be watched then shortcut ,finally system of equations video have to
watch.

LA and calculus - video - https://www.youtube.com/playlist?

list=PLx5CT0AzDJCmqjbTWbWCwzanbZwWQ_b18

2. Topics for that subject to read along with Chapter Subparts :

Propositional and first order logic - Rosen Chapter 1 - 1.1 to 1.6

 Gate Computer Science 21

Propositional Logic - Page 1 to 12. page 16 and 17

Propositional Equivalences - Page 25 to 31
Predicates and Quantifiers - page 37 to 49
Nested Quantifiers - page 57 to 63
Rules of Inference - page 69 to 78
Sets - Rosen Chapter 2 : 2.1 , 2.2
relations - Rosen Chapter 9 , 9.1 to 9.5
functions - Rosen Chapter 2.3
partial orders and lattices - Rosen Chapter 9.6

Groups : GROUP, Abelian Group, SEMIGROUP, MONOID, RING, INTEGRAL

DOMAIN, FIELD from IITM Kamala Madam video lectures 35, 36, 37

Graphs : connectivity, matching, coloring is there in syllabus

From Rosen - connectivity, euler and hamilton paths , coloring is in chapter 10 - 10.4,
10.5, 10.8
From narsingh deo Chapter no 2 - 2-5, 2-6, Chapter no 4 - 4-5 [ connectivity] , Chapter no
8 - 8-1, 8-2, 8-4, 8-6 , so 4 color theorem , Independent set is imp from graph coloring.

Counting, recurrence relations, generating functions - Rosen Chapter 6 and Chapter 8

Linear Algebra : Erwin Kryszig - 9th edition Chapter 7.1 to 7.7 , 8.1 to 8.3 , video -
https://www.youtube.com/playlist?list=PLx5CT0AzDJCmqjbTWbWCwzanbZwWQ_b18

Calculus : mean value theorem page 402 Kreyszig , and also from above video link

Probability : A first course in probability ~ Sheldon Ross,8th edition, chapter 1,2,3, 4

[exclude 4.8] ,5 [ exclude 5.6 ]

3. Types of problems from where questions came previous years :

1. Simple problems on logic.

2. Sets Related Questions. Properties of relation, function. Partial and Total Ordering.

3. Hasse Diagrams, Group Theory.

4. Different types of graph and there properties : vertex and edge connectivity , separable
graph , k-connected graph , connected component, matching , graph coloring ( 4 color
theorem ) ,
Euler and Hamiltonian Graphs , konigsberg Bridge problem, Independent set of vertices ,
chromatic number are important .
 Gate Computer Science 22

5. Tricky Problems on Permutations and Combinations. Pigeonhole principle.

6. LA : Eigen values and eigen vectors question. Simple questions related to matrix.

7. LA : Finding Values of variable with some properties of linear equations like infinite no
of solutions or unique solution.

8. Calculus : Finding Maxima and Minima. Properties of limit, Continuity and

differentiability. Finding values by Mean Value Theorem. Integration.

9. For probability questions You need to practice Bays theorem, Normal and poisson
distribution, mean and variance of different distributions , standard deviaton .
 Gate Computer Science 23

Computer Networks
1. What Books to read :

Book Name :

1. Computer Networking: A Top-Down Approach (1st Edition) by Kurose and Ross

2. Andrew S Tanenbaum - Computer networks , 4th edition

3. Behrouz A. Forouzan - Data Communications And Networking , 4th edition

2. Topics for that subject to read along with Chapter Subparts : ** marked parts are
important for problems

Concept of layering --- Kurose & Ross chapter 1.7 / Andrew S Tanenbaum chapter -
1.4

LAN technologies (Ethernet) --- Kurose & Ross chapter 5.2.3 , 5.5(5.5.3) / Andrew S
Tanenbaum chapter - 4.3

** Flow and error control techniques --- Kurose & Ross chapter 3.4.2 3.5.6[ flow control],
5.1, 5.2 / Andrew S Tanenbaum chapter - 3.1, 3.3.2, 3.4 [ Flow ] 3.2 [ error]

switching --- Kurose & Ross chapter 1.4 / Andrew S Tanenbaum chapter - 2.5.5

** IPv4/IPv6 ---- Kurose & Ross chapter 4.4, 4.7 / Andrew S Tanenbaum chapter -
5.6.1, 5.6.2, ( IPv4) 5.6.8 (IPv6)

routers ---- Kurose & Ross chapter 4.6 / Andrew S Tanenbaum chapter - 5.1.3, 5.1.4

** routing algorithms (distance vector, link state) ----- Kurose & Ross chapter 4.2 /
Andrew S Tanenbaum chapter - 5.2.1, 5.2.2, 5.2.3, 5.2.4 (DV), 5.2.5(link state),

TCP/UDP and sockets ---- Kurose & Ross chapter 3.3, 3.5 (sockets - 2.6,2.7) / Andrew
S Tanenbaum chapter - 6.1.3(sockets) , 6.4.1(udp), 6.5.1,6.5.2,6.5.3,6.5.4,6.5.5, 6.5.6, 6.5.8

** congestion control --- Kurose & Ross chapter 3.6, 3.7 / Andrew S Tanenbaum
chapter - 5.4.2 [leaky & token]
 Gate Computer Science 24

Application layer protocols (DNS, SMTP, POP, FTP, HTTP) --- Kurose & Ross chapter
2.1, 2.2, 2.3, 2.4 / Andrew S Tanenbaum chapter - 7.1,7.2,7.3

Basics of Wi-Fi --- Kurose & Ross chapter 6.1,6.2,6.3 (5.7 in old version) / Andrew S
Tanenbaum chapter - 4.4

Network security: authentication --- Kurose & Ross chapter 7.3 / Andrew S Tanenbaum
chapter - 8.7

** basics of public key and private key cryptography --- Kurose & Ross chapter ( Asymetric
key cryptography) 7.2 / Andrew S Tanenbaum chapter - 8.3

digital signatures and certificates --- Kurose & Ross chapter 7.5 / Andrew S Tanenbaum
chapter - 8.4.2 , 8.5.1

Firewalls --- Kurose & Ross chapter 8.5 / Andrew S Tanenbaum chapter - 8.6.2

3. From where to read ? to read from standard text book :

Computer Networking: A Top-Down Approach (1st Edition) by Kurose and Ross [ Chapter
1 to 5 ]
[ chapter 6 (basics of wifi) - 6.1, 6.2 , 6.3 ] [ chapter 8 - security in computer networks ]

AN Tanenbaum - chapter 1,2,3,4,5,6,7,8

4. Types of problems from where questions came previous years:

Important Types :

• Addressing related questions :: Subnet address, supernet address, brodcast address, range of
network, no of host, classless addressing, non continuous addresses, first host and last host
finding etc.

• Properties Of Circuit Switching and packet switching, Routing Protocols and Numerical
Problems on them.

• Flow Control and Error Control Policies.

Numerical Problems on Window Size [ sliding window protocols ] , No Of Sequence bits,
frame size, bandwidth, round trip time, utilization, Hamming Distance, CRC.
selective repeat [2016] , stop n wait [2016] , go back n[2008] - flow control .
 Gate Computer Science 25

• Congestion Control policies like slow start, congestion avoidence and Congestion
Detection. Token bucket [2016]

• IP Header , TCP and UDP header format, theory related to Ethernet . csma/cd

• Basics Of Different Type of protocols like : FTP, HTTP, DHCP, ARP, RARP, SMTP,
ICMP,POP .

• Basic Concepts of Cryptography and firewalls.

 Gate Computer Science 26

Operating System
Syllabus:
Processes, threads, inter-process communication, concurrency and synchronization.
Deadlock. CPU scheduling. Memory management and virtual memory. File systems.

1. What Books to read :

Book Name :
1 Operating System Concepts By Galvin 7th Edition ,
Chapter - 1 , 2, 3, 4, 5, 6, 7, 8 , 9, 10 , 11, 12
2 Operating Systems Internals and Design Principles By William Stalling , 5 Ed,
Chapter 3 , 4, 5 , 6, 9, 7 , 8 , 12
3 Modern Operating System By Andrew S Tanenbaum- 3 rd Edition ,
Chapter 2 , 3 , 4, 6 completely have to read

Video - P k Biswas ( Scheduling, Deadlock part is well explained) , Lecture No - 1 to 29

IISc - T Mathew Jacob ( best for process, IPC, Concurrency, memory & VM, Files and
storage ) Lecture Number - 12 , 13, 14, 15, 16,17,18,19,20 , 34 , 35
https://www.youtube.com/playlist?list=PL2F82ECDF8BB71B0C

2. Topics for that subject to read along with Chapter Subparts : ** marked parts are
important for problems

Processes : Galvin Chapter - 3 ( 3.1, 3.2, 3.3 ) / Stalling Chapter 3 ( 3.1, 3.2, 3.3, 3.4 )

Threads : Galvin Chapter - 4 ( 4.1, 4.2, 4.4, 4.5 ) / Stalling Chapter 4 ( 4.1, 4.2 )

Inter-process communication : Galvin 3.4 , 3.5 , 3.6

** Concurrency and synchronization : Galvin Chapter - 6 ( 6.1, 6.2, 6.3, 6.5, 6.6, 6.7, 6.8,
6.9) / Stalling Chapter 5 ( 5.1, 5.2, 5.3, 5.4, 5.5, 5.6 ) This chapter is better written than
Galvin

** Deadlock : Galvin Chapter - 7 ( 7.1, 7.2, 7.3, 7.4, 7.5, 7.6, 7.7 ) / Stalling Chapter 6
( 6.1, 6.2, 6.3, 6.4, 6.6 )

** CPU scheduling: Galvin Chapter - 5 ( 5.1, 5.2, 5.3, 5.4, 5.5, 5.7 ) / Stalling Chapter 9
( 9.1, 9.2 )
 Gate Computer Science 27

** Memory Management : Galvin Chapter - 8 ( 8.1, 8.2, 8.3, 8.4, 8.5, 8.6 ) / Stalling
Chapter 7 ( 7.1, 7.2, 7.3, 7.4 )

** Virtual memory : Galvin Chapter - 9 ( 9.1, 9.2, 9.4, 9.5, 9.6, 9.7, 9.8) / Stalling
Chapter 8 ( 8.1, 8.2 ) well written in stalling

** File systems: Galvin Chapter - 10 ( 10.1, 10.2, 10.3, 10.5 ) / Stalling Chapter 12 ( 12.1,
12.2, 12.4, 12.6 )
Chapter - 11( 11.1, 11.2, 11.4, 11.5, 11.6 )
** Chapter- 12.2, 12.3, 12.4 , 12.5, 12.7

3. Types of problems from where questions came previous years :

• Scheduling: Numerical Questions have more chances. Practice more in finding turn around
time and waiting time of different scheduling policies.

• Deadlock: Bankers Algo, Given Sequence is safe or not. Chances of common data or linked
questions.

• Concurrency and Synchronization : High Probability Of Questions in exam. Practice

some question related to semaphores and classical problems of synchronization
(this will help you to solve other questions), Mutual Exclusion case using P and V , Critical
section problem.
• Memory Management : Questions generally comes from page table size, number of pages,
logical address, physical address, page size, inverted page table, virtual memory, TLB etc.

• File systems: algorithms for disk scheduling