Wiley Acing the GATE: Computer Science and Information Technology

Preface v
Acing the GATE ix
About GATE ix
Attributes for Success in Examination xi
1 Digital Electronics 3
1.1 Introduction 3
1.2 Number System 3
1.2.1 Conversions of Number System 4
1.2.2 Complement of a Number 4
1.2.3 Representation of Negative Numbers 5
1.2.4 The IEEE Standard for Floating Point Numbers 5
1.3 Boolean Logic 6
1.3.1 Boolean Algebra Laws (Huntington’s Postulates) 7
1.3.2 Duality Theorem 7
1.3.3 Consensus Theorem 7
1.3.4 Positive Logic and Negative Logic 8
1.4 Digital Circuits 11
1.4.1 Combinational Circuits 11
1.4.2 Sequential Circuits 16
1.5 Digital Logic Families 26
xiv  CONTENTS
Important Formulas 28
Solved Examples 28
Gate Previous Years’ Questions 33
Practice Exercises 46
Answers to Practice Exercises 51
2 Computer Organization and Architecture 57
2.1 Introduction 57
2.2 Computer Architecture 57
2.2.1 Register Set 57
2.2.2 Quantitative Principles to Design High-Performance Processor 58
2.3 Machine Instructions and Addressing Modes 58
2.3.1 Machine Instructions 58
2.3.2 Addressing Modes 59
2.4 Arithmetic Logic Unit 61
2.4.1 Arithmetic Micro-Operations 61
2.4.2 Logic Micro-Operations 61
2.5 CPU Control Design 62
2.5.1 Instruction Execution 63
2.5.2 CPU Data Path 64
2.5.3 Control Unit Design 64
2.5.4 RISC versus CISC Processors 65
2.6 I/O Interface (Interrupt and DMA Mode) 65
2.7 Instruction Pipelining 67
2.8 Memory Hierarchy 72
2.8.1 Main Memory 72
2.8.2 Secondary Memory 73
2.8.3 Cache Memory 73
2.8.4 Cache Mapping Techniques 74
Important Formulas 77
Solved Examples 77
GATE Previous Years’ Questions 80
Practice Exercises 95
Answers to Practice Exercises 100
3 Programming and Data Structures 105
3.1 Introduction 105
3.2 Basic Terminology 105
3.2.1 Programming Languages 105
3.2.2 Classification of High-Level Languages 106
3.2.3 Procedural Programming and Object-Oriented Programming 106
3.2.4 Data Types 107
3.2.5 Control Flow Statements 108
3.2.6 Array 110
3.2.7 Function and Recursion 111
3.2.8 Pointers 113
CONTENTS xv
3.2.9 Parameter Passing 115
3.2.10 Structures and Unions 117
3.2.11 Enumerated Data Types 117
3.2.12 Scoping 117
3.2.13 Binding 118
3.2.14 Abstract Data Types 119
3.3 Stack 119
3.3.1 PUSH Operation on Stack 119
3.3.2 POP Operation on Stack 119
3.3.3 Application of Stack 120
3.4 Queue 122
3.4.1 Basic Operations on Queue 122
3.4.2 Types of Queue 123
3.4.3 Applications of Queues 123
3.5 Linked List 123
3.5.1 Basic Operations 123
3.5.2 Linked List Implementation 124
3.6 Trees 125
3.6.1 Binary Tree 125
3.6.2 Types of Binary Trees 125
3.6.3 Array Representation of Binary Trees 126
3.6.4 Tree Applications 126
3.6.5 Binary Search Tree 126
3.6.6 Graphs 127
Important Formulas 137
Solved Examples 138
GATE Previous Years’ Questions 142
Practice Exercises 165
Answers to Practice Exercises 172
4 Algorithms 177
4.1 Introduction 177
4.2 Algorithm 177
4.2.1 Properties of Algorithm 177
4.2.2 Steps to Solve a Problem 177
4.2.3 Algorithm Analysis 178
4.2.4 Asymptotic Notation 178
4.2.5 Recurrence Relations 180
4.3 Hashing 182
4.3.1 Hash Table 182
4.3.2 Hashing Functions 182
4.3.3 Collisions 182
4.4 Binary Heap 184
4.4.1 Insertion in Min-Heap Tree 185
4.4.2 Deletion in Min-Heap Tree 185
4.4.3 Time Complexity 186
xvi  CONTENTS
4.5 Searching and Sorting 186
4.5.1 Linear Search 186
4.5.2 Binary Search 187
4.5.3 Bubble Sort 187
4.5.4 Selection Sort 187
4.5.5 Insertion Sort 188
4.5.6 Heap Sort 188
4.5.7 Merge Sort 190
4.5.8 Quick Sort 192
4.5.9 Randomized Quick Sort 193
4.5.10 Counting Sort 193
4.5.11 Comparison of Sorting Techniques 194
4.6 Graph 194
4.6.1 Types of Graph 194
4.6.2 Types of Simple Graph 194
4.6.3 Graph Representation 195
4.7 Greedy Approach 195
4.7.1 Applications of Greedy Approach 196
4.7.2 Fractional Knapsack 196
4.7.3 Huffman Coding 197
4.7.4 Minimum Spanning Tree 198
4.7.5 Single-Source Shortest Path 200
4.8 Graph Traversal 201
4.8.1 Breadth-First Traversal 201
4.8.2 Depth-First Traversal 202
4.9 Dynamic Programming 203
4.9.1 Applications of Dynamic Programming 204
4.9.2 Fibonacci Series 204
4.9.3 0/1 Knapsack 204
4.9.4 Longest Common Subsequence 205
4.10 All-Pair Shortest Path 205
4.10.1 Floyd’s Algorithm 205
4.11 Concepts of Complexity Classes 205
4.11.1 P-Complexity Class 205
4.11.2 NP Complexity Class 206
4.11.3 NP-Complete 206
4.11.4 NP-Hard 206
Important Formulas 207
Solved Examples 207
GATE Previous Years’ Questions 210
Practice Exercises 227
Answers to Practice Exercises 232
5 Theory of Computation 237
5.1 Introduction 237
5.2 Finite Automata 237
5.2.1 Finite Automaton Model Characteristics 238
5.2.2 Technical Terms 238
5.2.3 Grammar 239
CONTENTS xvii
5.2.4 Noam Chomsky Grammar Classification 239
5.2.5 Chomsky Hierarchy 240
5.2.6 Different Grammar Types 240
5.3 Finite Automata and Regular Language 241
5.3.1 Deterministic Finite Automata 241
5.3.2 Non-deterministic Finite Automata 241
5.3.3 Comparison of DFA and NFA 241
5.3.4 DFA and NFA Design 241
5.3.5 Applications of DFA/NFA 243
5.3.6 Regular Expression and Grammar 243
5.3.7 Pumping Lemma 244
5.3.8 Myhill—Nerode Theorem 245
5.3.9 Transducer or Finite State Machine 245
5.3.10 Conversion in Finite Automata 246
5.3.11 Properties of Regular Sets/Languages 249
5.3.12 Some Important DFA 250
5.4 Pushdown Automata 250
5.4.1 Model of PDA 250
5.4.2 Transition Function 251
5.4.3 Non-deterministic PDA 251
5.4.4 Deterministic PDA 251
5.4.5 Parsing 252
5.5 Context-Free Grammar and Languages 252
5.5.1 Context-Free Grammar 252
5.5.2 Standard Context-Free Language 252
5.5.3 Derivation Tree or Parse Tree 253
5.5.4 Ambiguous Grammar 254
5.5.5 Removal of Ambiguity 254
5.5.6 Context-Free Grammar Simplification 254
5.5.7 Chomsky Normal Form 256
5.5.8 Greibach Normal Form 256
5.5.9 Identification of Language 256
5.6 Turing Machine 256
5.6.1 Model of a Turing Machine 257
5.6.2 Designing a Turing Machine 258
5.6.3 Recursive and Recursive Enumerable Languages 258
5.6.4 Variation of Turing Machine 258
5.7 Closure and Decidability 258
Important Formulas 260
Solved Examples 260
GATE Previous Years’ Questions 263
Practice Exercises 276
Answers to Practice Exercises 282
6 Compiler Design 287
6.1 Introduction 287
6.2 Compilers and Interpreters 287
6.2.1 Compiler 287
xviii  CONTENTS
6.2.2 Interpreter 288
6.2.3 Phases of a Compiler 288
6.2.4 Grouping of Phases 290
6.3 Lexical Analyzer 290
6.3.1 Functions of a Lexical Analyzer 290
6.3.2 Implementation of a Lexical Analyzer 290
6.4 Parser 291
6.4.1 Context-Free Grammar 292
6.4.2 Derivation Tree or Parse Tree 292
6.4.3 Ambiguous Grammar 293
6.4.4 Top-Down Parser 293
6.4.5 Bottom-Up Parser 297
6.5 Syntax-Directed Translation 302
6.5.1 Attributes of Syntax-Directed Translation 302
6.5.2 Types of Syntax-Directed Translation 302
6.5.3 Applications of SDT 302
6.6 Runtime Environment 303
6.6.1 Storage Organization 303
6.6.2 Activation Record and Activation Trees 304
6.6.3 Procedure Call Return Model 304
6.6.4 Lexical Versus Dynamic Scoping 305
6.6.5 Symbol Table 305
6.7 Intermediate Code Generation 305
6.7.1 Intermediate Representations 305
6.8 Code Optimization 307
6.8.1 Types and Levels of Optimization 307
6.8.2 Primary Source of Optimization 307
Important Formulas 308
Solved Examples 309
GATE Previous Years’ Questions 310
Practice Exercises 318
Answers to Practice Exercises 323
7 Operating System 327
7.1 Introduction 327
7.2 Types of Operating System 328
7.2.1 Batch Operating System 328
7.2.2 Multiprogramming Operating System 328
7.2.3 Multitasking Operating System 328
7.2.4 Multiprocessor Operating System 328
7.2.5 Real-Time Operating System 329
7.3 Process Management 329
7.3.1 Process 329
7.3.2 Schedulers 330
7.4 CPU Scheduling 331
7.4.1 Scheduling Algorithms 331
CONTENTS xix
7.5 Process Synchronization 335
7.5.1 Types of Processes 335
7.5.2 Interprocess Communication 336
7.5.3 Classical Synchronization Problems 336
7.5.4 Race Condition 336
7.5.5 Critical Section 337
7.5.6 Peterson’s Algorithm for Two Processes 337
7.5.7 Semaphores 338
7.5.8 Deadlock and Starvation 339
7.6 Deadlocks 339
7.6.1 Resource Types 340
7.6.2 Characteristics of a Deadlock 340
7.6.3 Resource Allocation Graph 340
7.6.4 Deadlock Prevention 341
7.6.5 Deadlock Avoidance 342
7.6.6 Deadlock Detection and Recovery 346
7.7 Threads 347
7.7.1 Benefits of Threads 347
7.7.2 Types of Threads 347
7.8 Memory Management 348
7.8.1 Partitioning 348
7.8.2 Partition Allocation Policies 348
7.8.3 Loading and Linking 349
7.8.4 Paging 350
7.8.5 Multi-Level Paging 352
7.8.6 Segmentation 354
7.8.7 Virtual Memory 355
7.8.8 Page Replacement Algorithms 355
7.9 File System 359
7.9.1 Directory Structures 359
7.9.2 Allocation Methods 359
7.10 I/O Systems 363
7.10.1 Disk Structure 363
7.10.2 Disk Scheduling Algorithms 366
7.11 Protection and Security 368
7.11.1 Security 368
7.11.2 Security Environment 369
7.11.3 Cryptography 369
7.11.4 Attacks from within the System 370
7.11.5 Attacks from Outside the System 370
7.11.6 Anti Virus Approaches 371
Important Formulas 371
Solved Examples 372
GATE Previous Years’ Questions 374
Practice Exercises 391
Answers to Practice Exercises 398
xx  CONTENTS
8 Databases 403
8.1 Introduction 403
8.1.1 Traditional File Processing Approach 403
8.1.2 Database Management System 404
8.2 Components of Database Systems 404
8.3 DBMS Architecture 405
8.3.1 3-Tier Architecture 405
8.3.2 Data Independence 405
8.4 Data Models 405
8.4.1 Relational Model 406
8.4.2 ER Model 407
8.5 Database Design 410
8.5.1 Integrity Constraints 410
8.5.2 Normal Forms 411
8.5.3 Attribute Closure 411
8.5.4 Key 411
8.5.5 Decomposition 412
8.6 Query Languages (SQL) 414
8.6.1 SQL Commands 414
8.7 File Structures 416
8.7.1 Sequential Files 416
8.7.2 Indexing 416
8.7.3 B Tree 416
8.7.4 B+ Trees 416
8.8 Transactions and Concurrency Control 417
8.8.1 Transactions 417
8.8.2 Schedule 417
8.8.3 Classification of Schedule Based on Recoverability 419
8.8.4 Classification of Schedule Based on Serializability 420
8.8.5 Concurrency Control Protocol 423
Important Formulas 424
Solved Examples 425
GATE Previous Years’ Questions 427
Practice Exercises 444
Answers to Practice Exercises 449
9 Information Systems and Software Engineering 453
9.1 Introduction 453
9.2 Information Systems 453
9.2.1 Components of Information Systems 454
9.2.2 Types of Information Systems 454
9.3 Software 456
9.3.1 Characteristics of Software 456
9.3.2 Software Engineering 457
9.4 Process Models 458
9.4.1 Conventional Process Model 458
9.4.2 Evolutionary Process Model 459
CONTENTS xxi
9.5 Measurement of Metrics 461
9.5.1 Metrics 461
9.5.2 Size-Oriented Metrics 462
9.5.3 Effort and Schedule (Duration) Estimation 463
9.6 Risk Analysis 466
9.6.1 Risk Identification 466
9.6.2 Risk Projection or Risk Estimation 466
9.7 Software Development Life Cycle 467
9.7.1 Requirement 467
9.7.2 Design 470
9.7.3 Coding 472
9.7.4 Testing 472
Important Formulas 477
Solved Examples 477
GATE Previous Years’ Questions 479
Practice Exercises 483
Answers to Practice Exercises 487
10 Computer Networks 491
10.1 Introduction 491
10.2 Network 491
10.2.1 Network Topology 492
10.3 LAN Technologies 492
10.3.1 Ethernet 492
10.3.2 Token Bus 493
10.3.3 Token Ring 493
10.4 ISO/OSI Stack 494
10.4.1 ISO/OSI Model 494
10.5 Routing Algorithms 498
10.6 Network Layer Protocols 501
10.6.1 Internet Protocol (IPv4) 501
10.6.2 ICMP 505
10.7 Layer 4: Transport Layer 505
10.8 Congestion 505
10.8.1 Congestion Versus Flow Control 506
10.9 User Datagram Protocol and Transmission Control Protocol 506
10.9.1 User Datagram Protocol 506
10.9.2 Transmission Control Protocol 506
10.10 Sockets 507
10.11 Layer 5: Session Layer 507
10.12 Layer 6: Presentation Layer 508
10.13 Layer 7: Application Layer 508
10.14 Devices 509
10.15 Network Security 510
10.15.1 Basic Concepts in Cryptography 510
10.15.2 Digital Signature 511
10.15.3 Firewall 511
xxii  CONTENTS
Important Formulas 512
Solved Examples 513
GATE Previous Years’ Questions 515
Practice Exercises 527
Answers to Practice Exercises 532
11 Web Technologies 537
11.1 Introduction 537
11.2 HTML 538
11.2.1 HTML Tags 538
11.2.2 HTML Attributes 538
11.2.3 HTML Elements 539
11.2.4 HTML Character Entities 539
11.2.5 HTML Formatting 539
11.2.6 HTML Phrase Tags 540
11.2.7 HTML Background 540
11.2.8 HTML Lists 540
11.2.9 HTML Links 540
11.2.10 HTML Images 540
11.2.11 HTML Tables 540
11.2.12 HTML Frames 541
11.2.13 HTML Forms 541
11.2.14 HTML Marquees 541
11.3 Cascading Style Sheets 541
11.4 XML 541
11.4.1 Advantages of XML 542
11.4.2 Document-Type Definition 542
11.4.3 Tag Rules for XML Documents 542
11.4.4 Types of XML Documents 543
11.4.5 XHTML 543
11.4.6 Document Object Model (DOM) 543
11.4.7 XUL 543
11.4.8 Flash and Silverlight 543
11.4.9 User-Interface Language 543
11.5 Basic Concepts of Client— Server Computing 544
11.5.1 Server Types 544
11.5.2 Stateless and Stateful Servers 544
11.5.3 Thin Client and Fat Servers 544
11.5.4 Functions of a Client 544
11.5.5 Functions of a Server 544
11.5.6 Topologies for Client-Server 545
11.5.7 Types of Client-Server Model 545
11.5.8 Merits and Demerits of Client-Server 546
11.6 J2EE platform 546
11.6.1 J2EE Services 546
11.6.2 J2EE Architecture 547
11.6.3 EJB Container 547
11.6.4 J2EE Application Server 547
CONTENTS xxiii
Important Formulas 547
Solved Examples 548
GATE Previous Years’ Questions 550
Practice Exercises 551
Answers to Practice Exercises 554
Solved GATE (CS) 2014 Set 1 555
Solved GATE (CS) 2014 Set 2 567
Solved GATE (CS) 2014 Set 3 579
Solved GATE (CS) 2015 Set 1 591
Solved GATE (CS) 2015 Set 2 605
Solved GATE (CS) 2015 Set 3 617
Index 631