gate-computer-science-and-information-technology-2019-9789352868469-9789353061166-9352868463_compress-1-578.pdf

 About Pearson Pearson is the world’s learning company, with presence across 70 countries worldwide. Our unique insights and world-class expertise comes from a long history of working closely with renowned teachers, authors and thought leaders, as a result of which, we have emer...

 About Pearson Pearson is the world’s learning company, with presence across 70 countries worldwide. Our unique insights and world-class expertise comes from a long history of working closely with renowned teachers, authors and thought leaders, as a result of which, we have emerged as the preferred choice for millions of teachers and learners across the world. We believe learning opens up opportunities, creates fulfilling careers and hence better lives. We hence collaborate with the best of minds to deliver you class-leading products, spread across the Higher Education and K12 spectrum. Superior learning experience and improved outcomes are at the heart of everything we do. This product is the result of one such effort. Your feedback plays a critical role in the evolution of our products and you can contact us at [email protected]. We look forward to it. This page is intentionally left blank  GATE (Graduate Aptitude Test in Engineering) Computer Science and Information Technology Trishna Knowledge Systems Copyright © 2017 Trishna Knowledge System Published by Pearson India Education Services Pvt. Ltd, CIN: U72200TN2005PTC057128, formerly known as TutorVista Global Pvt. Ltd, licensee of Pearson Education in South Asia. No part of this eBook may be used or reproduced in any manner whatsoever without the publisher’s prior written consent. This eBook may or may not include all assets that were part of the print version. The publisher reserves the right to remove any material in this eBook at any time. ISBN 978-93-528-6846-9 eISBN 978-93-530-6116-6 Head Office: 15th Floor, Tower-B, World Trade Tower, Plot No. 1, Block-C, Sector 16, Noida 201 301, Uttar Pradesh, India. Registered Office: 4th Floor, Software Block, Elnet Software City, TS-140, Block 2 & 9, Rajiv Gandhi Salai, Taramani, Chennai 600 113, Tamil Nadu, India. Fax: 080-30461003, Phone: 080-30461060 www.pearson.co.in, Email: [email protected] Contents Preface ix Key Pedagogical Features x Syllabus: Computer Science and Information Technology xii Chapter-wise Analysis of GATE Previous Years’ Papers xiii General Information about Gate xiv Solved Papers 2017 xvi solved PaPers 2018 l i PART I General Aptitude PART A  Verbal Ability Chapter 1 Grammar 1.5 Chapter 2 Vocabulary 1.49 PART B  Numerical Ability UNIT I  Quantitative Aptitude 1.71 Chapter 1 Simple Equations 1.73 Chapter 2 Ratio-Proportion-Variation 1.79 Chapter 3 Numbers 1.85 Chapter 4 Percentage, Profit and Loss 1.99 Chapter 5 Simple Interest and Compound Interest 1.106 Chapter 6 Average, Mixtures, Alligations 1.112 Chapter 7 Time and Work 1.118 Chapter 8 Time and Distance 1.124 Chapter 9 Indices, Surds, and Logarithms 1.130 Chapter 10 Quadratic Equations 1.136 Chapter 11 Inequalities 1.142 Chapter 12 Progressions 1.146 Chapter 13 Permutations and Combinations 1.151 Chapter 14 Data Interpretation 1.158 UNIT II Reasoning 1.177 Chapter 1 Number and Letter Series 1.179 Chapter 2 Analogies 1.185 Chapter 3 Odd Man Out (Classification) 1.188 Chapter 4 Coding and Decoding 1.191 Chapter 5 Blood Relations 1.195 Chapter 6 Venn Diagrams 1.200 vi | Contents Chapter 7 Seating Arrangements 1.204 Chapter 8 Puzzles 1.212 Chapter 9 Clocks and Calenders 1.225 PART I1 Engineering Mathematics Chapter 1 Mathematical Logic 2.237 Chapter 2 Probability 2.250 Chapter 3 Set Theory and Algebra 2.266 Chapter 4 Combinatorics 2.287 Chapter 5 Graph Theory 2.299 Chapter 6 Linear Algebra 2.317 Chapter 8 Calculus 2.333 PART III Computer Science and Information Technology UNIT 1 Digital Logic 3.351 Chapter 1 Number Systems 3.353 Chapter 2 Boolean Algebra and Minimization of Functions 3.364 Chapter 3 Combinational Circuits 3.384 Chapter 4 Sequential Circuits 3.405 UNIT II Computer Organization and Architecture 3.433 Chapter 1 Machine Instructions, Addressing Modes 3.435 Chapter 2 ALU and Data Path, CPU Control Design 3.448 Chapter 3 Memory Interface, I/O Interface 3.464 Chapter 4 Instruction Pipelining 3.478 Chapter 5 Cache and Main Memory, Secondary Storage 3.490 UNIT III  Programming and Data Structures 3.507 PART A  Programming and Data Structures Chapter 1 Programming in C 3.509 Chapter 2 Functions 3.520 Chapter 3 Arrays, Pointers and Structures 3.535 Chapter 4 Linked Lists, Stacks and Queues 3.551 Chapter 5 Trees 3.564  Contents | vii PART B  Algorithms Chapter 1 Asymptotic Analysis 3.585 Chapter 2 Sorting Algorithms 3.601 Chapter 3 Divide and Conquer 3.610 Chapter 4 Greedy Approach 3.618 Chapter 5 Dynamic Programming 3.637 UNIT 1V Databases 3.657 Chapter 1 ER Model and Relational Model 3.659 Chapter 2 Structured Query Language 3.677 Chapter 3 Normalization 3.704 Chapter 4 Transaction and Concurrency 3.719 Chapter 5 File Management 3.736 UNIT V  Theory of Computation 3.753 Chapter 1 Finite Automata and Regular Languages 3.755 Chapter 2 Context Free Languages and Push Down Automata 3.776 Chapter 3 Recursively Enumerable Sets and Turing Machines, Decidability 3.788 UNIT V1 Compiler Design 3.803 Chapter 1 Lexical Analysis and Parsing 3.805 Chapter 2 Syntax Directed Translation 3.828 Chapter 3 Intermediate Code Generation 3.837 Chapter 4 Code Optimization 3.856 UNIT VII Operating System 3.873 Chapter 1 Processes and Threads  3.875 Chapter 2 Interprocess Communication, Concurrency and Synchronization  3.889 Chapter 3 Deadlock and CPU Scheduling 3.907 Chapter 4 Memory Management and Virtual Memory 3.925 Chapter 5 File Systems, I/O Systems, Protection and Security 3.945 viii | Contents UNIT VIII Networks, Information Systems, Software Engineering and Web Technology 3.969 Part A  Network Chapter 1 OSI Layers 3.971 Chapter 2 Routing Algorithms 3.991 Chapter 3 TCP/UDP 3.1003 Chapter 4 IP(V4) 3.1018 Chapter 5 Network Security 3.1032 Part B  Information Systems Chapter 1 Process Life Cycle 3.1045 Chapter 2 Project Management and Maintenance 3.1055 Part C  Software Engineering and Web Technology Chapter 1 Markup Languages 3.1077 Preface Graduate Aptitude Test in Engineering (GATE) is one of the preliminary tests for undergraduate subjects in Engineering/ Technology/Architecture and postgraduate subjects in Science stream only. The number of aspirants appearing for the GATE examination is increasing significantly every year, owing to multifac- eted opportunities open to any good performer. Apart from giving the aspirant a chance to pursue an M.Tech. from insti- tutions like the IITs /NITs, a good GATE score can be highly instrumental in landing the candidate a plush public sector job, as many PSUs are recruiting graduate engineers on the basis of their performance in GATE. The GATE examination pattern has undergone several changes over the years—sometimes apparent and sometimes subtle. It is bound to continue to do so with changing technological environment. GATE Computer Science and Information Technology, as a complete resource helps the aspirants be ready with con- ceptual understanding, and enables them to apply these concepts in various applications, rather than just proficiency with questions type. Topics are handled in a comprehensive manner, beginning with the basics and progressing in a step-by-step manner along with a bottom-up approach. This allows the student to better understand the concept and to practice applica- tive techniques in a focused manner. The content has been systematically organized to facilitate easy understanding of all topics. The given examples will not only help the students to understand the concepts involved in the problems but also help to get a good idea about the different models of problems on that particular topic. Due care has also been taken to cover a very wide range of problems including questions that have been appearing over the last few years in GATE examination. The practice exercises in every chapter, contain questions ranging simple to moderate to difficult level. These exercises are meant to hone the examination readiness over a period of time. At the end of each unit, practice tests have been placed. These tests will help the student assess their level of learning on a regular interval. This book has been prepared by a group of faculty who are highly experienced in training GATE preparations and are also subject matter experts. As a result, this book would serve as an effective tool for GATE aspirant to crack the examination. Salient Features 1. Elaborate question bank covering previous 12 years’ GATE question papers 2. 5 free online mock tests for practice 3. Detailed coverage of key topics 4. Complete set of solved 2017 GATE online papers with chapter-wise analysis 5. Exhaustive pedagogy: (a) More than 1300 Solved Examples (b) More than 6000 Practice Questions (c) Unit-wise time-bound tests (d) Modular approach for easy understanding We would like to thank the below mentioned reviewers for their valuable feedback and suggestions which has helped in shaping this book. R. Marudhachalam Professor (Sr. Grade), Kumaraguru College of Technology Coimbatore, Tamil Nadu Daya Gupta Professor, Delhi Technological University, Main Bawana Road, Delhi Manoj Kumar Gupta Associate Professor, Delhi Technological University Main Bawana Road, Delhi Gurpreet Kour Lecturer, Lovely Professional University Phagwara, Punjab Pinaki Chakraborty Assistant Professor, Netaji Subhas Institute of Technology Dwarka, Delhi Gunit Kaur Lecturer, Lovely Professional University Phagwara, Punjab Despite of our best efforts, some errors may have inadvertently crept into the book. Constructive comments and suggestions to further improve the book are welcome and shall be acknowledged gratefully. Wishing you all the very best..!!! —Trishna Knowledge Systems  Chapter 1 Key Pedagogical Features Number Systems 3.536 | Digital Logic BCD addition Excess-3 (XS-3) code BCD addition is performed by individually adding the Excess-3 code is a non-weighted BCD code, where each corresponding digits of the decimal number expressed in digit binary code word is the corresponding 8421 code word Learning Objectives 4-bit binary groups LEARNING starting from the LSB. OBJECTIVES plus 0011. If there is no carry and the sum term is not an illegal code, Find the XS-3 code of List of important top- no correction After is needed. reading this chapter, you will be able to understand: Example 47: (3)10 → (0011)BCD = (0110)xS3 ics which are covered in If there is a carry out of one group to the next group or if Digital circuits Chapter Example Weighted 2 (16) 48:and Boolean → (0001 Algebra non-weighted codes 0110) and Minimization of Functions | 29 the sum term is an illegal code, the (6)10 is added to the chapter. 10 BCD sum Number term system with different of that group, and thebase resulting carry is added Error detection and→correction (0100 1001) code xS3 toConversion of number systems the next group. Sequential, reflective and cyclic codes Gray code Complements Y = (code Self complementing A ⋅ B ⋅ AB) = ( A + Bnumber Each gray code number differs from the preceding ) (A+ B)  ( A ⋅ B = A + B) Solution: =Subtraction {A ⊕43:B44⊕ fExample +B with12 ⊕ C } ⊕ {A ⊕ C complement ⊕ B ⊕ A} by a single bit. 0100 0100 (44 in BCD) Numeric codes = {A ⊕ 0 ⊕ C} ⊕ 0001 0010 ⊕inCBCD) {0(12 ⊕ B} = ( A + BGray Decimal ) + (Code A + B) = A ⋅ B + A ⋅ B 0 0000 0101 0110 (56 in BCD) =A⊕C⊕C⊕B=A⊕0⊕B=A⊕B = 1A ⋅ B + A0001 ⋅ B = A⊕ B Example 44: 76.9+ 56.6 2 0011 DIGITAL CIRCUITS 0111 0110. 1001 Example Example 5: (658)8 = 6 ×3 84: 2 + 5Simplify + 8 × 80 the × 81 0010 Boolean function A ⊕ A B ⊕ A 0101 0110. 0110 Computers work with binary numbers, which (all Solved Examples use are onlyillegal the digits Solved = 384Example 4 + 40 + 8 = 0110 Chapter (432)10 1 Number Systems | 13 ‘0’ and ‘1’. Since all the1100 digital1100. 1111 are based components codes) on binary Solution: Solved 5 ⊕ A Bgiven Asystem problems 0111 ⊕ A topic-wise operations, it is convenient0110 0110 to use binary numbers when analyzing Hexadecimal. 0110 Binary to gray number conversion Example (A) 11001001 1: Simplify the(B) Boolean 0010 or designing digital circuits. 10011100 function, 0010. 0101 x y + x′z + code.y In z ForI: example, hexadecimal Step Shifttothe learn number binary to -6 the system, base number number apply there 35 will 16the areposition one numbers 0be the rep- toconcepts toright, 9, and (C) 11010101 (D) +1 10101101 +1 +1 (propagate carry)resenteddigits bytheits from 10 BCH code to 15 number are Associativity 011101. represented by A to F, respectively. The LSB of shifted is discarded. Solution:Number x y + x′Systems z+ y z 0001 with 0011 Different 0011.Base 0101 Inbase learned in a of hexadecimal number system is 16. particular section as 4. Let r denotes number system’s1radix. The3only value(s) Stepthis numbering II: Exclusive or the system, bits = ⊕ of1the the AB binary=BCH A B number code with By using consensus Decimal number property system 3. 5 001001101011 Example those of the per exam corresponds 6: (1A5C) binary number pattern. = 1 × 16 3 to × 16following + Athe shifted. 2 + 5 × 16 + C 1 × 16 number 0 of r that satisfy thenumbers equation 3 (1331) = (11) is/are 16 = 1 × 4096 + 10 × 256 + 5 × 16 + 12 × 1 xy + x′z +Decimal yzBCD= xy + x′zare usual subtraction BCDnumbers r which subtraction r we use in our day-to- is performed by sub- in base -6 system. Example 49: Convert (1001)2 to = A gray+ B code ( = 4096 + 2560 + 80 + 12 = (6748)10. De Morgan’s) (A) 10 daytracting life. Thethe base digits (B) of the 11 4-bit ofdecimal each number system group is 10. of the There are subtrahend(A) Binary 4651 → 1010 (B) 4562 Y(C)= xy + x′z ten 10 and 11 numbers 0 to 9. from the corresponding (D) any r >group 4-bit 3 of the minuend in Table 1 Different number systems Binary → 101 ⊕ (D) 1353 (C) Shifted 1153 DecimalExample AB 1111 5: Octal The value of the nth digit of the number from the right side binary starting from the LSB. Gray →Binary Hexadecimal 5. Example 2: The X is 16-bit signed outputThe of 2’s = nth digit × (base)n–1 number. thecomplement given circuit repre- is equal to signed 00 010of 11 1010 11. The Gray to 0 2’s complement 000 CD representation 0 (-589) sentation ofExampleX is (F76A) Example 1: 45: (99)1042.→The × 10 90100 9 × 10(042 in BCD 2’s1 +complement 0010 repre- ) 1 binary conversion 001 1 1 A 8 × X is 16 = 90 + 9 = 99 in Hexadecimal (a) Take the number MSB of thesystem binary 00 is number 0 is 0 same 1 as MSB 1of sentation of −12 −0001 0010 (12 IN BCD) (A) (F24D) 2 010 2 (B)3 (FDB3)16 3 2 → × × × gray code number. Example 2: (332) 3 10 + 3 10 + 2 10 01to 0 × × 1bit 2 1 0 16 (No borrow, so this is 3 011 (A) (1460) B16 30 (B) 10 0011(D643) 0000 = 300 + 30 + 2 16the correct difference) (C) (b) (F42D) X-OR 4 16 the MSB (D) 100of the binary 4 (F3BD) the next16significant 4 (C) (4460)16 (D) (BB50) 11 × ×5 1 × Example 3: (1024)10 → 1 × 103 + 0 ×16102 + 2 × 101 + × 10012. The baseof 5 the gray code. of the 101 5 Example 46: = 1000 = 1024 is (c) X-OR thenumber 2nd110bit ofsystem binary for which the following 6to the 3rd bit 6of Gray code 6. The HEX number (CD.EF)16 in octal + 0number + 20 + 4 system (Borrow 6 66 10 1 0 1 1 247.7 0010 0100 0111. 0111 to7 is getto3rd bebitcorrect binary and = so13 7on. are operation 111 7 (A) (315.736) ABinary number (B) (513.637)8 system (d) Continue this1000 till all the 5 gray 8 − 8 10 bits are exhausted. 8 (C) (135.673) 156. 9 0001 (D) there 0101 (531.367) 0110. 1001 present,(A) 6 The minimized expression (B)11 7 to binary for the given K–map is BIn binary number system, are only 8 8 two digits ‘0’ and ‘1’. Example 9 50: Convert, 1001 gray code 1010 9 Since there are 90.8 0000 0111 only two numbers, ⋅0000. 1110 subtract(C) 8 its base is 2. (D)12 19 7. 8-bit 2’s complement representation a decimal number 0110) Gray 10 Solution: 1010 1 0AB 0 A Example 4: (1101)in = 1 × 23 + 1 ×−0100122 + 0 × −210110 + 1 × 20 11 1011 13 B is 10000000. The number 2 decimal is 13. The solution 1010 to the 1100 quadratic ⇓ ⊕ || equation CD ⊕1400  ||  x||2 - 11x ⊕ 01 11 +10 13 = 0 1000 Corrected (A) +256 A  B = AB +(B) = 8 + 4 + 11001 = (13)10 ⋅ 12 C Solution: AB0 000 (in number system with radix are = x = 4. difference 13 1100 1101 1 r) 1 15 00 00 x00 D1and 1 2 (C) -128 Octal number system (D) -256 (90.8) Then base = (1100) 14 of the2 number 1110 system 16 is (r) = E A Octal number system has eight numbers 0 to 7. The base of the × F× 8. The range of signed decimal 1 numbers that can be rep- (A) 7 15 1111 (B)17 0 01 6 1 Exercises B number system is 8. The number (8)10 is represented by (10)8.Exercises resented by 7-bit 1’s complement representation is (C) 5 (D) 11 × 4 × 1 (Continued )× Practice problems for (A) stu- -64 to +Practice 63 Problems (B) -63 1 to + 63 3 2. Ifcomplement 14.y The 16’s (84)x (in base xofnumberBADA10 system) is1 is0equal1to (64) 1 y (in (C) -127 to + 128 (D) -128 to +127 base y number system), then possible values of x and y dents to master the concepts Directions Chapter 01.indd 529 for questions 1 to 15: Select the correct alterna-(A) 4525 are (B) 4526 8/17/2015 8:25:39 PM tive from the given choices. Decimal A studied in chapter. 9.Exercises 54 in hexadecimal and BCD number system is (C) ADAB (A) 12, = 9A + B C (D)(B) 21416, 8 2 1. Assuming all the numbers are in 2’s X OR gate rep- complement consist of two levels of prob-B respectively resentation, which of the following is divisible by 15. (11A1B) (C)=9,(12CD) 8 12 16 , in the above (D) expression 12, 18 A and B (A) lems “Practice Problem I” 63, 10000111 11110110? (B) 36,01010100 represent AExample 3. Letpositive = 1111 digits 1011in 6: and In octal the 0000 figure B = number 1011 system shown, be two and8-bitC y , y , y will be 1s 2 1 0 (C) 66, 01010100 (A) 11101010(D) 36, 00110110 (B) 11100010 and D have signed their original meaning 2’s complement complement numbers. of x xin Their Hexadecimal, x if = product z ? in the 2’s and “Practice Problem II” A  B = AB + (D) (C) 11111010 AB11100111 values of A and B are? complement representation is2 1 0 10.diffi based on increasing A culty new binary-coded hextary (BCH) number system is proposed in which everycircuit digit ofisa ‘0’. base As -6 number (A) 2, 5 (B) 2, 3 level. So the output of above two inputs are same (C) 3, 2 (D)x03, 5 system is represented by its corresponding 3-bit binary y0 at third gate. Output of XOR gate with two equal inputs is zero. Chapter 01.indd 536 x 8/12/2015 12:15:36 PM Practice Problems 2 \y=0 (A) 11111 (B) 110001 y1 (C) 01111 (D) 10000 Directions Example for questions to 20: Select 3: The 1circuit shown theincorrect alterna-is functionally the figure tive from the given choices. 7. (0.25) in binary number systemx2is? equivalent to 10 y2 (A) (0.01) (B) (0.11) 1. The hexadecimal representation of (567)8 is (C) 0.001 (D) 0.101 (A) A 1AF (B) D77 (C) 177 (D) 133 8. The equivalent of (25)6 in number system z = with ? base 7 B is? 2. (2326)8 is equivalent to (A) 22 (B) 23 (A) A (14D6)16 (B) (103112)4 (C) 24 Solution: We(D) are26using X-OR gate (C) (1283)10 (D) (09AC)16 ∴ XOR out-put is complement of input only when other B 9. The operation 35 + 26 = 63 is true in number system with radix input is high. 3. (0.46) equivalent in decimal is? 8 (A) 0.59375 (B) 0.3534 (A) 7 ∴Z=1 (B) 8 (C) 0.57395 Solution: (D) 0.3435 (C) 9 (D) 11 4. The 15’s complement of (CAFA)16 is Example 7: The output y of the circuit shown is the figure is A 10. The hexadecimal equivalent of largest binary number A (A) (2051)16 (B) (2050)16A · B A (C) (3506)16 (D) (3505)16 (A + B ) with 14-bits is? (A) y=A⊕B 2FFF B (B) 3FFFF B  above code? What type of values is passed to the called procedure? (A) 5 (A) l-values (B) 6 (B) r-values (C) Text of actual parameters (C) 8 (D) None of these (D) 7 19. Which of the following is FALSE regarding a Block? 17. A basic block can be analyzed by (A) The first statement is a leader. (A) Flow graph (B) Any statement that is a target of conditional / un- conditional goto is a leader. (B) A graph with cycles (C) Immediately next statement of goto is a leader. (C) DAG (D) The last statement is a leader. (D) None of these previous yeArs’ QuesTions Previous Years’ 1. The least number of temporary variables required to create a three-address code in static single assignment (A) 5 and 7 (C) 5 and 5 (B) 6 and 7 (D) 7 and 8 Questions form for the expression q + r/3 + s – t * 5 + u * v/w is 3. Consider the following code segment. Contains previous 10 ________ x = u – t; years GATE Questions 2. Consider the intermediate code given below. y = x * v; x = y + w; at end of every chapter i=1 (1) y = t – z; which help students to get (2) j=1 y = x * y; an idea about the type of (3) t1 = 5 * i The minimum number of total variables required to con- (4) t2 = t1 + j vert the above code segment to static single assignment problems asked in GATE (5) t3 = 4 * t2 form is _____. and prepare accordingly. (6) t4 = t3 4. What will be the output of the following pseudo- (7) a[t4] = –1 code when parameters are passed by reference and (8) j=j+1 dynamic scoping is assumed? (9) if j < = 5 goto (3) a = 3; (10) i=i+1 void n(x) { x = x* a; print (x);} (11) if i < 5 goto (2) void m(y) {a = 1; a = y – a; n(a) ; print (a)} The number of nodes and edges in the control-flow- graph constructed for the above code, respectively, void main( ) {m(a);} are (A) 6,2 (B) 6,6 (C) 4,2 (D) 4,4 Answer keys 38 | Digital Logic exerCises Practice Problems 1 Hints/solutions Hints/Solutions 1. D 2. D 3. C 4. C 5. B 6. A 7. B 8. A 9. A 10. A This section gives complete 11. B Practice 12. C Problems13. 1 A 14. C 15. B Then Z = A + B Hence, the correct option is (B). solutions of all the unsolved 1. Practice Problems0 2 A A y=1 8. Error → transmits odd number of one’s, for both cases. questions given in the chapter. 1. B 2. B 3. A 4. B 5. B 6. A 7. B 8. C 9. A 10. A 11. B 12. D A 13. A A 14. C 15. C 16. A Hence, 17.theC correct18. option B is (A). 19. D The Hints/Solutions are 9. ∑(0, 1, 2, 4, 6) P should contain minterms of each func- included in the CD accompa- X-ORYears’ Previous of two equal inputs will give you result as zero. Questions tion of x as well as y nying the book. 1. 8Hence, the 2. B correct option 3. 10 is (B).4. D Hence, the correct option is (B). 2. Positive level OR means negative level AND vice versa 10. AB + ACD + AC Hence, the correct option is (D). = AB(C + C )( D + D) + A( B + B )CD + A( B + B )C ( D + D) 3. AB⋅CD ⋅ EF ⋅ GH = AB (CD + CD + CD + C D) + ABCD + ABCD + (De Morgan’s law) = AC ( BD + BD + BD + BD) = ( A + B ) (C + D ) ( E + F ) (G + ( H )) ABCD + ABCD + ABCD + ABC D + ABCD + Hence, the correct option is (B). ABCD + ABCD + ABCD + ABCD 4. AB A Hence, the correct option is (A). B Test | 103 AB · B = AB + B (AB + B ) · B = A + B 11. ABCD + ABCD + ABCD + ABCD Practice Tests = ABC + ABC TesT Time-bound Test provided at = BC y DigiTal logic end of each unit for assessment Hence, the correct option is (C). Time: 60 min. C 12. YZ of topics leaned in the(ABunit. + B ) · C = AC + BC Directions for questions WX 30: Select 1 to 01 00 11 10the correct alterna- 9. The number of product terms in the minimized SOP tive from the given choices. from is 00 1 1 = ( A + B ) + AC + BC 1. What is the range of signed decimal numbers that can 1 0 0 1 01 1 1 1 1 be represented by 4-bit 1’s complement notation? 0 D 0 0 = ( A + C + B ) = ABC (A) –7 to + 7 11 1 (B) –161 to +16 0 0 D 1 Hence, the correct option is (C). (C) –7 to +8 10 1 (D) –151 to +16 1 0 0 1 5. The output should be high when at least two outputs 2. Which are of the 1 octet + 1 quad following signed representation have a (A) 2 (B) 4 high y = ABC + ABC + ABC + ABC unique representation = z + wx of 0? (C) 5 (D) 3 (A) Sign-magnitude (B) 1’s complement The minimized output Hence, the correct option is (D). 10. The minimum number of 2 input NAND gates needed (C) 0’s complement (D) 2’s complement y = AB + AC + BC 13. A AB to implement Z = XY + VW is 3. Find the oddBone out among the following Hence, the correct option is (A). (A) 2 (B) 3 (A) EBCDIC (B) GRAY P = AB (C) 4 (D) 5 6. f1(x, y, z) x (C) Hamming (D) A ASCII x + f3 11. The operation a ⊕ b represents f2(x, y, z) 4.z)Gray code for number 8 is f (x, y, Y (A) 1100 (B) 1111 A + B (A) C ab + a b (B) ab + ab (C) 1000 (D) B 1101 f3(x, y, z) (C) ab + ab (D) a − b 5. Find the equivalent C = ABlogical ⋅(A + Bexpression ) for z = x + xy 12. Find the dual of X + [Y + XZ] + U x consists of all min terms, so x = 0, and f = f3 (A) z = x y (B) Z = xy (C) Z = x + y = ( A + B ) ( A + B ) (D) Z = x + y (A) X + [Y(X + Z)] + U (B) X(Y + XZ)U f3 (x1 y1 z) = (1, 4, 5) (C) X + [Y(X + Z)]U (D) X [Y(X + Z)]U AB + AB 6. The number of=distinct Boolean expression of 3 vari- Hence, the correct option is (A). 13. The simplified form of given function AB + BC + AC is ables is Hence, the correct option is (A). 7. I J equal to (A) 256 (B) 16 14. AB (A) AB + AC (B) AC + BC A (C) 1024 C (D) 65536 Z Boolean expression (C) AC + BC (D) AB + AC 7. The 0 0 0 for0the 0truth table shown is 14. Simplify the following 1 0 1 0 0 X Y Z F YZ Traal and error method ⇒ 0 B( A0+ C ) 0( A + C0). WX 1 1 0 1 I = 1, J = B 0 Hence, 0 correct the 1 option 0 is (A). 1 1 0 1 0 1 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 Syllabus: Computer Science and Information Technology Computer Science and Information Technology Digital Logic: Boolean algebra. Combinational and sequential circuits. Minimization. Number representations and com- puter arithmetic (fixed and floating point). Computer Organization and Architecture: Machine instructions and addressing modes. ALU, data-path and control unit. Instruction pipelining. Memory hierarchy: cache, main memory and secondary storage; I/O interface (interrupt and DMA mode). Programming and Data Structures: Programming in C. Recursion. Arrays, stacks, queues, linked lists, trees, binary search trees, binary heaps, graphs. Algorithms: Searching, sorting, hashing. Asymptotic worst case time and space complexity. Algorithm design tech- niques: greedy, dynamic programming and divide-and-conquer. Graph search, minimum spanning trees, shortest paths. Theory of Computation: Regular expressions and finite automata. Context-free grammars and push-down automata. Regular and contex-free languages, pumping lemma. Turing machines and undecidability. Compiler Design: Lexical analysis, parsing, syntax-directed translation. Runtime environments. Intermediate code generation. Operating System: Processes, threads, inter1process communication, concurrency and synchronization. Deadlock. CPU scheduling. Memory management and virtual memory. File systems. Databases: ER1model. Relational model: relational algebra, tuple calculus, SQL. Integrity constraints, normal forms. File organization, indexing (e.g., B and B+ trees). Transactions and concurrency control. Computer Networks: Concept of layering. LAN technologies (Ethernet). Flow and error control techniques, switch- ing. IPv4/IPv6, routers and routing algorithms (distance vector, link state). TCP/UDP and sockets, congestion control. Application layer protocols (DNS, SMTP, POP, FTP, HTTP). Basics of Wi-Fi. Network security: authentication, basics of public key and private key cryptography, digital signatures and certificates, firewalls.  Chapter-wise Analysis of GATE Previous Years’ Papers Subject 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 General Aptitude 1 Marks Questions 5 5 5 5 5 5 5 5 2 Marks Questions 5 5 5 5 5 5 6 5 Total Marks 15 15 15 15 15 15 17 15 Engineering Mathematics 1 Marks 6 3 4 5 4 6 2 3 5 5 4 5 4 2 Marks 12 11 11 11 6 5 7 3 2 5 6 4 5 Total Marks 30 25 26 27 16 16 16 9 9 15 16 13 14 Theory of Computation 1 Marks 0 2 2 3 4 1 3 4 1 5 1 3 2 2 Marks 7 6 5 6 3 3 3 1 2 6 3 3 4 Total Marks 14 14 12 15 10 7 9 6 5 17 7 9 10 Digital Logic 1 Marks 4 1 3 4 2 3 3 2 3 3 1 2 2 2 Marks 5 5 5 1 0 2 3 2 1 5 2 1 2 Total Marks 14 11 13 6 2 7 9 6 5 13 5 4 6 Computer Organization and Architecture 1 Marks Questions 4 0 2 0 2 1 3 2 1 2 1 2 3 2 Marks Questions 9 7 6 12 4 4 2 4 7 2 2 2 4 Total Marks 22 14 14 24 10 9 7 10 15 6 5 6 11 Programming and Data Structures 1 Marks Questions 5 0 1 1 1 3 4 2 2 0 5 2 4 2 Marks Questions 3 6 3 3 3 5 7 6 5 2 3 5 4 Total Marks 11 12 7 7 7 13 18 14 12 4 11 12 12 Algorithm 1 Marks Questions 2 8 3 2 3 1 1 4 5 1 4 4 2 2 Marks Questions 10 7 12 15 6 3 0 2 3 2 4 5 2 Total Marks 22 22 27 32 15 7 1 8 11 5 12 14 6 Compiler Design 1 Marks Questions 1 1 1 2 1 2 1 1 2 1 2 1 2 2 Marks Questions 5 5 5 2 0 1 0 3 2 2 1 1 1 Total Marks 11 11 11 6 1 4 1 7 6 5 4 3 4 Operating System 1 Marks Questions 0 1 2 2 2 3 3 1 1 0 2 1 2 2 Marks Questions 2 8 6 5 5 2 2 3 1 2 2 4 2 Total Marks 4 17 14 12 12 7 7 7 3 4 6 9 6 Database 1 Marks Questions 3 1 0 1 0 3 0 3 1 3 1 3 2 2 Marks Questions 4 4 6 5 5 2 3 3 4 2 2 1 3 Total Mark 11 9 12 11 5 7 6 9 9 7 5 5 8 Computer Networks 1 Marks Questions 5 1 2 1 0 2 5 3 4 4 2 2 2 2 Marks Questions 2 5 6 4 5 3 2 3 2 2 3 4 3 Total Marks 9 11 14 9 5 8 9 9 8 8 8 10 8 Software Engineering 1 Marks Questions 1 0 1 0 0 1 1 2 Marks Questions 0 0 0 0 1 0 1 Total Marks 1 0 1 0 2 1 3 Web Technology 1 Marks Questions 1 0 1 0 0 0 1 2 Marks Questions 0 0 0 0 0 0 1 Total Marks 1 0 1 0 0 0 3 General Information about GATE Structure of GATE The GATE examination consists of a single online paper of 3-hour duration, in which there will be a total of 65 questions carrying 100 marks out of which 10 questions carrying a total of 15 marks are in General Aptitude (GA). Section Weightage and Marks 70% of the total marks is given to the technical section while 15% weightage is given to General Aptitude and Engineering Mathematics each. Weightage Questions (Total 65) Respective 70 Marks 25—1markques- EngineeringBranch tions30—2mark EngineeringMaths 15 Marks questions General Aptitude 15 Marks 5—1 mark ques- tions 5—2 mark questions Particulars For 1-mark multiple-choice questions, 1/3 marks will be deducted for a wrong answer. Likewise, for 2-mark ­multiple-choice questions, 2/3 marks will be deducted for a wrong answer. There is no negative marking for numerical answer type questions. Question Types 1. Multiple Choice Questions (MCQ) carrying 1 or 2 marks each in all papers and sections. These questions are objective in nature, and each will have a choice of four answers, out of which the candidate has to mark the correct answer. 2. Numerical Answer carrying 1 or 2 marks each in all papers and sections. For numerical answer questions, choices will not be given. For these questions the answer is a real number, to be entered by the candidate using the virtual keypad. No choices will be shown for this type of questions. Design of Questions The fill in the blank questions usually consist of 35%– 40% of the total weightage. The questions in a paper may be designed to test the following abilities: 1. Recall: These are based on facts, principles, formulae or laws of the discipline of the paper. The candidate is expected to be able to obtain the answer either from his/her memory of the subject or at most from a one-line computation. 2. Comprehension: These questions will test the candidate’s understanding of the basics of his/her field, by requiring him/her to draw simple conclusions from fundamental ideas. 3. Application: In these questions, the candidate is expected to apply his/her knowledge either through computation or by logical reasoning. 4. Analysis and Synthesis: In these questions, the candidate is presented with data, diagrams, images etc. that require analysis before a question can be answered. A Synthesis question might require the candidate to compare two or more pieces of information. Questions in this category could, for example, involve candidates in recognising unstated assumptions, or separating useful information from irrelevant information. About Online Pattern The examination for all the papers will be carried out in an ONLINE Computer Based Test (CBT) mode where the candi- dates will be shown the questions in a random sequence on a computer screen. The candidates are required to either select the answer (for MCQ type) or enter the answer for numerical answer-type question using a mouse on a virtual keyboard (keyboard of the computer will be disabled). The candidates will also be allowed to use a calculator with which the online portal is equipped with. Important Tips for GATE The followings are some important tips which would be helpful for students to prepare for GATE exam 1. Go through the pattern (using previous year GATE paper) and syllabus of the exam and start preparing accordingly. 2. Preparation time for GATE depends on many factors, such as, individual’s aptitude, attitude, fundamentals, concentration level etc., Generally rigorous preparation for 4 to 6 months is considered good but it may vary from student to student. 3. Make a