GATE 2020 Computer Science and Information Technology

Cover
Contents
Preface
Key Pedagogical Features
Syllabus: Computer Science and Information Technology
Chapter-wise Analysis of GATE Previous Years’ Papers
General Information about GATE
GATE 2019 Solved Paper
Unit 1: Digital Logic
	Chapter 1: Number Systems
		Digital Circuits
		Complements
		Exercises
		Previous Years’ Questions
		Answer Keys
	Chapter 2: Boolean Algebra and Minimization of Functions
		Logic Gates
		Boolean Algebra
		Properties of Boolean Algebra
		Boolean Functions, Min Terms and Max Terms
		Minimization of Boolean Functions
		Implementation of Function by Using NAND–NOR Gates
		EX-OR, EX-NOR Gates
		Exercises
		Previous Years’ Questions
		Answer Keys
	Chapter 3: Combinational Circuits
		Introduction
		Combinational Logic Design
		Arithmetic Circuits
		Code Converters
		Decoder
		Encoders
		Multiplexer
		Demultiplexer
		Exercises
		Previous Years’ Questions
		Answer Keys
	Chapter 4: Sequential Circuits
		Sequential Circuits
		Flip-flops
		Counters
		Registers
		Exercises
		Previous Years’ Questions
		Answer Keys
	Test
Unit 2: Computer Organization and Architecture
	Chapter 1: Machine Instructions, Addressing Modes
		Computer
		Machine Instructions
		Addressing Modes
		Computer Performance
		Exercises
		Previous Years’ Questions
		Answer Keys
	Chapter 2: ALU and Data Path, CPU Control Design
		ALU (Arithmetic and Logic Unit)
		Data Path
		CPU Control Design
		RISC and CISC
		Exercise
		Previous Years’ Questions
		Answer Keys
	Chapter 3: Memory Interface, I/O Interface
		Memory Interface
		Input–output Interfacing
		Exercises
		Previous Years’ Questions
		Answer Keys
	Chapter 4: Instruction Pipelining
		Flynn’s Classification
		Pipelining
		Pipeline Performance
		Pipeline Hazards
		Exercises
		Previous Years’ Questions
		Answer Keys
	Chapter 5: Cache and Main Memory, Secondary Storage
		Characteristics of Memory System
		Memory Hierarchy
		Cache Memory
		Secondary Storage
		Exercise
		Previous Years’ Questions
		Answer Keys
	Test
Unit 3: Programming and Data Structures
	PART A: Programming and Data Structures
		Chapter 1: Programming in C
			Basic Concepts
			Data Types
			Program Structure
			Control Statements
			Exercises
			Previous Years’ Questions
			Answer Keys
		Chapter 2: Functions
			Functions
			Recursion
			Parameter Passing
			Scope, Lifetime and Binding
			Exercises
			Previous Years’ Questions
			Answer Keys
		Chapter 3: Arrays, Pointers and Structures
			Arrays
			Two-dimensional Arrays
			Multidimensional Arrays
			Pointers
			Array of Pointers
			Pointer to Function
			Dynamic Memory Management
			Structures
			Union
			Exercises
			Previous Years’ Questions
			Answer Keys
		Chapter 4: Linked Lists, Stacks and Queues
			Data Structure
			Linkek List
			single-Linked List
			Uses of Stack
			Queue
			Exercises
			Previous Years’ Questions
			Answer Keys
		Chapter 5: Trees
			Tree
			2-Tree
			Binary Tree
			Binary Heap
			Exercises
			Previous Years’ Questions
			Answer Keys
		Test
	PART B: Algorithms
		Chapter 1: Asymptotic Analysis
			Algorithm
			Set Representation
			Graph Representation
			Tree Representation
			Data Structure
			Asymptotic Notations
			Notations and Functions
			Exercises
			Previous Years’ Questions
			Answer Keys
		Chapter 2: Sorting Algorithms
			Sorting Algorithms
			Merge Sort
			Bubble Sort
			Insertion Sort
			Selection Sort
			Binary Search Trees
			Heap Sort
			Exercises
			Previous Years’ Questions
			Answer Keys
		Chapter 3: Divide-and-conquer
			Divide-and-conquer
			Merge Sort
			Quick Sort
			Searching
			Exercises
			Previous Years’ Questions
			Answer Keys
		Chapter 4: Greedy Approach
			Greedy Approach
			Knapsack Problem
			Spanning Trees
			Prim’s Algorithm
			Kruskal’s Algorithm
			Tree and Graph Traversals
			Connected Components
			Huffman Codes
			Task-scheduling Problem
			Sorting and Order Statistics
			Graph Algorithms
			Exercises
			Previous Years’ Questions
			Answer Keys
		Chapter 5: Dynamic Programming
			Dynamic Programming
			Multi-stage Graph
			All Pairs Shortest Path Problem (Floyd–Warshall Algorithm)
			Hashing Methods
			Matrix-chain Multiplication
			Longest Common Subsequence
			NP-hard and NP-complete
			Exercises
			Previous Years’ Questions
			Answer Keys
		Test
