Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
Line 59: | Line 59: | ||
*Algorithm design techniques: greedy, dynamic programming and divide‐and‐conquer. | *Algorithm design techniques: greedy, dynamic programming and divide‐and‐conquer. | ||
*Graph search, minimum spanning trees, shortest paths. | *Graph search, minimum spanning trees, shortest paths. | ||
+ | '''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. | ||
+ | |||
==Theory of Computation== | ==Theory of Computation== | ||
*Regular expressions and finite automata. | *Regular expressions and finite automata. | ||
*Context-free grammars and push-down automata. | *Context-free grammars and push-down automata. | ||
− | *Regular and | + | *Regular and context-free languages, pumping lemma. |
*Turing machines and undecidability. | *Turing machines and undecidability. | ||
+ | '''pumping lemma''' newly added. | ||
+ | '''Recursively enumerable sets''' removed but Turing machines are there. | ||
==Compiler Design== | ==Compiler Design== |
Boolean Algebra moved to Digital Logic. 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.
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 won't be there.
Functions, Parameter passing, Scope, Binding; Abstract data types removed. So, questions like pass by reference, static-dynamic scopes, etc won't 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 needn't be studied but reduction is there in Theory of Computation anyway.
pumping lemma newly added. Recursively enumerable sets removed but Turing machines are there.
Boolean Algebra moved to Digital Logic. 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.
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 won't be there.
Functions, Parameter passing, Scope, Binding; Abstract data types removed. So, questions like pass by reference, static-dynamic scopes, etc won't be there. Graphs added here.