|
|
| (40 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== |
| − | *Propositional and first order logic.
| + | [http://www.gate.iisc.ernet.in/wp-content/uploads/2015/06/Computer-Science-and-Information-Technology.pdf Computer Science] |
| − | *Sets, relations, functions, partial orders and lattices. Groups.
| |
| − | * Graphs: connectivity, matching, coloring.
| |
| − | * Combinatorics: counting, recurrence relations, generating functions.
| |
| | | | |
| − | '''Boolean Algebra''' moved to Digital Logic.
| + | [http://gate.iitk.ac.in/GATE2015/docs/syllabi/GA.pdf General Aptitude] |
| − | '''Permutations; Combinations''' removed from Combinatorics but being basic and counting being there this doesn't 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.
| |
| | | | |
| − | ==Linear Algebra== | + | ==[http://www.gatecse.in/gate-subjects/ Discrete Mathematics]== |
| − | *Matrices, determinants | + | *[http://gateoverflow.in/tag/mathematical-logic Propositional and first order logic.] |
| − | *System of linear equations | + | *[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]. |
| − | *Eigenvalues and eigenvectors | + | * 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:] [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. |
| | + | '''[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 |
| | + | '''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) |
| | + | |
| | + | ==[http://www.gatecse.in/linear-algebra/ Linear Algebra]== |
| | + | *[http://gateoverflow.in/tag/matrices Matrices, determinants] |
| | + | *[http://gateoverflow.in/tag/system-of-equations System of linear equations] |
| | + | *[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''' is removed and '''Integration''' added. So, this would mean we can expect only simple integration questions. | + | '''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 |
| | + | |
| | + | ==[http://www.gatecse.in/digital-logic/ Digital Logic]== |
| | + | |
| | + | *[http://gateoverflow.in/tag/boolean-expressions Boolean algebra]. |
| | + | *[http://gateoverflow.in/tag/circuit-output Combinational and sequential circuits.] [http://gateoverflow.in/tag/canonical-normal-form Minimization]. |
| | + | *[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 |
| | | | |
| − | ==Digital Logic== | + | ==[http://www.gatecse.in/co-architecture/ Computer Organization and Architecture]== |
| | | | |
| − | *Boolean algebra. | + | *[http://gateoverflow.in/tag/machine-instructions Machine instructions] and [http://gateoverflow.in/tag/addressing-modes addressing modes]. |
| − | *Combinational and sequential circuits. Minimization. | + | *[http://gateoverflow.in/tag/microprogramming ALU, data‐path and control unit]. |
| − | *Number representations and computer arithmetic (fixed and floating point). | + | *[http://gateoverflow.in/tag/pipeline Instruction pipelining.] |
| − | '''Boolean algebra''' added to here from set theory & algebra | + | * [http://gateoverflow.in/tag/cache-memory Memory hierarchy: cache, main memory and secondary storage;] |
| | + | * [http://gateoverflow.in/tag/io-handling I/O interface]. ([http://gateoverflow.in/tag/interrupts Interrupt] and [http://gateoverflow.in/tag/dma DMA mode]) |
| | + | '''[http://gateoverflow.in/tag/ram Memory interface]''' part is removed. So, questions on RAM would not be there. |
| | | | |
| − | ==Computer Organization and Architecture== | + | ==[http://www.gatecse.in/data-structures/ Programming and Data Structures]== |
| | + | *[http://gateoverflow.in/tag/programming-in-c Programming in C.] [http://gateoverflow.in/tag/recursion Recursion]. |
| | + | *[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, [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. |
| | | | |
| − | *Machine instructions and addressing modes. | + | ==[http://www.gatecse.in/algorithms/ Algorithms]== |
| − | *ALU, data‐path and control unit. | + | *[http://gateoverflow.in/tag/binary-search Searching], [http://gateoverflow.in/tag/sorting sorting], [http://gateoverflow.in/tag/hashing hashing]. |
| − | *Instruction pipelining. | + | *[http://gateoverflow.in/tag/time-complexity Asymptotic worst case time] and [http://gateoverflow.in/tag/space-complexity space complexity.] |
| − | * Memory hierarchy: cache, main memory and secondary storage;
| + | *Algorithm design techniques: [http://gateoverflow.in/tag/greedy-algorithm greedy], [http://gateoverflow.in/tag/dynamic-programming dynamic programming] and divide‐and‐conquer. |
| − | * I/O interface (interrupt and DMA mode).
| + | *[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]. |
| − | ''' Memory interface''' part is removed. So, questions on RAM won't be there. | + | '''Space and time complexity''' restricted to only worst case. |
| | + | '''[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 and other algorithm portions. |
| | + | '''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. |
| | | | |
| − | ==Programming and Data Structures== | + | ==[http://www.gatecse.in/theory-of-computation/ Theory of Computation]== |
| − | *Programming in C. Recursion. | + | *[http://gateoverflow.in/tag/regular-expressions Regular expressions] and [http://gateoverflow.in/tag/finite-automata finite automata]. |
| − | *Arrays, stacks, queues, linked lists, trees, binary search trees, binary heaps, graphs. | + | *[http://gateoverflow.in/tag/grammar Context-free grammars] and [http://gateoverflow.in/tag/pda push-down automata]. |
| − | '''Functions, Parameter passing, Scope, Binding; Abstract data types''' removed. So, questions like pass by reference, static-dynamic scopes, etc won't be there. | + | *[http://gateoverflow.in/tag/regular-set Regular] and [http://gateoverflow.in/tag/context-free context-free languages], pumping lemma. |
| − | '''Graphs''' added here. | + | *[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. |
| | + | '''Recursively enumerable sets''' removed but Turing machines are there. So, this should not really matter. |
| | | | |
| − | ==Algorithms== | + | ==[http://www.gatecse.in/compiler-design/ Compiler Design]== |
| − | *Searching, sorting, hashing. | + | *[http://gateoverflow.in/tag/lexical-analysis Lexical analysis], [http://gateoverflow.in/tag/parsing parsing], [http://gateoverflow.in/tag/syntax-directed-translation syntax-directed translation]. |
| − | *Asymptotic worst case time and space complexity.
| + | *[http://gateoverflow.in/tag/runtime-environments Runtime environments]. |
| − | *Algorithm design techniques: greedy, dynamic programming and divide‐and‐conquer. | + | *[http://gateoverflow.in/tag/intermediate-code Intermediate code generation]. |
| − | *Graph search, minimum spanning trees, shortest paths. | + | '''[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 |
| − | '''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 needn't be studied but reduction is there in Theory of Computation anyway.
| |
| | | | |
| | + | ==[http://www.gatecse.in/operating-systems/ Operating System]== |
| | + | *[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.] |
| | + | *[http://gateoverflow.in/tag/resource-allocation Deadlock.] |
| | + | *[http://gateoverflow.in/tag/process-schedule CPU scheduling.] |
| | + | *[http://gateoverflow.in/tag/memory-management Memory management] and [http://gateoverflow.in/tag/virtual-memory virtual memory.] |
| | + | *[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. Rarely questions like size of graphic card required etc have been asked. |
| | | | |
| − | ==Theory of Computation== | + | ==[http://www.gatecse.in/databases/ Databases]== |
| − | *Regular expressions and finite automata. | + | *[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]. |
| − | *Context-free grammars and push-down automata. | + | *[http://gateoverflow.in/tag/referential-integrity Integrity constraints], |
| − | *Regular and context-free languages, pumping lemma. | + | *[http://gateoverflow.in/tag/database-normalization normal forms.] |
| − | *Turing machines and undecidability. | + | *[http://gateoverflow.in/tag/indexing File organization], [http://gateoverflow.in/tag/b-tree indexing (e.g., B and B+ trees)]. |
| − | '''pumping lemma''' newly added. | + | *[http://gateoverflow.in/tag/transactions Transactions and concurrency control]. |
| − | '''Recursively enumerable sets''' removed but Turing machines are there.
| + | No change |
| | | | |
| − | ==Compiler Design== | + | ==[http://www.gatecse.in/computer-networks/ Computer Networks]== |
| − | *Lexical analysis, parsing, syntax-directed translation. | + | *[http://gateoverflow.in/tag/network-layering Concept of layering]. [http://gateoverflow.in/tag/lan-technologies LAN technologies (Ethernet)]. |
| − | *Runtime environments. | + | *[http://gateoverflow.in/tag/sliding-window Flow] and [http://gateoverflow.in/tag/error-detection error control] techniques, |
| − | *Intermediate code generation. | + | *[http://gateoverflow.in/tag/network-switching switching]. |
| | + | *[http://gateoverflow.in/tag/ip-packet IPv4]/IPv6, |
| | + | *[http://gateoverflow.in/tag/routing 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]. |
| | + | *[http://gateoverflow.in/tag/application-layer-protocols Application layer protocols (DNS, SMTP, POP, FTP, HTTP)]. |
| | + | *Basics of Wi-Fi. |
| | + | *[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 |
| | + | '''[http://gateoverflow.in/tag/token-ring Token Ring]''' removed |
| | + | '''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. |
| | | | |
| − | ==Operating System== | + | ==General Aptitude== |
| − | *Processes, threads, inter‐process communication, concurrency and synchronization. | + | *No change in [http://www.gatecse.in/numerical-ability/ Numerical Ability] as well as [http://www.gatecse.in/verbal-ability/ Verbal Ability]. |
| − | *Deadlock.
| |
| − | *CPU scheduling.
| |
| − | *Memory management and virtual memory.
| |
| − | *File systems.
| |
| | | | |
| − | ==Databases== | + | ==Removals== |
| − | *ER‐model. Relational model:
| + | Except LU decomposition, all portions of Web Technologies, IS & Software Engineering and Numerical Methods are removed. |
| − | *relational algebra, tuple calculus, SQL.
| |
| − | *Integrity constraints,
| |
| − | *normal forms.
| |
| − | *File organization, indexing (e.g., B and B+ trees).
| |
| − | *Transactions and concurrency control.
| |
| | | | |
| − | ==Computer Networks==
| + | '''Web technologies:''' HTML, XML, basic concepts of client-server computing. |
| − | *Concept of layering. LAN technologies (Ethernet).
| |
| − | *Flow and error control techniques,
| |
| − | *switching.
| |
| − | *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.
| |
| | | | |
| | + | '''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. |
| | | | |
| | + | {{Template:FBD}} |
| | [[Category:GATE]] | | [[Category:GATE]] |
GATECSE