Paper III - Elective/Optional
Elective - I
Theory of Computation: Formal language, Need for formal computational models, Non-computational problems, diagonal argument and Russel's paradox.
Deterministic Finite Automaton (DFA), Non-deterministic Finite Automaton (NFA), Regular languages and regular sets, Equivalence of DFA and NFA. Minimizing the number of states of a DFA. Non-regular languages and Pumping lemma.
Pushdown Automaton (PDA), Deterministic Pushdown Automaton (DPDA), Non-equivalence of PDA and DPDA.
Context free Grammars: Greibach Normal Form (GNF) and Chomsky Normal Form (CNF), Ambiguity, Parse Tree Representation of Derivations. Equivalence of PDA's and CFG's. Parsing techniques for parsing of general CFG's - Early's, Cook-Kassami-Younger (CKY), and Tomita's parsing.
Linear Bounded Automata (LBA): Power of LBA. Closure properties.
Turing Machine (TM): One tape, multitape. The notions of time and space complexity in terms of TM. Construction of TM for simple problems. Computational complexity.
Chomsky Hierarchy of Languages: Recursive and recursively-enumerable languages.
Elective - II
Model for Information Channel: Discrete Memoryless Channel, Binary Symmetric Channel (BSC), Burst Channel, Bit-error rates. Probability, Entropy and Shannon's measure of information. Mutual information. Channel capacity theorem. Rate and optimality of information transmission.
Variable Length Codes: Prefix codes. Huffman Codes, Lempel-Ziev (LZ) codes. Optimality of these codes. Information content of these codes.
Error Correcting and Detecting Codes: Finite fields, Hamming distance, Bounds of codes, Linear (Parity Check) codes, Parity check matrix, Generator matrix, Decoding of linear codes, Hamming codes.
Image Processing: Image Registration, Spatial Fourier Transforms, Discrete Spatial (2-dimensional) Fourier transforms, Restoration, Lossy Compression of images (pictures).
Data Compression Techniques: Representation and compression of text, sound, picture, and video files (based on the JPEG and MPEG standards).
Elective - III
Linear Programming Problem: Linear Programming Problem (LPP) in the standard form, LPP in Canonical form. Conversion of LPP in Standard form to LPP in Canonical form. Simplex-Prevention of cyclic computations in Simplex and Tableau, Big-M method, dual simplex and revised simplex. Complexity of simplex algorithm(s). Exponential behaviour of simplex.
Ellipsoid method and Karmakar's method for solving LPPs. Solving simple LPPs through these methods. Comparison of complexity of these methods.
Assignment and Transportation Problems: Simple algorithms like Hungarian method, etc.
Shortest Path Problems: Dijkstra's and Moore's method. Complexity.
Network Flow Problem: Formulation. Max-Flow Min-Cut theorem. Ford and Fulkerson’s algorithm. Exponential behaviour of Ford and Fulkerson's algorithm. Malhotra-Pramodkumar-Maheshwari (MPM) Polynomial algorithm for solving Network flow problem. Bipartite Graphs and Matchings; Solving matching problems using Network flow problems.
Matroids: Definition. Graphic and Cographic matroids. Matroid intersection problem.
Non-linear Programming: Kuhn-Tucker conditions. Convex functions and Convex regions. Convex programming problems. Algorithms for solving convex programming problems - Rate of convergence of iterative methods for solving these problems.
Elective - IV
Neural Networks: Perception model, Linear separability and XOR problem. Two and three layered neural nets, Backpropagation - Convergence. Hopfield nets, Neural net learning, Applications.
Fuzzy Systems: Definition of a Fuzzy set, Fuzzy relations, Fuzzy functions, Fuzzy measures, Fuzzy reasoning, Applications of Fuzzy systems.
Elective - V
Unix: Operating system, Structure of Unix Operating System, Unix Commands, Interfacing with Unix, Editors and Compilers for Unix, LEX and YACC, File system, System calls. Filters, Shell programming.
Windows: Windows environment, Unicode, Documents and Views, Drawing in a window, Message handling, Scrolling and Splitting views, Docking toolbars and Status bars, Common dialogs and Controls, MDI, Multithreading, OLE, Active X controls, ATL, Database access, Network programming.
Elective - I
Theory of Computation: Formal language, Need for formal computational models, Non-computational problems, diagonal argument and Russel's paradox.
Deterministic Finite Automaton (DFA), Non-deterministic Finite Automaton (NFA), Regular languages and regular sets, Equivalence of DFA and NFA. Minimizing the number of states of a DFA. Non-regular languages and Pumping lemma.
Pushdown Automaton (PDA), Deterministic Pushdown Automaton (DPDA), Non-equivalence of PDA and DPDA.
Context free Grammars: Greibach Normal Form (GNF) and Chomsky Normal Form (CNF), Ambiguity, Parse Tree Representation of Derivations. Equivalence of PDA's and CFG's. Parsing techniques for parsing of general CFG's - Early's, Cook-Kassami-Younger (CKY), and Tomita's parsing.
Linear Bounded Automata (LBA): Power of LBA. Closure properties.
Turing Machine (TM): One tape, multitape. The notions of time and space complexity in terms of TM. Construction of TM for simple problems. Computational complexity.
Chomsky Hierarchy of Languages: Recursive and recursively-enumerable languages.
Elective - II
Model for Information Channel: Discrete Memoryless Channel, Binary Symmetric Channel (BSC), Burst Channel, Bit-error rates. Probability, Entropy and Shannon's measure of information. Mutual information. Channel capacity theorem. Rate and optimality of information transmission.
Variable Length Codes: Prefix codes. Huffman Codes, Lempel-Ziev (LZ) codes. Optimality of these codes. Information content of these codes.
Error Correcting and Detecting Codes: Finite fields, Hamming distance, Bounds of codes, Linear (Parity Check) codes, Parity check matrix, Generator matrix, Decoding of linear codes, Hamming codes.
Image Processing: Image Registration, Spatial Fourier Transforms, Discrete Spatial (2-dimensional) Fourier transforms, Restoration, Lossy Compression of images (pictures).
Data Compression Techniques: Representation and compression of text, sound, picture, and video files (based on the JPEG and MPEG standards).
Elective - III
Linear Programming Problem: Linear Programming Problem (LPP) in the standard form, LPP in Canonical form. Conversion of LPP in Standard form to LPP in Canonical form. Simplex-Prevention of cyclic computations in Simplex and Tableau, Big-M method, dual simplex and revised simplex. Complexity of simplex algorithm(s). Exponential behaviour of simplex.
Ellipsoid method and Karmakar's method for solving LPPs. Solving simple LPPs through these methods. Comparison of complexity of these methods.
Assignment and Transportation Problems: Simple algorithms like Hungarian method, etc.
Shortest Path Problems: Dijkstra's and Moore's method. Complexity.
Network Flow Problem: Formulation. Max-Flow Min-Cut theorem. Ford and Fulkerson’s algorithm. Exponential behaviour of Ford and Fulkerson's algorithm. Malhotra-Pramodkumar-Maheshwari (MPM) Polynomial algorithm for solving Network flow problem. Bipartite Graphs and Matchings; Solving matching problems using Network flow problems.
Matroids: Definition. Graphic and Cographic matroids. Matroid intersection problem.
Non-linear Programming: Kuhn-Tucker conditions. Convex functions and Convex regions. Convex programming problems. Algorithms for solving convex programming problems - Rate of convergence of iterative methods for solving these problems.
Elective - IV
Neural Networks: Perception model, Linear separability and XOR problem. Two and three layered neural nets, Backpropagation - Convergence. Hopfield nets, Neural net learning, Applications.
Fuzzy Systems: Definition of a Fuzzy set, Fuzzy relations, Fuzzy functions, Fuzzy measures, Fuzzy reasoning, Applications of Fuzzy systems.
Elective - V
Unix: Operating system, Structure of Unix Operating System, Unix Commands, Interfacing with Unix, Editors and Compilers for Unix, LEX and YACC, File system, System calls. Filters, Shell programming.
Windows: Windows environment, Unicode, Documents and Views, Drawing in a window, Message handling, Scrolling and Splitting views, Docking toolbars and Status bars, Common dialogs and Controls, MDI, Multithreading, OLE, Active X controls, ATL, Database access, Network programming.