Unit 4: Databases
	Chapter 1: ER Model and Relational Model
		Introduction
		Schemas
		ER Model
		Relationship Sets
		Cardinality Ratio and Participation Constraints
		Relational Database
		NULL in Tuples
		Relational Model Constraints
		Triggers
		Exercises
		Previous Years’ Questions
		Answer Keys
	Chapter 2: Structured Query Language
		Relational Algebra
		Tuple Relational Calculus
		SQL (Structured Query Language)
		Exercises
		Previous Years’ Questions
		Answer Keys
	Chapter 3: Normalization
		Normalization
		First Normal Form (1NF)
		Second Normal Form
		Third Normal Form
		Higher Normal Forms (Boyce–Codd Normal Form)
		Fourth Normal Form
		Fifth Normal Form
		Exercises
		Previous Years’ Questions
		Answer Keys
	Chapter 4: Transaction and Concurrency
		Introduction
		Transaction
		Concurrency Control
		Transaction Processing Systems
		Concurrency Control with Locking Methods
		Deadlocks
		Concurrency Control with Time Stamping Methods
		Serializability
		Recoverability
		Equivalence of Schedules
		Exercises
		Previous Years’ Questions
		Answer Keys
	Chapter 5: File Management
		Files
		Memory Hierarchies
		Description of Disk Devices
		File Records
		Sorted Files (Ordered Records)
		Hashing Techniques
		Indexing
		Exercises
		Previous Years’ Questions
		Answer Keys
	Test
Unit 5: Theory of Computation
	Chapter 1: Finite Automata and Regular Languages
		Fundamentals
		NFA with ∈-Moves
		Mealy and Moore Machines
		Regular Languages
		Constructing FA for Given RE
		Closure Properties of Regular Sets
		Types of Gramars
		Exercises
		Previous Years’ Questions
		Answer Keys
	Chapter 2: Context Free Languages and Push Down Automata
		Context Free Grammar
		Context Free Language (CFL)
		Ambiguity in Context Free Grammars
		Minimization of Context Free Grammar
		Normal Forms
		Pumping Lemma for Context Free Languages
		Closure Properties of CFL’s
		Push Down Automata (PDA)
		Converting CFG to PDA
		Deterministic PDA (Deterministic CFL)
		Exercises
		Previous Years’ Questions
		Answer Keys
	Chapter 3: Recursively Enumerable Sets and Turing Machines, Decidability
		Turing Machines
		Languages Accepted by a TM
		Types of Turing Machines
		Recursively Enumerable Languages
		Properties of Recursive and Recursively Enumerable Languages
		Undecidability
		Problems
		NP Problems
		NP-Complete Problem
		NP-Hard Problem
		Exercises
		Previous Years’ Questions
		Answer Keys
	Test
Unit 6: Compiler Design
	Chapter 1: Lexical Analysis and Parsing
		Language Processing System
		Lexical Analysis
		Syntax Analysis
		Context Free Grammars and Ambiguity
		Types of Parsing
		Topdown Parsing
		Bottom up Parsing
		Exercises
		Previous Years’ Questions
		Answer Keys
	Chapter 2: Syntax Directed Translation
		Syntax Directed Translation
		Syntax Directed Definitions
		Synthesized Attribute
		Dependency Graph
		Constructing Syntax Trees for Expressions
		Types of SDD’S
		Syntax Directed Translation Schemes
		Bottom-up Evaluation of Inherited Attributes
		exerciSeS
		Previous Years’ Questions
		Answer Keys
	Chapter 3: Intermediate Code Generation
		Introduction
		Three-Address Code
		Symbol Table Operations
		Assignment Statements
		Boolean Expressions
		Flow of Control Statements
		Procedure Calls
		Code Generation
		Runtime Storage Management
		DAG Representation of Basic Blocks
		Peephole Optimization
		Exercises
		Previous Years’ Questions
		Answer Keys
	Chapter 4: Code Optimization
		Code Optimization Basics
		Principle Sources of Optimization
		Loops in Flow Graphs
		Global Dataflow Analysis
		Exercises
		Previous Years’ Questions
		Answer Keys
	Test
