Table of Contents
Table of Contents 1
Contributors 5
1 Algorithms (183) 6
1.1 Algorithm Design Techniques (1) 7
1.2 Asymptotic Notations (15) 7
1.3 Binary Heap (1) 9
1.4 Breadth First Search (3) 9
1.5 Bucket Sort (5) 10
1.6 Countingsort (4) 10
1.7 Divide And Conquer (4) 11
1.8 Graph Algorithms (7) 12
1.9 Hashing (21) 13
1.10 Heap (23) 15
1.11 Heap Sort (5) 19
1.12 Inversion (4) 20
1.13 Kruskals Algorithm (1) 21
1.14 Linked List (8) 21
1.15 Master Theorem (7) 22
1.16 Merge Sort (2) 23
1.17 Priority Queue (1) 23
1.18 Queue (4) 23
1.19 Quick Sort (16) 24
1.20 Radix Sort (3) 27
1.21 Recurrence Relation (19) 27
1.22 Searching (4) 29
1.23 Sorting (5) 30
1.24 Stablesort (1) 30
1.25 Stack (3) 31
1.26 Time Complexity (3) 31
1.27 Tree (1) 32
Answer Keys 32
2 CO and Architecture (2) 34
2.1 Input Output (1) 34
2.2 Machine Instructions (1) 34
Answer Keys 34
3 Compiler Design (124) 35
3.1 Ambiguous Grammar (1) 37
3.2 Annotated Parse Trees (1) 37
3.3 Bottom Up Parses (1) 37
3.4 Compiler Tokenization (2) 37
3.5 Conjunctive Normal Form (1) 38
3.6 Context Free Grammar (9) 38
3.7 Cyk Algorithm (1) 40
3.8 Dependency Graph (1) 40
3.9 Directed Acyclic Graph (2) 40
3.10 First And Follow (2) 41
3.11 Grammar (15) 41
3.12 Infix Expressions (1) 45
3.13 Left Recursion (4) 45
3.14 Lexemes (2) 46
3.15 Lexical Analyzer (3) 46
3.16 Ll Parser (2) 47
3.17 Lr Parser (5) 47
3.18 Parsing (1) 48
3.19 Postfix Notation (1) 48
3.20 Predictive Parser (2) 48
3.21 Recursive Descent Parser (2) 49
, 3.22 Regular Expression (9) 50
3.23 Slr Item (2) 52
3.24 Strings (1) 52
3.25 Syntax Directed Translation (19) 52
3.26 Three Address Code (18) 57
3.27 Viable Prefix (1) 62
3.28 Yacc (4) 62
Answer Keys 63
4 Computer Networks (76) 64
4.1 Error Correction (3) 76
4.2 Link State Routing (1) 76
4.3 Routers Bridge Hubs Switches (1) 76
Answer Keys 77
5 Databases (107) 78
5.1 Database Design (25) 79
5.2 Rdbms (1) 83
5.3 Relational Calculus (5) 84
5.4 Relational Model (64) 84
5.5 Tuple Relational Calculus (2) 100
Answer Keys 101
6 Discrete Mathematics: Combinatory (416) 102
6.1 Binomial Theorem (39) 102
6.2 Counting (329) 107
6.3 Generating Functions (1) 156
6.4 Pigeonhole Principle (47) 157
Answer Keys 162
7 Discrete Mathematics: Graph Theory (1) 165
Answer Keys 165
8 Discrete Mathematics: Mathematical Logic (222) 166
8.1 First Order Logic (1) 172
8.2 Logical Reasoning (1) 172
8.3 Propositional Logic (184) 172
Answer Keys 201
9 Discrete Mathematics: Set Theory & Algebra (236) 203
Answer Keys 235
10 Engineering Mathematics: Probability (89) 237
10.1 Conditional Probability (8) 244
10.2 Normal Distribution (1) 245
10.3 Random Variable (27) 245
Answer Keys 249
11 Operating System (600) 250
11.1 Bankers Algorithm (1) 258
11.2 Bitmaps (1) 258
11.3 Cache Memory (1) 259
11.4 Contiguous Allocation (1) 259
11.5 Cylinders (2) 259
11.6 Deadlock Prevention Avoidance Detection (62) 259
11.7 Dining Philosophers Problem (1) 273
11.8 Disk (14) 273
11.9 Disk Controller (1) 276
11.10 Disk Scheduling (7) 276
11.11 File Allocation Table (2) 277
11.12 File Organization (1) 278
11.13 File System (55) 278
11.14 Fragmentation (1) 286
11.15 Hard Disk (1) 286
11.16 I Node (1) 286
11.17 Input Output (50) 287
, 11.18 Instruction Format (1) 296
11.19 Interrupt Driven (1) 296
11.20 Inverted Page Table (1) 296
11.21 Io System (17) 296
11.22 Kernel Mode (1) 299
11.23 Kernel User Mode (1) 299
11.24 Least Recently Used (1) 299
11.25 Memory (1) 299
11.26 Memory Management (37) 299
11.27 Memory Mapped (2) 305
11.28 Monitors (1) 306
11.29 Multi Programming (1) 306
11.30 Multilevel Paging (1) 306
11.31 Multiplexing (1) 306
11.32 Multiprocessors (2) 306
11.33 Multithreaded (2) 307
11.34 Mutual Exclusion (1) 307
11.35 Page Fault (10) 308
11.36 Page Replacement (14) 310
11.37 Paging (14) 313
11.38 Preemptable Nonpreemptable (1) 316
11.39 Process (18) 316
11.40 Process And Threads (54) 320
11.41 Process Scheduling (28) 328
11.42 Process Synchronization (31) 332
11.43 Program (2) 337
11.44 Race Conditions (1) 337
11.45 Resource Allocation (2) 337
11.46 Round Robin Scheduling (2) 338
11.47 Segmentation (2) 338
11.48 Semaphore (1) 338
11.49 Shared System (1) 339
11.50 Starvation (1) 339
11.51 System Call (7) 339
11.52 Threads (15) 340
11.53 Timesharing System (1) 342
11.54 Translation Lookaside Buffer (8) 343
11.55 Trap Instruction (1) 344
11.56 Unix (8) 344
11.57 Virtual Machines (1) 345
11.58 Virtual Memory (34) 346
Answer Keys 352
12 Theory of Computation (793) 356
12.1 Ambiguous Grammar (1) 357
12.2 Closure Property (31) 358
12.3 Computability (1) 362
12.4 Conjunctive Normal Form (3) 362
12.5 Context Free Grammar (100) 362
12.6 Context Free Language (36) 378
12.7 Countable Uncountable Set (2) 383
12.8 Decidability (70) 383
12.9 Dpda (1) 392
12.10 Enumerated Language (1) 392
12.11 Finite Automata (19) 392
12.12 Finite State Transducer (2) 396
12.13 Fst (2) 396
12.14 Functions (1) 397
12.15 Gnf (5) 397
12.16 Grammar (28) 397
12.17 Homomorphism (1) 402
, 12.18 Inherently Ambiguous (4) 402
12.19 Legitimate Turing Machine (1) 403
12.20 Non Determinism (1) 403
12.21 Npda (27) 403
12.22 Parse Trees (1) 408
12.23 Perfect Shuffle (2) 408
12.24 Peter Linz (99) 408
12.25 Pigeonhole Principle (1) 423
12.26 Polynomials (1) 424
12.27 Post Correspondence Problem (6) 424
12.28 Prefix Free Property (2) 424
12.29 Pumping Lemma (45) 425
12.30 Pushdown Automata (12) 431
12.31 Recursive And Recursively Enumerable Languages (53) 433
12.32 Reduction (7) 441
12.33 Regular Expression (49) 442
12.34 Regular Grammar (17) 449
12.35 Regular Language (27) 452
12.36 Relations (1) 456
12.37 Rice Theorem (3) 456
12.38 Rotational Closure Of Language (1) 457
12.39 Scarnes Cut (1) 457
12.40 Set Theory (3) 457
12.41 Shuffle (1) 458
12.42 Simplification (1) 458
12.43 State Diagram (7) 458
12.44 Suffix Operation (1) 460
12.45 Synchronizable Dfa (1) 460
12.46 Transducer (1) 460
12.47 Turing Machine (103) 461
Answer Keys 476
Table of Contents 1
Contributors 5
1 Algorithms (183) 6
1.1 Algorithm Design Techniques (1) 7
1.2 Asymptotic Notations (15) 7
1.3 Binary Heap (1) 9
1.4 Breadth First Search (3) 9
1.5 Bucket Sort (5) 10
1.6 Countingsort (4) 10
1.7 Divide And Conquer (4) 11
1.8 Graph Algorithms (7) 12
1.9 Hashing (21) 13
1.10 Heap (23) 15
1.11 Heap Sort (5) 19
1.12 Inversion (4) 20
1.13 Kruskals Algorithm (1) 21
1.14 Linked List (8) 21
1.15 Master Theorem (7) 22
1.16 Merge Sort (2) 23
1.17 Priority Queue (1) 23
1.18 Queue (4) 23
1.19 Quick Sort (16) 24
1.20 Radix Sort (3) 27
1.21 Recurrence Relation (19) 27
1.22 Searching (4) 29
1.23 Sorting (5) 30
1.24 Stablesort (1) 30
1.25 Stack (3) 31
1.26 Time Complexity (3) 31
1.27 Tree (1) 32
Answer Keys 32
2 CO and Architecture (2) 34
2.1 Input Output (1) 34
2.2 Machine Instructions (1) 34
Answer Keys 34
3 Compiler Design (124) 35
3.1 Ambiguous Grammar (1) 37
3.2 Annotated Parse Trees (1) 37
3.3 Bottom Up Parses (1) 37
3.4 Compiler Tokenization (2) 37
3.5 Conjunctive Normal Form (1) 38
3.6 Context Free Grammar (9) 38
3.7 Cyk Algorithm (1) 40
3.8 Dependency Graph (1) 40
3.9 Directed Acyclic Graph (2) 40
3.10 First And Follow (2) 41
3.11 Grammar (15) 41
3.12 Infix Expressions (1) 45
3.13 Left Recursion (4) 45
3.14 Lexemes (2) 46
3.15 Lexical Analyzer (3) 46
3.16 Ll Parser (2) 47
3.17 Lr Parser (5) 47
3.18 Parsing (1) 48
3.19 Postfix Notation (1) 48
3.20 Predictive Parser (2) 48
3.21 Recursive Descent Parser (2) 49
, 3.22 Regular Expression (9) 50
3.23 Slr Item (2) 52
3.24 Strings (1) 52
3.25 Syntax Directed Translation (19) 52
3.26 Three Address Code (18) 57
3.27 Viable Prefix (1) 62
3.28 Yacc (4) 62
Answer Keys 63
4 Computer Networks (76) 64
4.1 Error Correction (3) 76
4.2 Link State Routing (1) 76
4.3 Routers Bridge Hubs Switches (1) 76
Answer Keys 77
5 Databases (107) 78
5.1 Database Design (25) 79
5.2 Rdbms (1) 83
5.3 Relational Calculus (5) 84
5.4 Relational Model (64) 84
5.5 Tuple Relational Calculus (2) 100
Answer Keys 101
6 Discrete Mathematics: Combinatory (416) 102
6.1 Binomial Theorem (39) 102
6.2 Counting (329) 107
6.3 Generating Functions (1) 156
6.4 Pigeonhole Principle (47) 157
Answer Keys 162
7 Discrete Mathematics: Graph Theory (1) 165
Answer Keys 165
8 Discrete Mathematics: Mathematical Logic (222) 166
8.1 First Order Logic (1) 172
8.2 Logical Reasoning (1) 172
8.3 Propositional Logic (184) 172
Answer Keys 201
9 Discrete Mathematics: Set Theory & Algebra (236) 203
Answer Keys 235
10 Engineering Mathematics: Probability (89) 237
10.1 Conditional Probability (8) 244
10.2 Normal Distribution (1) 245
10.3 Random Variable (27) 245
Answer Keys 249
11 Operating System (600) 250
11.1 Bankers Algorithm (1) 258
11.2 Bitmaps (1) 258
11.3 Cache Memory (1) 259
11.4 Contiguous Allocation (1) 259
11.5 Cylinders (2) 259
11.6 Deadlock Prevention Avoidance Detection (62) 259
11.7 Dining Philosophers Problem (1) 273
11.8 Disk (14) 273
11.9 Disk Controller (1) 276
11.10 Disk Scheduling (7) 276
11.11 File Allocation Table (2) 277
11.12 File Organization (1) 278
11.13 File System (55) 278
11.14 Fragmentation (1) 286
11.15 Hard Disk (1) 286
11.16 I Node (1) 286
11.17 Input Output (50) 287
, 11.18 Instruction Format (1) 296
11.19 Interrupt Driven (1) 296
11.20 Inverted Page Table (1) 296
11.21 Io System (17) 296
11.22 Kernel Mode (1) 299
11.23 Kernel User Mode (1) 299
11.24 Least Recently Used (1) 299
11.25 Memory (1) 299
11.26 Memory Management (37) 299
11.27 Memory Mapped (2) 305
11.28 Monitors (1) 306
11.29 Multi Programming (1) 306
11.30 Multilevel Paging (1) 306
11.31 Multiplexing (1) 306
11.32 Multiprocessors (2) 306
11.33 Multithreaded (2) 307
11.34 Mutual Exclusion (1) 307
11.35 Page Fault (10) 308
11.36 Page Replacement (14) 310
11.37 Paging (14) 313
11.38 Preemptable Nonpreemptable (1) 316
11.39 Process (18) 316
11.40 Process And Threads (54) 320
11.41 Process Scheduling (28) 328
11.42 Process Synchronization (31) 332
11.43 Program (2) 337
11.44 Race Conditions (1) 337
11.45 Resource Allocation (2) 337
11.46 Round Robin Scheduling (2) 338
11.47 Segmentation (2) 338
11.48 Semaphore (1) 338
11.49 Shared System (1) 339
11.50 Starvation (1) 339
11.51 System Call (7) 339
11.52 Threads (15) 340
11.53 Timesharing System (1) 342
11.54 Translation Lookaside Buffer (8) 343
11.55 Trap Instruction (1) 344
11.56 Unix (8) 344
11.57 Virtual Machines (1) 345
11.58 Virtual Memory (34) 346
Answer Keys 352
12 Theory of Computation (793) 356
12.1 Ambiguous Grammar (1) 357
12.2 Closure Property (31) 358
12.3 Computability (1) 362
12.4 Conjunctive Normal Form (3) 362
12.5 Context Free Grammar (100) 362
12.6 Context Free Language (36) 378
12.7 Countable Uncountable Set (2) 383
12.8 Decidability (70) 383
12.9 Dpda (1) 392
12.10 Enumerated Language (1) 392
12.11 Finite Automata (19) 392
12.12 Finite State Transducer (2) 396
12.13 Fst (2) 396
12.14 Functions (1) 397
12.15 Gnf (5) 397
12.16 Grammar (28) 397
12.17 Homomorphism (1) 402
, 12.18 Inherently Ambiguous (4) 402
12.19 Legitimate Turing Machine (1) 403
12.20 Non Determinism (1) 403
12.21 Npda (27) 403
12.22 Parse Trees (1) 408
12.23 Perfect Shuffle (2) 408
12.24 Peter Linz (99) 408
12.25 Pigeonhole Principle (1) 423
12.26 Polynomials (1) 424
12.27 Post Correspondence Problem (6) 424
12.28 Prefix Free Property (2) 424
12.29 Pumping Lemma (45) 425
12.30 Pushdown Automata (12) 431
12.31 Recursive And Recursively Enumerable Languages (53) 433
12.32 Reduction (7) 441
12.33 Regular Expression (49) 442
12.34 Regular Grammar (17) 449
12.35 Regular Language (27) 452
12.36 Relations (1) 456
12.37 Rice Theorem (3) 456
12.38 Rotational Closure Of Language (1) 457
12.39 Scarnes Cut (1) 457
12.40 Set Theory (3) 457
12.41 Shuffle (1) 458
12.42 Simplification (1) 458
12.43 State Diagram (7) 458
12.44 Suffix Operation (1) 460
12.45 Synchronizable Dfa (1) 460
12.46 Transducer (1) 460
12.47 Turing Machine (103) 461
Answer Keys 476
