GATE CSE Question Paper Analysis
Maths: G07(21 marks)
TOC: G07(14 marks)
DIG: G07(12 marks)
COA: G07(16 marks)
DS&C: G07(14 marks)
Algo: G07(22 marks)
Compiler:G07(9 marks)
OS: G07(14 marks)
DBMS:G07(12 marks)
CNW:G07(14 marks)
I. Engineering Mathematics
1. Calculus
*G07 \Q1 , 1(Differentiability and continuity)
2. Set theory and Algebra
*G07 \Q2 ,1 (equivalence relations)
*G07\Q21,2 (non-isomorphic abelian groups, order)
*G07\Q26,2(partial order, poset diagram)
*G07\Q27,2
*G06\Q1,1 (polynomials)
*G06\Q2,1 (subsets, functions)
*G06\Q3,1 (group, multiplication modulo 10)
*G06\Q4,1(relation,partial order, total order, equivalence relation)
*G06\Q22,2
*G06\Q24,2 (permutations)
*G06\Q25,2
*G06\Q28,2(relations)
*G05\Q7,1 (transitive closure, time complexity, binary relation)
*G05\Q8,1(set theory)
*G05\Q9,1(hasse diagram, poset, distributive lattice)
*G05\Q13,1 (group, multiplication modulo 15)
*G05\Q42,2 (equivalence relations)
*G05\Q43,2 (onto function)
*G05\Q44,2
*G05\Q46,2(group, monoid, semi group)
*G05\Q50,2
*G04\Q24,1(binary relation, reflexive transitive closure)
*G04\Q72,2(4-element group)
*G04\Q73,2(complete lattice, partial order, set containment)
*G04\Q75,2(permutations,coloring)
*G03\Q4,1(permutations)
*G03\Q7,1(group)
*G03\Q31,2 (partial order)
*G03\Q37,2(injective,one-to-one,subsets)
*G03\Q38,2(sets)
3. Boolean Algebra
*G07\Q3,1
4. Graph Theory
*G07\Q4,1 (non-planar graph)
*G07\Q5,1 (DAG, topological ordering)
*G07\Q23,2 (Eulerian circuit,k-regualr graph, complete graphs
*G06\Q71,2
*G06\Q72,2
*G06\Q73,2
*G05\Q6,1 (minimum spanning tree)
*G05\Q10,1 (number of faces)
*G05\Q11,1 (maximum independent set)
*G05\Q47,2
*G05\Q82a,2
*G05\Q82b,2
*G04\Q77,2(graph coloring)
*G04\Q79,2 (edges, vertices)
*G04\Q81,2(connected graphs, cut vertex, cycle, bridge, chromatic number)
*G03\Q8,1(graph)
*G03\Q36,2(perfect matching)
*G03\Q40,2(degree)
*G03\Q68,2(minimum spanning tree)
*G03\Q70,2(hamiltonian cycle)
5. Math Logic
*G07\Q22 ,2
*G06\Q26,2
*G06\Q27,2
*G05\Q40,2(tautology)
*G05\Q41,2
*G04\Q23,1
*G04\Q70,2
*G03\Q32,2
*G03\Q33,2
*G03\Q71,2
*G03\Q72,2
6. Probability
*G07\Q24,2
*G06\Q18,1
*G06\Q21,2
*G05\Q12,1 (random variable, continuous probability density function)
*G05\Q51,2
*G05\Q52,2
*G04\Q25,1
*G04\Q74,2(Expectation)
*G04\Q78,2(hamming distance, bit strings)
*G04\Q80,2(expected value)
*G03\Q3,1(conditional probability)
*G03\Q60,2(probability density functions , time complexity)
7. Linear Algebra
*G07\Q25,2 (eigen value of a matrix)
*G06\Q23,2
*G05\Q48,2
*G05\Q49,2 (eigen value)
*G04\Q26,1
*G04\Q27,1
*G04\Q71,2
*G04\Q76,2
*G03\Q41,2(number of solutions)
8. Numerical Methods
*G07\Q28,2 (Newton Raphson method)
*G03\Q42,2(Newton Raphson method)
9. Permutations
*G03\Q4,1
*G03\Q5,1
*G03\Q34,2
*G03\Q61,2
II. Theory of Computation
1. Undecidability
*G07\Q6,1
*G05\Q45,2
*G03\Q52,2
2. Regular sets
*G07\Q7,1
3. DFA accepting a language, number of states
*G07\Q29,2
*G07\Q75,2
*G06\Q34,2
*G05\Q53,2
*G05\Q63,2
*G04\Q86,2
*G03\Q50,2(number of strings accepted by DFA )
4. Given a language , find the family in which it belongs
*G07\Q30,2
*G07\Q31,2 (regular languages)
*G06\Q29,2 (regular languages)
*G06\Q30,2(recursive, recursively enumerable, context free, regular)
*G06\Q33,2 (regular language, deterministic CFL, re but not recursive language)
*G05\Q54,2 (NFA,NPDA)
*G05\Q55,2(cfl,csl)
*G05\Q56,2(recursive language, re language)
*G05\Q57,2(deterministic CFL)
*G04\Q87,2(regular,cfl,csl,type 0)
*G04\Q89,2(re language)
*G03\Q13,1(NP, recursive, recursively enumerable, re)
*G03\Q15,1(finite,regular,context free, recursive)
*G03\Q51,2(cfg, ambiguous, pda)
*G03\Q54,2(recursive,recursively enumerable)
*G03\Q55,2(NFA)
5. Regular Expressions
*G07\Q74,2
*G03\Q14,1
6. NP completeness
*G06\Q16,1
*G06\Q31,2(hamiltonian cycle)
*G05\Q58,2(graph)
*G04\Q30,1(3-SAT, 2-SAT)
*G03\Q12,1(3-SAT,NP-hard, NP-complete)
*G03\Q52,2
7.Context free Languages
*G06\Q19,1
*G06\Q32,2 (Context free grammar)
8. Grammar generating the language
*G06\Q84,2
*G06\Q85,2
9.Turing Machine
*G03\Q53,2
III. Digital logic
1. Decoders
*G07\Q8,1
2.Boolean functions and K-maps
*G07\Q9,1
*G07\Q32,2
*G07\Q33,2
*G06\Q38,2
*G05\Q15,1 (gates)
*G05\Q18,1
*G04\Q17,1
*G04\Q58,2(gates)
*G04\Q59,2
*G03\Q45,2
*G03\Q47,2(xor gate)
3. MUX implementing boolean function
*G07\Q34,2
*G06\Q35,2
*G04\Q60,2
4. Carry look ahead adder
*G07\Q35,2
*G06\Q36,2
*G04\Q62,2
*G03\Q46,2
5. Binary Counter
*G07\Q36,2
6. Flip-Flop
*G06\Q8,1
*G06\Q37,2(D-Flip Flop)
*G05\Q62,2 (D-FF)
*G05\Q64,2 (D- Flip flop)
*G04\Q18,1(SR flip flop)
*G04\Q61,2(t-Flip Flop, counter)
7. Binary Adder
*G06\Q39,2
8.Grey Code
*G06\Q40,2
9. Number system
*G05\Q16,1 (2s compliment number system)
*G05\Q17 ,1(octal to hex conversion )
*G05\Q85a,2
*G05\Q85b,2
*G04\Q19,1
*G04\Q28,1(3 digit floating point arithmetic)
*G04\Q66,2(2s compliment product)
*G03\Q9,1(2s compliment, divisible)
*G03\Q43,2(floating point)
10. Sequential logic
*G03\Q44,2
IV. Computer Organization and Architecture
1. Cache
*G07\Q10,1 (4-way set associative cache)
*G07\Q80,2
*G07\Q81,2
*G06\Q41,2
*G06\Q74,2 (2-way set associative, direct mapped)
*G06\Q75,2
*G06\Q80,2 (direct mapped cache, byte block size)
*G06\Q81,2
*G05\Q67,2(direct mapped cache)
*G04\Q65,2(2-ways set associative cache, LRU, cache misses)
2. Disk Capacity
*G07\Q11,1
3. Pipelining
*G07\Q37,2
*G06\Q42,2
*G05\Q68,2 (clock cycles needed)
*G04\Q69,2(4-stage pipe line, time taken to process)
*G03\Q10,1
4. Instructions
*G07\Q54,2
*G07\Q71,2
*G07\Q72,2
*G07\Q73,2
*G06\Q9,1
*G06\Q43,2
*G05\Q20,1 (memory mapped I/O )
*G05\Q65,2 (memory cycles, addressing modes)
*G05\Q66,2(addressing mode)
*G05\Q79,2(min no of clock cycles needed)
*G05\Q80,2(min no of cpu clock cycles needed)
*G04\Q20,1(addressing modes)
*G04\Q64,2(total number of clock cycles required)
*G04\Q67,2(micro instructions )
*G03\Q48,2(assembly language)
*G03\Q49,2
5. Interrupts
*G05\Q19,1
*G05\Q69,2(interrupt mode, program control mode)
*G04\Q63,2 (byte addressable)
V. Programming in C and Principles of programming languages and Data Structures
1. Binary tree
*G07\Q12,1
*G07\Q13,1
*G07\Q43,2 (Complete n-ary tree)
*G06\Q13,1(binary tree in array)
*G05\Q35,2 (binary search tree, BST)
*G05\Q36,2(k-ary tree)
*G04\Q4,1(height of binary search tree,BST)
*G04\Q43,2(what does the program do ?)
*G04\Q85,2(binary search tree , BST)
*G03\Q6,1(BST)
*G03\Q19,1(BST,in order traversal)
*G03\Q63,2(BST,Heap)
*G03\Q65,2
2. Stack
*G07\Q39,2 (post fix expression evaluation)
*G06\Q49,2(queue implementation using stack)
*G05\Q2,1(ADT definition)
*G04\Q5,1
*G03\Q64,2
3. Binary tree traversal
*G07\Q39,2
*G05\Q33,2 (post order, BST,in order)
*G04\Q6,1
*G04\Q35,2
4.Hashing
*G07\Q40,2 (closed hashing)
*G04\Q7,1
5. Recursion
*G07\Q42,2
*G07\Q46,2
*G05\Q31,2
*G05\Q32,2
*G04\Q31,2
6.Arrays
*G06\Q50,2
*G05\Q5,1
*G04\Q3,1
7. C programming
*G06\Q53,2
*G06\Q55,2
*G06\Q57,2
*G05\Q1,1 (pointers)
*G05\Q61,2
*G04\Q2,1 (pass by value)
*G04\Q32,2
*G04\Q33,2
*G04\Q41,2
*G04\Q42,2
*G03\Q1,1(approximation)
*G03\Q2,1(compile time errors)
*G03\Q88,2
*G03\Q89,2
*G03\Q90,2 (list, sorting)
8. Principles of programming languages
*G06\Q56,2
*G05\Q3,1(logic programming languages, functional languages)
*G05\Q4,1(Object oriented programming languages)
*G04\Q1,1(structured programming)
*G04\Q9,1
*G04\Q90,2(functional, logic, object oriented, imperative)
*G03\Q24,1(statically typed language, dynamically typed, un typed)
*G03\Q73,2(static scoping, call-by-need)
*G03\Q74,2(dynamic scoping,call-by-name)
*G03\Q75,2(object oriented language, inheritance, dynamic binding)
*G03\Q76,2(shared statically/dynamically linked libraries)
10. Max Heap
*G06\Q76,2
*G06\Q77,2
*G05\Q34,2 (priority queue)
*G04\Q37,2
*G03\Q23,1
11. Circular Linked lists
*G04\Q36,2(queue)
12. Postfix , infix, prefix
*G04\Q38,2
VI. Algorithms
1. Time complexity
*G07\Q14,1 ( Sorting & Worst case Time complexity)
*G07\Q15,1(C-program given, find time complexity)
*G07\Q41,2 (undirected connected graph, shortest path, Dijkstra's algo , Warshalls algo, BFS, DFS)
*G07\Q45,2 (recursion)
*G07\Q51,2 (timing complexity of a C program)
*G06\Q10,1(binary max heap , smallest element)
*G06\Q17,1(array-leader)
*G06\Q,2(quick sort)
*G06\Q54,2
*G05\Q7,1 (transitive closure of a binary relation )
*G05\Q38,2(Dijkstra's single source shortest path algo , binary heap)
*G05\Q38,2(heap)
*G04\Q39,2(matrix multiplication , RMO, CMO)
*G04\Q40,2(linked list, union, intersection.. )
*G04\Q82,2(C-program)
*G04\Q83,2(C-program)
*G04\Q85,2(worst case, BST)
*G03\Q11,1(array multiplier)
*G03\Q20,1
*G03\Q22,1(Insertion sort,array, binary search)
*G03\Q23,1(heap,smallest element)
*G03\Q62,2(Insertion sort, worse case )
*G03\Q66,2(cube root)
2. Asymptotic notations
*G07\Q44,2
*G07\Q47,2 (Max heap)
*G06\Q15,1
3. Minimum spanning tree
*G07\Q49,2
*G06\Q11,1 (weighted complete graph)
*G06\Q47,2(Kruskal's Algorithm)
*G05\Q26,1 (LAN)
4. No of comparisons needed
*G07\Q50,2 ( Find max and min of an array)
*G04\Q29,1(comparison based sorting)
5. Huffman Coding
*G07\Q76,2
*G07\Q77,2
6. Robot movement and permutations
*G07\Q84,2
*G07\Q85,2
7. Dijkstra's shortest path Algorithm
*G06\Q12,1
*G04\Q44,2
*G03\Q67,2(single source shortest path)
8. Sorting
*G06\Q14,1(quick sort, Insertion sort, Selection sort , Heap sort)
9.DFS
*G06\Q48,2
*G06\Q82,2 (spanning tree)
*G03\Q21,1
10. Recurrence relations
*G06\Q51,2
*G05\Q37,2
*G04\Q84,2
*G03\Q35,2
11. Space complexity
*G05\Q81a,2
*G05\Q81b,2
12. Job scheduling with dead lines
*G05\Q84a,2
*G05\Q84b,2
VII. Compiler Design
1. Parsers
*G07\Q18,1 (Top down parsers)
*G03\Q17,1(SLR, LALR)
2. Grammar
*G07\Q52,2( LL1 grammar)
*G07\Q53,2(regular grammar,LR(1) grammar, regular set)
*G06\Q7,1 ( LR(0) items, canonical sets of items )
*G06\Q58,2(predictive parser table)
*G06\Q59,2 (translation scheme)
*G05\Q14,1(predictive parsing, ambiguous, left recursive, right recursive, an operator grammar)
*G05\Q59,2(right sentential form)
*G05\Q60,2(SLR(1),LR(1),LALR(1))
*G05\Q83a,2(yacc, LALR(1) parser generator, reduce-reduce conflict, shift-reduce conflict
*G05\Q83b,2(precedence and left\right associativity)
*G04\Q8,1(operator grammar)
*G04\Q88,2(language generated)
*G03\Q16,1(LL(1), CFG, left recursion, factoring)
*G03\Q39,2
*G03\Q56,2(predictive parse table)
*G03\Q57,2(LL(1), LALR(1),SLR(1),LR(1))
3. Strings generated by a given grammar
*G07\Q78,2
4. Number of derivation trees for a string generated by a grammar
*G07\Q79,2
5.Code Optimization
*G06\Q61,2
*G04\Q10,1
6. SDT
*G04\Q45,2
*G03\Q18,1
*G03\Q58,2
*G03\Q59,2
VIII. Operating System
1. CPU scheduling
*G07\Q16,1
2. User level and Kernel level threads
*G07\Q17,1
*G04\Q11,1
3.Scheduling
*G07\Q55,2 (SRT first scheduling algorithm)
*G06\Q6,1 (Shortest remaining time first scheduling algorithm)
*G06\Q64,2(longest remaining time first scheduling)
*G06\Q65,2(shortest remaining compute time first scheduling)
*G04\Q12,1(FCFS,shortest seek time first)
*G04\Q46,2(Shortest remaining process time first)
*G03\Q69,2
*G03\Q77,2(FCFS,SRTF,round robin with time quantum, static priority scheduling)
4. Page replacement policies
*G07\Q56,2 (FIFO, Bellady's anomaly)
*G07\Q82,2(optimal page replacement policy)
*G07\Q83,2(LRU)
*G05\Q22,1 (page faults )
5. Resource allocation
*G07\Q57,2
6.Synchronization and deadlocks
*G07\Q58,2
*G06\Q66,2 (deadlock)
*G06\Q78,2(semaphore)
*G06\Q79,2
*G05\Q71,2 (deadlock)
*G05\Q72,2(fork)
*G04\Q47,2(binary semaphore)
*G03\Q80,2(binary semaphores)
*G03\Q81,2(binary semaphores)
7. Paging
*G06\Q62,2(TLB, 4-way set associative)
*G04\Q47,2(TLB,2-level paging)
*G03\Q26,1(fragmentation)
*G03\Q78,2(TLB,paging)
*G03\Q79,2(paging)
8. virtual memory
*G06\Q63,2
*G04\Q21,1(number of page frames)
9. Disk
*G05\Q21,1 (swap space)
*G05\Q70,2(DMA,cycle stealing mode, disk specifications)
*G04\Q68,2(DMA,processor time)
10. Files
*G04\Q49,2(i-node,file size)
*G03\Q25,1
IX. Databases
1. Relational algebra
*G07\Q59,2
*G05\Q30,1
*G04\Q13,1 (referential integrity)
*G04\Q51,2
*G03\Q30,1(sql)
2. Relational Calculus
*G07\Q60,2
3. SQL
*G07\Q61,2
*G06\Q67,2
*G06\Q68,2
*G05\Q77,2
*G04\Q53,2
*G03\Q30,1(relational algebra)
*G03\Q86,2
4. Normal forms
*G07\Q48,2 (Conjuntive Normal Form)
*G07\Q62,2 (BCNF,2NF,3NF)
*G05\Q29,1
*G04\Q50,2(functional dependencies)
*G03\Q85,2(BCNF,2nd normal form)
5. B+ trees
*G07\Q63,2 (order of leaf node)
*G05\Q28,1
*G04\Q52,2
6.Transactions
*G07\Q64,2 (Conflict serializability)
*G06\Q20,1
*G03\Q29,1(committed)
*G03\Q87,2(serializable)
7. Query plans
*G06\Q69,2
8. Functional Dependencies
*G06\Q70,2
9. ER diagrams
*G05\Q75,2
10. Referential Integrity
*G05\Q76,2
11. Functional dependencies
*G05\Q78,2 (candidate keys)
12. Natural join
*G04\Q14,1
13. Database design
*G04\Q34,2
X. Computer Networks
1. Ethernet
*G07\Q19,1 (Manchester encoding, bit rate, baud rate)
*G06\Q82,2
*G06\Q83,2
*G05\Q74,2(round trip propagation delay, jamming signal, frame size)
*G04\Q54,2(probability)
*G03\Q83,2(CSMA/CD,packet size)
2. UDP and TCP
*G07\Q20,1
*G05\Q23,1
3. Slotted LAN
*G07\Q65,2 (probability)
4.Token ring
*G07\Q66,2 (bit delay)
5. Subnetting
*G07\Q67,2 (max num of subnets and hosts)
*G06\Q45,2 (netmask)
*G05\Q27,1
*G03\Q82,2
6. CRC polynomial
*G07\Q68,2
7. Sliding window protocol
*G07\Q69,2 (number of bits in sequence number)
*G06\Q44,2(round trip delay, bandwidth, optimal window size)
*G06\Q46,2
*G05\Q25,1 (selective reject protocol)
8. Protocols
*G07\Q70,2 (SMTP,BGP,TCP,PPP)
*G06\Q5,1(IP,TTL)
*G05\Q24,1 (ARP)
*G03\Q27,1(IP)
*G03\Q28,1(TCP)
9. Packet switching
*G05\Q73,2
10. Layers
*G04\Q15,1
11. Network devices
*G04\Q16,1(bridge,router,IP address , MAC address)
12. Data Transmission
*G04\Q22,1
*G04\Q56,2
*G04\Q57,2
*G03\Q84,2
13. Routing
*G04\Q55,2
TOC: G07(14 marks)
DIG: G07(12 marks)
COA: G07(16 marks)
DS&C: G07(14 marks)
Algo: G07(22 marks)
Compiler:G07(9 marks)
OS: G07(14 marks)
DBMS:G07(12 marks)
CNW:G07(14 marks)
I. Engineering Mathematics
1. Calculus
*G07 \Q1 , 1(Differentiability and continuity)
2. Set theory and Algebra
*G07 \Q2 ,1 (equivalence relations)
*G07\Q21,2 (non-isomorphic abelian groups, order)
*G07\Q26,2(partial order, poset diagram)
*G07\Q27,2
*G06\Q1,1 (polynomials)
*G06\Q2,1 (subsets, functions)
*G06\Q3,1 (group, multiplication modulo 10)
*G06\Q4,1(relation,partial order, total order, equivalence relation)
*G06\Q22,2
*G06\Q24,2 (permutations)
*G06\Q25,2
*G06\Q28,2(relations)
*G05\Q7,1 (transitive closure, time complexity, binary relation)
*G05\Q8,1(set theory)
*G05\Q9,1(hasse diagram, poset, distributive lattice)
*G05\Q13,1 (group, multiplication modulo 15)
*G05\Q42,2 (equivalence relations)
*G05\Q43,2 (onto function)
*G05\Q44,2
*G05\Q46,2(group, monoid, semi group)
*G05\Q50,2
*G04\Q24,1(binary relation, reflexive transitive closure)
*G04\Q72,2(4-element group)
*G04\Q73,2(complete lattice, partial order, set containment)
*G04\Q75,2(permutations,coloring)
*G03\Q4,1(permutations)
*G03\Q7,1(group)
*G03\Q31,2 (partial order)
*G03\Q37,2(injective,one-to-one,subsets)
*G03\Q38,2(sets)
3. Boolean Algebra
*G07\Q3,1
4. Graph Theory
*G07\Q4,1 (non-planar graph)
*G07\Q5,1 (DAG, topological ordering)
*G07\Q23,2 (Eulerian circuit,k-regualr graph, complete graphs
*G06\Q71,2
*G06\Q72,2
*G06\Q73,2
*G05\Q6,1 (minimum spanning tree)
*G05\Q10,1 (number of faces)
*G05\Q11,1 (maximum independent set)
*G05\Q47,2
*G05\Q82a,2
*G05\Q82b,2
*G04\Q77,2(graph coloring)
*G04\Q79,2 (edges, vertices)
*G04\Q81,2(connected graphs, cut vertex, cycle, bridge, chromatic number)
*G03\Q8,1(graph)
*G03\Q36,2(perfect matching)
*G03\Q40,2(degree)
*G03\Q68,2(minimum spanning tree)
*G03\Q70,2(hamiltonian cycle)
5. Math Logic
*G07\Q22 ,2
*G06\Q26,2
*G06\Q27,2
*G05\Q40,2(tautology)
*G05\Q41,2
*G04\Q23,1
*G04\Q70,2
*G03\Q32,2
*G03\Q33,2
*G03\Q71,2
*G03\Q72,2
6. Probability
*G07\Q24,2
*G06\Q18,1
*G06\Q21,2
*G05\Q12,1 (random variable, continuous probability density function)
*G05\Q51,2
*G05\Q52,2
*G04\Q25,1
*G04\Q74,2(Expectation)
*G04\Q78,2(hamming distance, bit strings)
*G04\Q80,2(expected value)
*G03\Q3,1(conditional probability)
*G03\Q60,2(probability density functions , time complexity)
7. Linear Algebra
*G07\Q25,2 (eigen value of a matrix)
*G06\Q23,2
*G05\Q48,2
*G05\Q49,2 (eigen value)
*G04\Q26,1
*G04\Q27,1
*G04\Q71,2
*G04\Q76,2
*G03\Q41,2(number of solutions)
8. Numerical Methods
*G07\Q28,2 (Newton Raphson method)
*G03\Q42,2(Newton Raphson method)
9. Permutations
*G03\Q4,1
*G03\Q5,1
*G03\Q34,2
*G03\Q61,2
II. Theory of Computation
1. Undecidability
*G07\Q6,1
*G05\Q45,2
*G03\Q52,2
2. Regular sets
*G07\Q7,1
3. DFA accepting a language, number of states
*G07\Q29,2
*G07\Q75,2
*G06\Q34,2
*G05\Q53,2
*G05\Q63,2
*G04\Q86,2
*G03\Q50,2(number of strings accepted by DFA )
4. Given a language , find the family in which it belongs
*G07\Q30,2
*G07\Q31,2 (regular languages)
*G06\Q29,2 (regular languages)
*G06\Q30,2(recursive, recursively enumerable, context free, regular)
*G06\Q33,2 (regular language, deterministic CFL, re but not recursive language)
*G05\Q54,2 (NFA,NPDA)
*G05\Q55,2(cfl,csl)
*G05\Q56,2(recursive language, re language)
*G05\Q57,2(deterministic CFL)
*G04\Q87,2(regular,cfl,csl,type 0)
*G04\Q89,2(re language)
*G03\Q13,1(NP, recursive, recursively enumerable, re)
*G03\Q15,1(finite,regular,context free, recursive)
*G03\Q51,2(cfg, ambiguous, pda)
*G03\Q54,2(recursive,recursively enumerable)
*G03\Q55,2(NFA)
5. Regular Expressions
*G07\Q74,2
*G03\Q14,1
6. NP completeness
*G06\Q16,1
*G06\Q31,2(hamiltonian cycle)
*G05\Q58,2(graph)
*G04\Q30,1(3-SAT, 2-SAT)
*G03\Q12,1(3-SAT,NP-hard, NP-complete)
*G03\Q52,2
7.Context free Languages
*G06\Q19,1
*G06\Q32,2 (Context free grammar)
8. Grammar generating the language
*G06\Q84,2
*G06\Q85,2
9.Turing Machine
*G03\Q53,2
III. Digital logic
1. Decoders
*G07\Q8,1
2.Boolean functions and K-maps
*G07\Q9,1
*G07\Q32,2
*G07\Q33,2
*G06\Q38,2
*G05\Q15,1 (gates)
*G05\Q18,1
*G04\Q17,1
*G04\Q58,2(gates)
*G04\Q59,2
*G03\Q45,2
*G03\Q47,2(xor gate)
3. MUX implementing boolean function
*G07\Q34,2
*G06\Q35,2
*G04\Q60,2
4. Carry look ahead adder
*G07\Q35,2
*G06\Q36,2
*G04\Q62,2
*G03\Q46,2
5. Binary Counter
*G07\Q36,2
6. Flip-Flop
*G06\Q8,1
*G06\Q37,2(D-Flip Flop)
*G05\Q62,2 (D-FF)
*G05\Q64,2 (D- Flip flop)
*G04\Q18,1(SR flip flop)
*G04\Q61,2(t-Flip Flop, counter)
7. Binary Adder
*G06\Q39,2
8.Grey Code
*G06\Q40,2
9. Number system
*G05\Q16,1 (2s compliment number system)
*G05\Q17 ,1(octal to hex conversion )
*G05\Q85a,2
*G05\Q85b,2
*G04\Q19,1
*G04\Q28,1(3 digit floating point arithmetic)
*G04\Q66,2(2s compliment product)
*G03\Q9,1(2s compliment, divisible)
*G03\Q43,2(floating point)
10. Sequential logic
*G03\Q44,2
IV. Computer Organization and Architecture
1. Cache
*G07\Q10,1 (4-way set associative cache)
*G07\Q80,2
*G07\Q81,2
*G06\Q41,2
*G06\Q74,2 (2-way set associative, direct mapped)
*G06\Q75,2
*G06\Q80,2 (direct mapped cache, byte block size)
*G06\Q81,2
*G05\Q67,2(direct mapped cache)
*G04\Q65,2(2-ways set associative cache, LRU, cache misses)
2. Disk Capacity
*G07\Q11,1
3. Pipelining
*G07\Q37,2
*G06\Q42,2
*G05\Q68,2 (clock cycles needed)
*G04\Q69,2(4-stage pipe line, time taken to process)
*G03\Q10,1
4. Instructions
*G07\Q54,2
*G07\Q71,2
*G07\Q72,2
*G07\Q73,2
*G06\Q9,1
*G06\Q43,2
*G05\Q20,1 (memory mapped I/O )
*G05\Q65,2 (memory cycles, addressing modes)
*G05\Q66,2(addressing mode)
*G05\Q79,2(min no of clock cycles needed)
*G05\Q80,2(min no of cpu clock cycles needed)
*G04\Q20,1(addressing modes)
*G04\Q64,2(total number of clock cycles required)
*G04\Q67,2(micro instructions )
*G03\Q48,2(assembly language)
*G03\Q49,2
5. Interrupts
*G05\Q19,1
*G05\Q69,2(interrupt mode, program control mode)
*G04\Q63,2 (byte addressable)
V. Programming in C and Principles of programming languages and Data Structures
1. Binary tree
*G07\Q12,1
*G07\Q13,1
*G07\Q43,2 (Complete n-ary tree)
*G06\Q13,1(binary tree in array)
*G05\Q35,2 (binary search tree, BST)
*G05\Q36,2(k-ary tree)
*G04\Q4,1(height of binary search tree,BST)
*G04\Q43,2(what does the program do ?)
*G04\Q85,2(binary search tree , BST)
*G03\Q6,1(BST)
*G03\Q19,1(BST,in order traversal)
*G03\Q63,2(BST,Heap)
*G03\Q65,2
2. Stack
*G07\Q39,2 (post fix expression evaluation)
*G06\Q49,2(queue implementation using stack)
*G05\Q2,1(ADT definition)
*G04\Q5,1
*G03\Q64,2
3. Binary tree traversal
*G07\Q39,2
*G05\Q33,2 (post order, BST,in order)
*G04\Q6,1
*G04\Q35,2
4.Hashing
*G07\Q40,2 (closed hashing)
*G04\Q7,1
5. Recursion
*G07\Q42,2
*G07\Q46,2
*G05\Q31,2
*G05\Q32,2
*G04\Q31,2
6.Arrays
*G06\Q50,2
*G05\Q5,1
*G04\Q3,1
7. C programming
*G06\Q53,2
*G06\Q55,2
*G06\Q57,2
*G05\Q1,1 (pointers)
*G05\Q61,2
*G04\Q2,1 (pass by value)
*G04\Q32,2
*G04\Q33,2
*G04\Q41,2
*G04\Q42,2
*G03\Q1,1(approximation)
*G03\Q2,1(compile time errors)
*G03\Q88,2
*G03\Q89,2
*G03\Q90,2 (list, sorting)
8. Principles of programming languages
*G06\Q56,2
*G05\Q3,1(logic programming languages, functional languages)
*G05\Q4,1(Object oriented programming languages)
*G04\Q1,1(structured programming)
*G04\Q9,1
*G04\Q90,2(functional, logic, object oriented, imperative)
*G03\Q24,1(statically typed language, dynamically typed, un typed)
*G03\Q73,2(static scoping, call-by-need)
*G03\Q74,2(dynamic scoping,call-by-name)
*G03\Q75,2(object oriented language, inheritance, dynamic binding)
*G03\Q76,2(shared statically/dynamically linked libraries)
10. Max Heap
*G06\Q76,2
*G06\Q77,2
*G05\Q34,2 (priority queue)
*G04\Q37,2
*G03\Q23,1
11. Circular Linked lists
*G04\Q36,2(queue)
12. Postfix , infix, prefix
*G04\Q38,2
VI. Algorithms
1. Time complexity
*G07\Q14,1 ( Sorting & Worst case Time complexity)
*G07\Q15,1(C-program given, find time complexity)
*G07\Q41,2 (undirected connected graph, shortest path, Dijkstra's algo , Warshalls algo, BFS, DFS)
*G07\Q45,2 (recursion)
*G07\Q51,2 (timing complexity of a C program)
*G06\Q10,1(binary max heap , smallest element)
*G06\Q17,1(array-leader)
*G06\Q,2(quick sort)
*G06\Q54,2
*G05\Q7,1 (transitive closure of a binary relation )
*G05\Q38,2(Dijkstra's single source shortest path algo , binary heap)
*G05\Q38,2(heap)
*G04\Q39,2(matrix multiplication , RMO, CMO)
*G04\Q40,2(linked list, union, intersection.. )
*G04\Q82,2(C-program)
*G04\Q83,2(C-program)
*G04\Q85,2(worst case, BST)
*G03\Q11,1(array multiplier)
*G03\Q20,1
*G03\Q22,1(Insertion sort,array, binary search)
*G03\Q23,1(heap,smallest element)
*G03\Q62,2(Insertion sort, worse case )
*G03\Q66,2(cube root)
2. Asymptotic notations
*G07\Q44,2
*G07\Q47,2 (Max heap)
*G06\Q15,1
3. Minimum spanning tree
*G07\Q49,2
*G06\Q11,1 (weighted complete graph)
*G06\Q47,2(Kruskal's Algorithm)
*G05\Q26,1 (LAN)
4. No of comparisons needed
*G07\Q50,2 ( Find max and min of an array)
*G04\Q29,1(comparison based sorting)
5. Huffman Coding
*G07\Q76,2
*G07\Q77,2
6. Robot movement and permutations
*G07\Q84,2
*G07\Q85,2
7. Dijkstra's shortest path Algorithm
*G06\Q12,1
*G04\Q44,2
*G03\Q67,2(single source shortest path)
8. Sorting
*G06\Q14,1(quick sort, Insertion sort, Selection sort , Heap sort)
9.DFS
*G06\Q48,2
*G06\Q82,2 (spanning tree)
*G03\Q21,1
10. Recurrence relations
*G06\Q51,2
*G05\Q37,2
*G04\Q84,2
*G03\Q35,2
11. Space complexity
*G05\Q81a,2
*G05\Q81b,2
12. Job scheduling with dead lines
*G05\Q84a,2
*G05\Q84b,2
VII. Compiler Design
1. Parsers
*G07\Q18,1 (Top down parsers)
*G03\Q17,1(SLR, LALR)
2. Grammar
*G07\Q52,2( LL1 grammar)
*G07\Q53,2(regular grammar,LR(1) grammar, regular set)
*G06\Q7,1 ( LR(0) items, canonical sets of items )
*G06\Q58,2(predictive parser table)
*G06\Q59,2 (translation scheme)
*G05\Q14,1(predictive parsing, ambiguous, left recursive, right recursive, an operator grammar)
*G05\Q59,2(right sentential form)
*G05\Q60,2(SLR(1),LR(1),LALR(1))
*G05\Q83a,2(yacc, LALR(1) parser generator, reduce-reduce conflict, shift-reduce conflict
*G05\Q83b,2(precedence and left\right associativity)
*G04\Q8,1(operator grammar)
*G04\Q88,2(language generated)
*G03\Q16,1(LL(1), CFG, left recursion, factoring)
*G03\Q39,2
*G03\Q56,2(predictive parse table)
*G03\Q57,2(LL(1), LALR(1),SLR(1),LR(1))
3. Strings generated by a given grammar
*G07\Q78,2
4. Number of derivation trees for a string generated by a grammar
*G07\Q79,2
5.Code Optimization
*G06\Q61,2
*G04\Q10,1
6. SDT
*G04\Q45,2
*G03\Q18,1
*G03\Q58,2
*G03\Q59,2
VIII. Operating System
1. CPU scheduling
*G07\Q16,1
2. User level and Kernel level threads
*G07\Q17,1
*G04\Q11,1
3.Scheduling
*G07\Q55,2 (SRT first scheduling algorithm)
*G06\Q6,1 (Shortest remaining time first scheduling algorithm)
*G06\Q64,2(longest remaining time first scheduling)
*G06\Q65,2(shortest remaining compute time first scheduling)
*G04\Q12,1(FCFS,shortest seek time first)
*G04\Q46,2(Shortest remaining process time first)
*G03\Q69,2
*G03\Q77,2(FCFS,SRTF,round robin with time quantum, static priority scheduling)
4. Page replacement policies
*G07\Q56,2 (FIFO, Bellady's anomaly)
*G07\Q82,2(optimal page replacement policy)
*G07\Q83,2(LRU)
*G05\Q22,1 (page faults )
5. Resource allocation
*G07\Q57,2
6.Synchronization and deadlocks
*G07\Q58,2
*G06\Q66,2 (deadlock)
*G06\Q78,2(semaphore)
*G06\Q79,2
*G05\Q71,2 (deadlock)
*G05\Q72,2(fork)
*G04\Q47,2(binary semaphore)
*G03\Q80,2(binary semaphores)
*G03\Q81,2(binary semaphores)
7. Paging
*G06\Q62,2(TLB, 4-way set associative)
*G04\Q47,2(TLB,2-level paging)
*G03\Q26,1(fragmentation)
*G03\Q78,2(TLB,paging)
*G03\Q79,2(paging)
8. virtual memory
*G06\Q63,2
*G04\Q21,1(number of page frames)
9. Disk
*G05\Q21,1 (swap space)
*G05\Q70,2(DMA,cycle stealing mode, disk specifications)
*G04\Q68,2(DMA,processor time)
10. Files
*G04\Q49,2(i-node,file size)
*G03\Q25,1
IX. Databases
1. Relational algebra
*G07\Q59,2
*G05\Q30,1
*G04\Q13,1 (referential integrity)
*G04\Q51,2
*G03\Q30,1(sql)
2. Relational Calculus
*G07\Q60,2
3. SQL
*G07\Q61,2
*G06\Q67,2
*G06\Q68,2
*G05\Q77,2
*G04\Q53,2
*G03\Q30,1(relational algebra)
*G03\Q86,2
4. Normal forms
*G07\Q48,2 (Conjuntive Normal Form)
*G07\Q62,2 (BCNF,2NF,3NF)
*G05\Q29,1
*G04\Q50,2(functional dependencies)
*G03\Q85,2(BCNF,2nd normal form)
5. B+ trees
*G07\Q63,2 (order of leaf node)
*G05\Q28,1
*G04\Q52,2
6.Transactions
*G07\Q64,2 (Conflict serializability)
*G06\Q20,1
*G03\Q29,1(committed)
*G03\Q87,2(serializable)
7. Query plans
*G06\Q69,2
8. Functional Dependencies
*G06\Q70,2
9. ER diagrams
*G05\Q75,2
10. Referential Integrity
*G05\Q76,2
11. Functional dependencies
*G05\Q78,2 (candidate keys)
12. Natural join
*G04\Q14,1
13. Database design
*G04\Q34,2
X. Computer Networks
1. Ethernet
*G07\Q19,1 (Manchester encoding, bit rate, baud rate)
*G06\Q82,2
*G06\Q83,2
*G05\Q74,2(round trip propagation delay, jamming signal, frame size)
*G04\Q54,2(probability)
*G03\Q83,2(CSMA/CD,packet size)
2. UDP and TCP
*G07\Q20,1
*G05\Q23,1
3. Slotted LAN
*G07\Q65,2 (probability)
4.Token ring
*G07\Q66,2 (bit delay)
5. Subnetting
*G07\Q67,2 (max num of subnets and hosts)
*G06\Q45,2 (netmask)
*G05\Q27,1
*G03\Q82,2
6. CRC polynomial
*G07\Q68,2
7. Sliding window protocol
*G07\Q69,2 (number of bits in sequence number)
*G06\Q44,2(round trip delay, bandwidth, optimal window size)
*G06\Q46,2
*G05\Q25,1 (selective reject protocol)
8. Protocols
*G07\Q70,2 (SMTP,BGP,TCP,PPP)
*G06\Q5,1(IP,TTL)
*G05\Q24,1 (ARP)
*G03\Q27,1(IP)
*G03\Q28,1(TCP)
9. Packet switching
*G05\Q73,2
10. Layers
*G04\Q15,1
11. Network devices
*G04\Q16,1(bridge,router,IP address , MAC address)
12. Data Transmission
*G04\Q22,1
*G04\Q56,2
*G04\Q57,2
*G03\Q84,2
13. Routing
*G04\Q55,2
No comments:
Post a Comment