Unit 7: Operating System
	Chapter 1: Processes and Threads
		Basics of Operating System
		Processes
		OS Control Structures
		Process Control Structures
		Process Control
		Threads
		Thread Functionality
		Types of Threads
		Threading Issues
		Exercises
		Previous Years’ Questions
		Answer Keys
	Chapter 2: Interprocess Communication, Concurrency and Synchronization
		BasIc Concepts
		PrIncIples of Concurrency
		Process Interaction (IPC)
		Basic Definitions
		Critical Section
		Mutual Exclusion
		Other Mechanisms for Mutual Exclusion
		Classical Problems of Synchronization
		Monitors
		Message Passing
		Exercises
		Previous Years’ Questions
		Answer Keys
	Chapter 3: Deadlock and CPU Scheduling
		Deadlock
		Methods of Handling Deadlocks
		Dining Philosophers Problem
		CPU Scheduling
		Types of Processor Scheduling
		Scheduling Algorithms
		Exercises
		Previous Years’ Questions
		Answer Keys
	Chapter 4: Memory Management and Virtual Memory
		Basic Concepts
		Memory Management Requirements
		Memory Mapping Techniques
		Virtual Memory
		OS Software for Memory Management
		Exercises
		Previous Years’ Questions
		Answer Keys
	Chapter 5: File Systems, I/O Systems, Protection and Security
		File Systems
		File System Architecture
		File Directories
		Secondary Storage Management
		Free Space Management
		Unix File Management
		I/O Systems
		Disk Scheduling
		RAID (Redundant Array of Independent Disks)
		Protection and Security
		Exercises
		Previous Years’ Questions
		Answer Keys
	Test
Unit 8: Networks, Information Systems, Software Engineering and Web Technology
	Part A: Network
		Chapter 1: OSI Layers
			Computer Network
			LAN
			MAN
			WAN
			The OSI Reference Model
			LAN Technologies
			Physical Layer
			Data Link Layer
			Types of Errors Errors
			Medium Access Control Sublayer
			Exercises
			Previous Years’ Questions
			Answer Keys
		Chapter 2: Routing Algorithms
			Routing Algorithms Basics
			Flooding
			Distance Vector Routing
			Link State Routing
			RIP
			OSPF
			Congestion Control Techniques
			Exercises
			Previous Years’ Questions
			Answer Keys
		Chapter 3: TCP/UDP
			Transport Layer
			User Datagram Protocol (UDP)
			TCP/IP
			Application Layer
			Application Layer Protocols
			SMTP
			POP3
			IMAP 4
			HTTP
			DNS
			Networking Devices
			Exercises
			Previous Years’ Questions
			Answer Keys
		Chapter 4: IP(v4)
			IP Addressing
			Subnet Mask
			Classless Inter Domain Routing (CIDR)
			Network Address
			IP-Protocol
			Exercises
			Previous Years’ Questions
			Answer Keys
		Chapter 5: Network Security
			Network Security Basics
			Cryptographic Techniques
			Traditional Cipher Algorithms
			Symmetric Key Encryption
			Asymmetric Key Encryption
			Exercises
			Previous Years’ Questions
			Answer Keys
		Test
	Part B: Information Systems
		Chapter 1: Process Life Cycle
			IntroductIon
			Process Versus Program
			Software Components and Elements
			Information Gathering
			Requirement Analysis
			Feasibility Analysis
			Data Flow DIagrams (DFD)
			Processs PecIfIcatIon (PSPEC)
			Input/Output Design
			Software Process Life Cycle
			Software Process Models
			Exercises
			Previous Years’ Questions
			Answer Keys
		Chapter 2: Project Management and Maintenance
			Project Management
			Project Planning Tools
			Software Design
			Software Testing
			Implementation and Maintenance
			Exercises
			Previous Years’ Questions
			Answer Keys
		Test
	Part C: Software Engineering and Web Technology
		Chapter 1: Markup Languages
			Hypertext Markup Language (HTML)
			Tags
			Cascading Style Sheets
			Extensible Markup Language (XML)
			Client–Server Computing
			Exercises
			Previous Years’ Questions
			Answer Keys
		Test