Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) (→Compiler Design) |
||
(34 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
+ | {{alert| Some missing links for topics do not mean that they were never asked for GATE. I'll add their links soon after correcting the corresponding tags in [http://gateoverflow.in/tags GATE Overflow] |alert-danger}} | ||
− | ==Discrete Mathematics== | + | ==Official Syllabus Links== |
+ | [http://www.gate.iisc.ernet.in/wp-content/uploads/2015/06/Computer-Science-and-Information-Technology.pdf Computer Science] | ||
+ | |||
+ | [http://gate.iitk.ac.in/GATE2015/docs/syllabi/GA.pdf General Aptitude] | ||
+ | |||
+ | ==[http://www.gatecse.in/gate-subjects/ Discrete Mathematics]== | ||
*[http://gateoverflow.in/tag/mathematical-logic Propositional and first order logic.] | *[http://gateoverflow.in/tag/mathematical-logic Propositional and first order logic.] | ||
− | *Sets, relations, functions, partial orders and lattices. Groups. | + | *[http://gateoverflow.in/tag/set Sets], [http://gateoverflow.in/tag/relations relations], [http://gateoverflow.in/tag/functions functions], [http://gateoverflow.in/tag/partial-order partial orders] and [http://gateoverflow.in/tag/lattice lattices]. [http://gateoverflow.in/tag/groups Groups]. |
− | * Graphs: connectivity, matching, coloring. | + | * Graphs: [http://gateoverflow.in/tag/graph-connectivity connectivity], [http://gateoverflow.in/tag/graph-matching matching], [http://gateoverflow.in/tag/graph-coloring coloring]. |
− | * [http://gateoverflow.in/tag/combinatory Combinatorics:] counting,[http://gateoverflow.in/tag/recurrence recurrence relations], generating functions. | + | * [http://gateoverflow.in/tag/combinatory Combinatorics:] [http://gateoverflow.in/tag/counting counting], [http://gateoverflow.in/tag/recurrence recurrence relations], [http://gateoverflow.in/tag/generating-functions generating functions]. |
'''Boolean Algebra''' moved to Digital Logic. | '''Boolean Algebra''' moved to Digital Logic. | ||
− | '''Permutations; Combinations''' removed from Combinatorics but being basic and counting being there this does not really matter. | + | '''[http://gateoverflow.in/tag/permutation Permutations]; [http://gateoverflow.in/tag/combinations Combinations]''' removed from Combinatorics but being basic and counting being there this does not really matter. |
'''asymptotics''' removed, but basics are in asymptotic analysis part of Algorithms | '''asymptotics''' removed, but basics are in asymptotic analysis part of Algorithms | ||
− | '''spanning trees; Cut vertices & edges; covering; independent sets; Planarity; Isomorphism''' removed. But based on other topics this just means Planarity and isomorphism are removed (spanning trees are already in algorithms) | + | '''spanning trees; Cut vertices & edges; covering; independent sets; [http://gateoverflow.in/tag/planar-embedding Planarity]; [http://gateoverflow.in/tag/isomorphism Isomorphism]''' removed. But based on other topics this just means Planarity and isomorphism are removed (spanning trees are already in algorithms) |
− | ==Linear Algebra== | + | ==[http://www.gatecse.in/linear-algebra/ Linear Algebra]== |
− | *Matrices, determinants | + | *[http://gateoverflow.in/tag/matrices Matrices, determinants] |
− | *System of linear equations | + | *[http://gateoverflow.in/tag/system-of-equations System of linear equations] |
− | *Eigenvalues and eigenvectors | + | *[http://gateoverflow.in/tag/eigen-value Eigenvalues and eigenvectors] |
*LU decomposition | *LU decomposition | ||
'''LU decomposition''' added here from Numerical methods which was removed as a whole otherwise. | '''LU decomposition''' added here from Numerical methods which was removed as a whole otherwise. | ||
− | ==Calculus== | + | ==[http://www.gatecse.in/calculus/ Calculus]== |
− | * Limits, continuity and differentiability. | + | * [http://gateoverflow.in/tag/limit Limits], [http://gateoverflow.in/tag/continuity continuity] and [http://gateoverflow.in/tag/differentiability differentiability]. |
− | * Maxima and minima. Mean value theorem. | + | * [http://gateoverflow.in/tag/maxima-minima Maxima and minima]. Mean value theorem. |
− | * Integration. | + | * [http://gateoverflow.in/tag/integration Integration]. |
− | '''Theorems of integral calculus, evaluation of definite & improper integrals, Partial derivatives, Total derivatives''' | + | '''Theorems of integral calculus, evaluation of definite & improper integrals, Partial derivatives, Total derivatives''' removed and '''Integration''' added. So, this would mean we can expect only simple integration questions. |
− | ==Probability== | + | ==[http://www.gatecse.in/probability/ Probability]== |
− | * Random variables. | + | *[http://gateoverflow.in/tag/random-variable Random variables]. |
− | *Uniform, normal, exponential, poisson and binomial distributions. | + | *Uniform, [http://gateoverflow.in/tag/normal-distribution normal], [http://gateoverflow.in/tag/exponential-distribution exponential], [http://gateoverflow.in/tag/poisson-distribution poisson] and [http://gateoverflow.in/tag/binomial-distribution binomial distributions]. |
− | *Mean, median, mode and standard deviation. | + | *[http://gateoverflow.in/tag/statistics Mean, median, mode and standard deviation]. |
*Conditional probability and Bayes theorem. | *Conditional probability and Bayes theorem. | ||
'''Bayes theorem''' newly added but it was implicitly part of conditional probability | '''Bayes theorem''' newly added but it was implicitly part of conditional probability | ||
− | ==Digital Logic== | + | ==[http://www.gatecse.in/digital-logic/ Digital Logic]== |
− | *Boolean algebra. | + | *[http://gateoverflow.in/tag/boolean-expressions Boolean algebra]. |
− | *[http://gateoverflow.in/tag/circuit-output Combinational and sequential circuits.] Minimization. | + | *[http://gateoverflow.in/tag/circuit-output Combinational and sequential circuits.] [http://gateoverflow.in/tag/canonical-normal-form Minimization]. |
− | *Number representations and computer arithmetic (fixed and floating point). | + | *[http://gateoverflow.in/tag/number-representation Number representations] and computer arithmetic (fixed and [http://gateoverflow.in/tag/floating-point-representation floating point]). |
'''Boolean algebra''' added to here from set theory & algebra | '''Boolean algebra''' added to here from set theory & algebra | ||
− | ==Computer Organization and Architecture== | + | ==[http://www.gatecse.in/co-architecture/ Computer Organization and Architecture]== |
− | *Machine instructions and addressing modes. | + | *[http://gateoverflow.in/tag/machine-instructions Machine instructions] and [http://gateoverflow.in/tag/addressing-modes addressing modes]. |
− | *ALU, data‐path and control unit. | + | *[http://gateoverflow.in/tag/microprogramming ALU, data‐path and control unit]. |
*[http://gateoverflow.in/tag/pipeline Instruction pipelining.] | *[http://gateoverflow.in/tag/pipeline Instruction pipelining.] | ||
* [http://gateoverflow.in/tag/cache-memory Memory hierarchy: cache, main memory and secondary storage;] | * [http://gateoverflow.in/tag/cache-memory Memory hierarchy: cache, main memory and secondary storage;] | ||
− | * I/O interface ( | + | * [http://gateoverflow.in/tag/io-handling I/O interface]. ([http://gateoverflow.in/tag/interrupts Interrupt] and [http://gateoverflow.in/tag/dma DMA mode]) |
− | ''' Memory interface''' part is removed. So, questions on RAM would not be there. | + | '''[http://gateoverflow.in/tag/ram Memory interface]''' part is removed. So, questions on RAM would not be there. |
− | ==Programming and Data Structures== | + | ==[http://www.gatecse.in/data-structures/ Programming and Data Structures]== |
− | *[http://gateoverflow.in/tag/programming-in-c Programming in C.] Recursion. | + | *[http://gateoverflow.in/tag/programming-in-c Programming in C.] [http://gateoverflow.in/tag/recursion Recursion]. |
− | *Arrays, stacks, queues, linked lists, trees, binary search trees, binary heaps, graphs. | + | *[http://gateoverflow.in/tag/arrays Arrays], [http://gateoverflow.in/tag/stack stacks], [http://gateoverflow.in/tag/queues queues], [http://gateoverflow.in/tag/linked-lists linked lists], [http://gateoverflow.in/tag/trees trees], [http://gateoverflow.in/tag/binary-tree binary search trees], [http://gateoverflow.in/tag/heap binary heaps], graphs. |
− | '''Functions, Parameter passing, Scope, Binding; Abstract data types''' removed. So, questions like pass by reference, static-dynamic scopes, etc would not be there. | + | '''Functions, Parameter passing, Scope, [http://gateoverflow.in/tag/variable-binding Binding]; Abstract data types''' removed. So, questions like pass by reference, static-dynamic scopes, etc would not be there. |
− | '''Graphs''' added here. | + | '''Graphs''' added here. |
− | ==Algorithms== | + | ==[http://www.gatecse.in/algorithms/ Algorithms]== |
− | *Searching,[http://gateoverflow.in/tag/sorting sorting], hashing. | + | *[http://gateoverflow.in/tag/binary-search Searching], [http://gateoverflow.in/tag/sorting sorting], [http://gateoverflow.in/tag/hashing hashing]. |
− | *[http://gateoverflow.in/tag/time-complexity Asymptotic worst case time and space complexity.] | + | *[http://gateoverflow.in/tag/time-complexity Asymptotic worst case time] and [http://gateoverflow.in/tag/space-complexity space complexity.] |
− | *Algorithm design techniques: greedy, dynamic programming and divide‐and‐conquer. | + | *Algorithm design techniques: [http://gateoverflow.in/tag/greedy-algorithm greedy], [http://gateoverflow.in/tag/dynamic-programming dynamic programming] and divide‐and‐conquer. |
− | *Graph search, minimum spanning trees, shortest paths. | + | *[http://gateoverflow.in/tag/graph-search Graph search], [http://gateoverflow.in/tag/spanning-tree minimum spanning trees], [http://gateoverflow.in/tag/shortest-path shortest paths]. |
'''Space and time complexity''' restricted to only worst case. | '''Space and time complexity''' restricted to only worst case. | ||
− | '''Connected components''' removed | + | '''[http://gateoverflow.in/tag/connected-components Connected components]''' removed here, but they are in Graph theory anyway |
− | '''Tree and graph traversals''' removed. But these are implied in Data Structure portion. | + | '''Tree and graph traversals''' removed. But these are implied in Data Structure portion and other algorithm portions. |
− | '''Basic concepts of complexity classes – P, NP, NP-hard, NP-complete. ''' removed. So, these definitions need not be studied but reduction is there in Theory of Computation anyway. | + | '''Basic concepts of complexity classes – [http://gateoverflow.in/tag/p-np-npc-nph P, NP, NP-hard, NP-complete]. ''' removed. So, these definitions need not be studied but reduction is there in Theory of Computation anyway. |
− | |||
− | ==Theory of Computation== | + | ==[http://www.gatecse.in/theory-of-computation/ Theory of Computation]== |
− | *[http://gateoverflow.in/tag/regular-expressions Regular expressions] and finite automata. | + | *[http://gateoverflow.in/tag/regular-expressions Regular expressions] and [http://gateoverflow.in/tag/finite-automata finite automata]. |
− | *[http://gateoverflow.in/tag/grammar Context-free grammars] and push-down automata. | + | *[http://gateoverflow.in/tag/grammar Context-free grammars] and [http://gateoverflow.in/tag/pda push-down automata]. |
*[http://gateoverflow.in/tag/regular-set Regular] and [http://gateoverflow.in/tag/context-free context-free languages], pumping lemma. | *[http://gateoverflow.in/tag/regular-set Regular] and [http://gateoverflow.in/tag/context-free context-free languages], pumping lemma. | ||
− | *Turing machines and undecidability. | + | *[http://gateoverflow.in/tag/turing-machine Turing machines] and [http://gateoverflow.in/tag/decidability undecidability]. |
'''pumping lemma''' newly added. So, questions based on pumping length or some examples can be asked. | '''pumping lemma''' newly added. So, questions based on pumping length or some examples can be asked. | ||
'''Recursively enumerable sets''' removed but Turing machines are there. So, this should not really matter. | '''Recursively enumerable sets''' removed but Turing machines are there. So, this should not really matter. | ||
− | ==Compiler Design== | + | ==[http://www.gatecse.in/compiler-design/ Compiler Design]== |
− | *Lexical analysis, [http://gateoverflow.in/tag/parsing parsing], syntax-directed translation. | + | *[http://gateoverflow.in/tag/lexical-analysis Lexical analysis], [http://gateoverflow.in/tag/parsing parsing], [http://gateoverflow.in/tag/syntax-directed-translation syntax-directed translation]. |
− | *Runtime environments. | + | *[http://gateoverflow.in/tag/runtime-environments Runtime environments]. |
− | *Intermediate code generation. | + | *[http://gateoverflow.in/tag/intermediate-code Intermediate code generation]. |
− | '''target code generation, Basics of code optimization.''' removed. This is quite a good removal for students. Questions like register allocation, | + | '''[http://gateoverflow.in/tag/code-generation target code generation], [http://gateoverflow.in/tag/optimization Basics of code optimization].''' removed. This is quite a good removal for students. Questions like register allocation, optimizations like code motion etc. would not be there |
− | ==Operating System== | + | ==[http://www.gatecse.in/operating-systems/ Operating System]== |
− | *Processes, threads, inter‐process communication, [http://gateoverflow.in/tag/process-synchronization concurrency and synchronization.] | + | *[http://gateoverflow.in/tag/fork Processes], [http://gateoverflow.in/tag/threads threads], [http://gateoverflow.in/tag/semaphore inter‐process communication], [http://gateoverflow.in/tag/process-synchronization concurrency and synchronization.] |
− | *Deadlock. | + | *[http://gateoverflow.in/tag/resource-allocation Deadlock.] |
*[http://gateoverflow.in/tag/process-schedule CPU scheduling.] | *[http://gateoverflow.in/tag/process-schedule CPU scheduling.] | ||
− | *[http://gateoverflow.in/tag/ | + | *[http://gateoverflow.in/tag/memory-management Memory management] and [http://gateoverflow.in/tag/virtual-memory virtual memory.] |
− | *[http://gateoverflow.in/tag/disk File systems.] | + | *[http://gateoverflow.in/tag/disk-scheduling File systems.] [http://gateoverflow.in/tag/disk Disks is also under this] |
− | '''I/O systems, Protection and security''' removed. | + | '''I/O systems, Protection and security''' removed. Rarely questions like size of graphic card required etc have been asked. |
− | ==Databases== | + | ==[http://www.gatecse.in/databases/ Databases]== |
− | *ER‐model. Relational model: relational algebra,[http://gateoverflow.in/tag/relational-calculus tuple calculus],[http://gateoverflow.in/tag/sql SQL]. | + | *[http://gateoverflow.in/tag/er-model ER‐model]. Relational model:[http://gateoverflow.in/tag/relational-algebra relational algebra], [http://gateoverflow.in/tag/relational-calculus tuple calculus],[http://gateoverflow.in/tag/sql SQL]. |
− | *Integrity constraints, | + | *[http://gateoverflow.in/tag/referential-integrity Integrity constraints], |
*[http://gateoverflow.in/tag/database-normalization normal forms.] | *[http://gateoverflow.in/tag/database-normalization normal forms.] | ||
− | *File organization, [http://gateoverflow.in/tag/b-tree indexing (e.g., B and B+ trees)]. | + | *[http://gateoverflow.in/tag/indexing File organization], [http://gateoverflow.in/tag/b-tree indexing (e.g., B and B+ trees)]. |
− | *Transactions and concurrency control. | + | *[http://gateoverflow.in/tag/transactions Transactions and concurrency control]. |
No change | No change | ||
− | + | ==[http://www.gatecse.in/computer-networks/ Computer Networks]== | |
− | ==Computer Networks== | + | *[http://gateoverflow.in/tag/network-layering Concept of layering]. [http://gateoverflow.in/tag/lan-technologies LAN technologies (Ethernet)]. |
− | *Concept of layering. LAN technologies (Ethernet). | + | *[http://gateoverflow.in/tag/sliding-window Flow] and [http://gateoverflow.in/tag/error-detection error control] techniques, |
− | *Flow and error control techniques, | + | *[http://gateoverflow.in/tag/network-switching switching]. |
− | *switching. | + | *[http://gateoverflow.in/tag/ip-packet IPv4]/IPv6, |
− | *IPv4/IPv6, | + | *[http://gateoverflow.in/tag/routing routers and routing algorithms (distance vector, link state)]. |
− | *routers and routing algorithms (distance vector, link state). | + | *[http://gateoverflow.in/tag/tcp TCP]/[http://gateoverflow.in/tag/udp UDP] and [http://gateoverflow.in/tag/sockets sockets], [http://gateoverflow.in/tag/congestion-control congestion control]. |
− | *TCP/UDP and sockets, congestion control. | + | *[http://gateoverflow.in/tag/application-layer-protocols Application layer protocols (DNS, SMTP, POP, FTP, HTTP)]. |
− | *Application layer protocols (DNS, SMTP, POP, FTP, HTTP). | ||
*Basics of Wi-Fi. | *Basics of Wi-Fi. | ||
− | *Network security: authentication, basics of public key and private key cryptography, digital signatures and certificates, firewalls. | + | *[http://gateoverflow.in/tag/network-security Network security: authentication, basics of public key and private key cryptography, digital signatures and certificates], [http://gateoverflow.in/tag/firewall firewalls]. |
'''IPv6''' added | '''IPv6''' added | ||
− | ''' | + | '''[http://gateoverflow.in/tag/token-ring Token Ring]''' removed |
− | '''Basics of Wi-Fi''' added | + | '''Basics of Wi-Fi''' added |
+ | '''[http://gateoverflow.in/tag/routers-bridge-hubs-switches Basic concepts of hubs, switches, gateways, and routers]''' removed | ||
+ | '''[http://gateoverflow.in/tag/subnettting Subnetting]''' is an important part under IP. | ||
+ | |||
+ | ==General Aptitude== | ||
+ | *No change in [http://www.gatecse.in/numerical-ability/ Numerical Ability] as well as [http://www.gatecse.in/verbal-ability/ Verbal Ability]. | ||
==Removals== | ==Removals== | ||
Line 119: | Line 128: | ||
'''Numerical Methods:''' LU decomposition for systems of linear equations; numerical solutions of non-linear algebraic equations by Secant, Bisection and Newton-Raphson Methods; Numerical integration by trapezoidal and Simpson’s rules. | '''Numerical Methods:''' LU decomposition for systems of linear equations; numerical solutions of non-linear algebraic equations by Secant, Bisection and Newton-Raphson Methods; Numerical integration by trapezoidal and Simpson’s rules. | ||
− | + | {{Template:FBD}} | |
[[Category:GATE]] | [[Category:GATE]] |
Boolean Algebra moved to Digital Logic. Permutations; Combinations removed from Combinatorics but being basic and counting being there this does not really matter. asymptotics removed, but basics are in asymptotic analysis part of Algorithms spanning trees; Cut vertices & edges; covering; independent sets; Planarity; Isomorphism removed. But based on other topics this just means Planarity and isomorphism are removed (spanning trees are already in algorithms)
LU decomposition added here from Numerical methods which was removed as a whole otherwise.
Theorems of integral calculus, evaluation of definite & improper integrals, Partial derivatives, Total derivatives removed and Integration added. So, this would mean we can expect only simple integration questions.
Bayes theorem newly added but it was implicitly part of conditional probability
Boolean algebra added to here from set theory & algebra
Memory interface part is removed. So, questions on RAM would not be there.
Functions, Parameter passing, Scope, Binding; Abstract data types removed. So, questions like pass by reference, static-dynamic scopes, etc would not be there. Graphs added here.
Space and time complexity restricted to only worst case. Connected components removed here, but they are in Graph theory anyway Tree and graph traversals removed. But these are implied in Data Structure portion and other algorithm portions. Basic concepts of complexity classes – P, NP, NP-hard, NP-complete. removed. So, these definitions need not be studied but reduction is there in Theory of Computation anyway.
pumping lemma newly added. So, questions based on pumping length or some examples can be asked. Recursively enumerable sets removed but Turing machines are there. So, this should not really matter.
target code generation, Basics of code optimization. removed. This is quite a good removal for students. Questions like register allocation, optimizations like code motion etc. would not be there
I/O systems, Protection and security removed. Rarely questions like size of graphic card required etc have been asked.
No change
IPv6 added Token Ring removed Basics of Wi-Fi added Basic concepts of hubs, switches, gateways, and routers removed Subnetting is an important part under IP.
Except LU decomposition, all portions of Web Technologies, IS & Software Engineering and Numerical Methods are removed.
Web technologies: HTML, XML, basic concepts of client-server computing.
Information Systems and Software Engineering: information gathering, requirement and feasibility analysis, data flow diagrams, process specifications, input/output design, process life cycle, planning and managing the project, design, coding, testing, implementation, maintenance
Numerical Methods: LU decomposition for systems of linear equations; numerical solutions of non-linear algebraic equations by Secant, Bisection and Newton-Raphson Methods; Numerical integration by trapezoidal and Simpson’s rules.
Boolean Algebra moved to Digital Logic. Permutations; Combinations removed from Combinatorics but being basic and counting being there this does not really matter. asymptotics removed, but basics are in asymptotic analysis part of Algorithms spanning trees; Cut vertices & edges; covering; independent sets; Planarity; Isomorphism removed. But based on other topics this just means Planarity and isomorphism are removed (spanning trees are already in algorithms)
LU decomposition added here from Numerical methods which was removed as a whole otherwise.
Theorems of integral calculus, evaluation of definite & improper integrals, Partial derivatives, Total derivatives is removed and Integration added. So, this would mean we can expect only simple integration questions.
Bayes theorem newly added but it was implicitly part of conditional probability
Boolean algebra added to here from set theory & algebra
Memory interface part is removed. So, questions on RAM would not be there.
Functions, Parameter passing, Scope, Binding; Abstract data types removed. So, questions like pass by reference, static-dynamic scopes, etc would not be there. Graphs added here.
Space and time complexity restricted to only worst case. Connected components removed Tree and graph traversals removed. But these are implied in Data Structure portion. Basic concepts of complexity classes – P, NP, NP-hard, NP-complete. removed. So, these definitions need not be studied but reduction is there in Theory of Computation anyway.
pumping lemma newly added. So, questions based on pumping length or some examples can be asked. Recursively enumerable sets removed but Turing machines are there. So, this should not really matter.
target code generation, Basics of code optimization. removed. This is quite a good removal for students. Questions like register allocation, DAG etc. would not be there
I/O systems, Protection and security removed. But I do not remember any question from these portions.
No change
IPv6 added icmp removed Basics of Wi-Fi added
Except LU decomposition, all portions of Web Technologies, IS & Software Engineering and Numerical Methods are removed.
Web technologies: HTML, XML, basic concepts of client-server computing.
Information Systems and Software Engineering: information gathering, requirement and feasibility analysis, data flow diagrams, process specifications, input/output design, process life cycle, planning and managing the project, design, coding, testing, implementation, maintenance
Numerical Methods: LU decomposition for systems of linear equations; numerical solutions of non-linear algebraic equations by Secant, Bisection and Newton-Raphson Methods; Numerical integration by trapezoidal and Simpson’s rules.