<<<<<<< HEAD rgpv syllabus MCA Dual Degree Grading System 6th Semester Microsoft Word - VI MCA Dual Degree Syllabus


MCADD-601 Analysis Design of Algorithm



UNIT – I

Pre-requisites: Data structure & Discrete structures, models of computation, algorithm analysis, order architecture, time space complexities average and worst case analysis.

UNIT-II

Divide and conquer: Structure of divide-and-conquer algorithms: examples; Binary search, quick sort, Strassen Multiplication; Analysis of divide and conquer run time recurrence relations.

Graph searching and Traversal: Overview, Traversal methods (depth first and breadth first search)


UNIT-III

Greedy Method: Overview of the greedy paradigm examples of exact optimization solution (minimum cost spanning tree), Approximate solution (Knapsack problem), Single source shortest paths.

Branch and bound: LC searching Bounding, FIFO branch and bound, LC branch and bound application: 0/1 Knapsack problem, Traveling Salesman Problem, searching & sorting algorithms.


UNIT-IV


Dynamic programming: Overview, difference between dynamic programming and divide and conquer, Applications: Shortest path in graph, Matrix multiplication, Traveling salesman Problem, longest Common sequence.

Back tracking: Overview, 8-queen problem, and Knapsack problem


UNIT-V

Computational Complexity: Complexity measures, Polynomial Vs non-polynomial time complexity; NP-hard and NP-complete classes, examples.

Combinational algorithms, string processing algorithm, Algebric algorithms , set algorithms

BOOKS

  1. Ullman "Analysis and Design of Algorithm" TMH

  2. Goodman “Introduction to the Design & Analysis of Algorithms, TMH-2002.

  3. Sara Basse, A. V. Gelder, “ Computer Algorithms,” Addison Wesley

  4. T. H. Cormen, Leiserson , Rivest and Stein, “Introduction of Computer algorithm,” PHI

  5. E. Horowitz, S. Sahni, and S. Rajsekaran, “Fundamentals of Computer Algorithms,” Galgotia Publication



UNIT-I

MCADD-602 Advanced Computer Networks

Introduction: Computer Network, Layered Network Architecture-Review of ISO-OSI Model., Transmission Fundamentals-, Communication Media-Conductive Metal (Wired Cable), Optical Fiber links, Wireless Communication-Radio links, Setellite Links, Communication Services & Devices, Telephone System., Integrated Service Digital Network (ISDN)., Cellular Phone., ATM, Modulation & Demodulation-, Digital to Analog Conversion-Frequency Modulation (FM), Amplitude, Modulation (AM), Phase Modulation (PM)., Analog to Digital Conversion-Pulse Amplitude Modulation(PAM), Pulse Code Modulation (PCM), Differential Pulse Code Modulation, (DPCM)., Modem & Modem Types., Multiplexing-, Frequency Division Multiplexing (FDM)., Time Division Multiplexing (TDM), Statistical Time Division Multiplexing (STDM)., Contention Protocol-, Stop-Go-Access Protocol, Aloha Protocol-Pure aloha & Slotted aloha, Carrier sense multiple access with collision detection (CSMA/CD)

UNIT-II

Data Security and Integrity: Parity Checking Code, Cyclic redundancy checks (CRC), Hemming Code, Protocol Concepts –, Basic flow control, Sliding window protocal-Go-Back-N protocol and selective repeat protocol, Protocol correctness- Finite state machine


UNIT-III

Local Area Network: Ethernet : 802.3 IEEE standard, Token Ring : 802.5 IEEE standard, Token Bus : 802.4 IEEE standard, FDDI Protocol, DQDB Protocol, Inter Networking, Layer 1 connections- Repeater, Hubs, Layer 2 connections- Bridges, Switches, Layer 3 connections- Routers, Gateways.


UNIT-IV

Wide Area Network: Introduction, Network routing, Routing Tables, Types of routing, Dijkstra’s Algorithm, Bellman-Ford Algorithm, Link state routing, Open shortest path first, Flooding, Broadcasting, Multicasting, Congestion & Dead Lock, Internet Protocols, Overview of TCP/IP, Transport protocols, Elements of Transport Protocol, Transmission control protocol (TCP), User data-gram protocol (UDP).


UNIT-V

Network Security, Virtual Terminal Protocol, Overview of DNS, SNMP, email, WWW, Multimedia. BOOKS

  1. A.S.Tanenbaum, “Computer Network”, 4th addition,PHI

  2. Forouzan “Data Communication and Networking 3ed”, TMH

  3. J.F.Hayes, “Moduling and Analysis of Computer Communication Networks”, Plenum Press

  4. D.E.Comer, “Internetworking with TCP/IP”, Volume Ist & IInd, PHI

  5. Willium Stalling, “Data & Computer communications”,Maxwell Macmillan International Ed.

  6. D.Bertsekas and R.Gallager,”Data Networks”, 2nd Ed. ,PHI.

  7. G.E. Keiser ,”Local Area Networks “, McGraw Hill, International Ed.

MCADD-603 Advanced DBMS


UNIT-I

Objected Oriented and Object Relational Databases

Modeling Complex Data Semantics, Specialization, Generalization, Aggregation and Association, Objects, Object Identity and its implementation, Clustering, Equality and Object Reference, Architecture of Object Oriented and Object Relational databases, Persistent Programming Languages, Cache Coherence. Case Studies: Gemstone, O2, Object Store, SQL3, Oracle xxi, DB2.


UNIT-II

Deductive Databases

Data log and Recursion, Evaluation of Data log program, Recursive queries with negation.

Parallel and Distributed Databases

Parallel architectures, shared nothing/shared disk/shared memory based architectures, Data partitioning, Intra-operator parallelism, pipelining. Distributed Data Storage – Fragmentation & Replication, Location and Fragment Transparency Distributed Query Processing and Optimization, Distributed Transaction Modeling and concurrency Control, Distributed Deadlock, Commit Protocols, Design of Parallel Databases, and Parallel Query Evaluation.


UNIT-III

Advanced Transaction Processing

Advanced transaction models: Savepoints, Nested and Multilevel Transactions, Compensating Transactions and Saga, Long Duration Transactions, Weak Levels of Consistency, Transaction Work Flows, Transaction Processing Monitors, Shared disk systems.


UNIT-IV

Active Database and Real Time Databases

Triggers in SQL, Event Constraint and Action: ECA Rules, Query Processing and Concurrency Control, Recursive query processing, Compensation and Databases Recovery, multi-level recovery.


UNIT-V

Image and Multimedia Databases

Modeling and Storage of Image and Multimedia Data, Data Structures – R-tree, k-d tree, Quad trees, Content Based Retrieval: Color Histograms, Textures, etc., Image Features, Spatial and Topological Relationships, Multimedia Data Formats, Video Data Model, Audio & Handwritten Data, Geographic Information Systems (GIS).

WEB Database

Accessing Databases through WEB, WEB Servers, XML Databases, Commercial Systems – Oracle xxi, DB2.


BOOKS

  1. Elmarsi, “Fundamentals of Database Systems”, 4 th Edition, Pearson Education

  2. R. Ramakrishnan, “Database Management Systems”, 1998, McGraw Hill International Editions

  3. Elmagarmid.A.K. “Database transaction models for advanced applications”, Morgan Kaufman.

  4. Transaction Processing, Concepts and Techniques, J. Gray and A. Reuter, Morgan Kauffman..

  5. S. Abiteboul, R. hull and V. Vianu, “Foundations of Databases”, 1995, Addison – Wesley Publishing Co., Reading Massachusetts.

  6. W. Kim, “Modern Database Systems”, 1995, ACM Press, Addison – Wesley.

  7. D. Maier, “The Theory of Relational Databases”, 1993, Computer Science Press, Rockville, Maryland


MCADD-604 Theory of Computation


UNIT-I

Review of Mathematical Priliminaries : Set, Relations and functions, Graphs and trees, string, alphabets and languages. Principle of induction, predicates and propositional calculus.

Theory of Automation : Definition, description, DFA,NFA, Transition systems,2DFA, equivalence of DFA & NDFA, Regular expressions, regular grammer, FSM with output (mealy and moore models), Minimisation of finite automata.


UNIT-II

Formal Languages : Definition & description, Pharse structured grammars & their classification, Chomskey classification of languages, closure properties of families of language, regular grammar, regular set & their closure properties, finite automata, equivalence of FA and regular expression, equivalence of two way finite automata, equivalence of regular expressions.


UNIT -III

Context-Free grammar & PDA : Properties unrestricted grammar & their equivalence, derivation tree simplifying CFG, unambiguifying CFG, 7-productions, normal form for CFG, Pushdown automata, 2 way PDA, relation of PDA with CFG, Determinism & Non determinism in PDA & related theorems, parsing and pushdown automata.


UNIT-IV

Turing Machine : Model, design, representation of TM, language accepted by TM, universal turing machine, determine & non-determinism in TM, TM as acceptor/generator/algorithms, multidimentional, multitracks, multitape, Two way infinite tape, multihead, Halting problems of TM.


UNIT-V

Computability : Concepts, Introduction to complexity theory, Introduction to undecidaibility, recursively enumerable sets, primitive recursive functions, recursive set, partial recursive sets, concepts of linear bounded Automata, context sensitive grammars & their equivalence.


BOOKS

  1. Hopcroft & Ullman “Introduction to Automata theory, languages & Computation” , Narosha Publishing house.

  2. Lewish Papadimutrau “Theory of Computation” , Prentice Hall of India, New Delhi.

  3. Peter linz, “An Introduction to formal language and automata”, Third edition, Narosa publication.

  4. Marvin L. Minskay “Computation : Finite & Infinite Machines”, PHI.

  5. Mishra & Chander Shekhar “Theory of Computer Science (Automate, Language & Computations), PHI.


MCADD-605 Artificial Intelligence


UNIT-I


General Issues and Overview of AI


The AI problems, what is an AI technique, Characteristics of AI applications. Introduction to LISP programming: Syntax and numeric functions, Basic list manipulation functions, predicates and conditionals, input output and local variables, iteraction and recursion, property lists and arrays.

UNIT-II


Problem Solving, Search and Control Strategies


General problem solving, production systems, control strategies forward and backward chaining, exhausive searches depth first breadth first search.

Heuristic Search Techniques


Hill climbing, branch and bound technique, best first search & A* algorithm, AND / OR graphs, problem reduction & AO* algorithm, constraint satisfaction problems.


UNIT-III

Knowledge Representations

First order predicate calculus, skolemization, resolution principle & unification, interface mechanisms, horn's clauses, semantic networks, frame systems and value inheritance, scripts, conceptual dependency.

UNIT-IV

Natural Language processing

Parsing techniques, context free grammer, recursive transitions nets (RNT), augmented transition nets (ATN), case and logic grammers, symantic analysis.


Game playing

Minimax search procedure, alpha-beta cutoffs, additional refinments.

Planning

Overview an example domain the block word, component of planning systems, goal stack planning, non linear planning.

UNIT-V

Probabilistic Reasoning and Uncertainty


Probability theory, bayes theorem and bayesian networks, certainty factor.


Expert Systems


Introduction to expert system and application of expert systems, various expert system shells, vidwan frame work, knowledge acquisition, case studies, MYCIN.


Learning


Rote learning, learning by induction, explanation based learning.


BOOKS


  1. Elaine Rich and Kevin Knight “Artifical Intelligence” - Tata McGraw Hill.

  2. “Artifical Intelligence” 4 ed. Pearson.

  3. Dan W. Patterson “Introduction to Artifical Intelligence and Expert Systems”, Prentice India.

  4. Nils J. Nilson “Principles of Artifical Intelligence”, Narosa Publishing House.

  5. Clocksin & C.S.Melish “Programming in PROLOG”, Narosa Publishing House.

  6. M.Sasikumar,S.Ramani etc. “Rule based Expert System”, Narosa Publishing House.

======= rgpv syllabus MCA Dual Degree Grading System 6th Semester Microsoft Word - VI MCA Dual Degree Syllabus


MCADD-601 Analysis Design of Algorithm



UNIT – I

Pre-requisites: Data structure & Discrete structures, models of computation, algorithm analysis, order architecture, time space complexities average and worst case analysis.

UNIT-II

Divide and conquer: Structure of divide-and-conquer algorithms: examples; Binary search, quick sort, Strassen Multiplication; Analysis of divide and conquer run time recurrence relations.

Graph searching and Traversal: Overview, Traversal methods (depth first and breadth first search)


UNIT-III

Greedy Method: Overview of the greedy paradigm examples of exact optimization solution (minimum cost spanning tree), Approximate solution (Knapsack problem), Single source shortest paths.

Branch and bound: LC searching Bounding, FIFO branch and bound, LC branch and bound application: 0/1 Knapsack problem, Traveling Salesman Problem, searching & sorting algorithms.


UNIT-IV


Dynamic programming: Overview, difference between dynamic programming and divide and conquer, Applications: Shortest path in graph, Matrix multiplication, Traveling salesman Problem, longest Common sequence.

Back tracking: Overview, 8-queen problem, and Knapsack problem


UNIT-V

Computational Complexity: Complexity measures, Polynomial Vs non-polynomial time complexity; NP-hard and NP-complete classes, examples.

Combinational algorithms, string processing algorithm, Algebric algorithms , set algorithms

BOOKS

  1. Ullman "Analysis and Design of Algorithm" TMH

  2. Goodman “Introduction to the Design & Analysis of Algorithms, TMH-2002.

  3. Sara Basse, A. V. Gelder, “ Computer Algorithms,” Addison Wesley

  4. T. H. Cormen, Leiserson , Rivest and Stein, “Introduction of Computer algorithm,” PHI

  5. E. Horowitz, S. Sahni, and S. Rajsekaran, “Fundamentals of Computer Algorithms,” Galgotia Publication



UNIT-I

MCADD-602 Advanced Computer Networks

Introduction: Computer Network, Layered Network Architecture-Review of ISO-OSI Model., Transmission Fundamentals-, Communication Media-Conductive Metal (Wired Cable), Optical Fiber links, Wireless Communication-Radio links, Setellite Links, Communication Services & Devices, Telephone System., Integrated Service Digital Network (ISDN)., Cellular Phone., ATM, Modulation & Demodulation-, Digital to Analog Conversion-Frequency Modulation (FM), Amplitude, Modulation (AM), Phase Modulation (PM)., Analog to Digital Conversion-Pulse Amplitude Modulation(PAM), Pulse Code Modulation (PCM), Differential Pulse Code Modulation, (DPCM)., Modem & Modem Types., Multiplexing-, Frequency Division Multiplexing (FDM)., Time Division Multiplexing (TDM), Statistical Time Division Multiplexing (STDM)., Contention Protocol-, Stop-Go-Access Protocol, Aloha Protocol-Pure aloha & Slotted aloha, Carrier sense multiple access with collision detection (CSMA/CD)

UNIT-II

Data Security and Integrity: Parity Checking Code, Cyclic redundancy checks (CRC), Hemming Code, Protocol Concepts –, Basic flow control, Sliding window protocal-Go-Back-N protocol and selective repeat protocol, Protocol correctness- Finite state machine


UNIT-III

Local Area Network: Ethernet : 802.3 IEEE standard, Token Ring : 802.5 IEEE standard, Token Bus : 802.4 IEEE standard, FDDI Protocol, DQDB Protocol, Inter Networking, Layer 1 connections- Repeater, Hubs, Layer 2 connections- Bridges, Switches, Layer 3 connections- Routers, Gateways.


UNIT-IV

Wide Area Network: Introduction, Network routing, Routing Tables, Types of routing, Dijkstra’s Algorithm, Bellman-Ford Algorithm, Link state routing, Open shortest path first, Flooding, Broadcasting, Multicasting, Congestion & Dead Lock, Internet Protocols, Overview of TCP/IP, Transport protocols, Elements of Transport Protocol, Transmission control protocol (TCP), User data-gram protocol (UDP).


UNIT-V

Network Security, Virtual Terminal Protocol, Overview of DNS, SNMP, email, WWW, Multimedia. BOOKS

  1. A.S.Tanenbaum, “Computer Network”, 4th addition,PHI

  2. Forouzan “Data Communication and Networking 3ed”, TMH

  3. J.F.Hayes, “Moduling and Analysis of Computer Communication Networks”, Plenum Press

  4. D.E.Comer, “Internetworking with TCP/IP”, Volume Ist & IInd, PHI

  5. Willium Stalling, “Data & Computer communications”,Maxwell Macmillan International Ed.

  6. D.Bertsekas and R.Gallager,”Data Networks”, 2nd Ed. ,PHI.

  7. G.E. Keiser ,”Local Area Networks “, McGraw Hill, International Ed.

MCADD-603 Advanced DBMS


UNIT-I

Objected Oriented and Object Relational Databases

Modeling Complex Data Semantics, Specialization, Generalization, Aggregation and Association, Objects, Object Identity and its implementation, Clustering, Equality and Object Reference, Architecture of Object Oriented and Object Relational databases, Persistent Programming Languages, Cache Coherence. Case Studies: Gemstone, O2, Object Store, SQL3, Oracle xxi, DB2.


UNIT-II

Deductive Databases

Data log and Recursion, Evaluation of Data log program, Recursive queries with negation.

Parallel and Distributed Databases

Parallel architectures, shared nothing/shared disk/shared memory based architectures, Data partitioning, Intra-operator parallelism, pipelining. Distributed Data Storage – Fragmentation & Replication, Location and Fragment Transparency Distributed Query Processing and Optimization, Distributed Transaction Modeling and concurrency Control, Distributed Deadlock, Commit Protocols, Design of Parallel Databases, and Parallel Query Evaluation.


UNIT-III

Advanced Transaction Processing

Advanced transaction models: Savepoints, Nested and Multilevel Transactions, Compensating Transactions and Saga, Long Duration Transactions, Weak Levels of Consistency, Transaction Work Flows, Transaction Processing Monitors, Shared disk systems.


UNIT-IV

Active Database and Real Time Databases

Triggers in SQL, Event Constraint and Action: ECA Rules, Query Processing and Concurrency Control, Recursive query processing, Compensation and Databases Recovery, multi-level recovery.


UNIT-V

Image and Multimedia Databases

Modeling and Storage of Image and Multimedia Data, Data Structures – R-tree, k-d tree, Quad trees, Content Based Retrieval: Color Histograms, Textures, etc., Image Features, Spatial and Topological Relationships, Multimedia Data Formats, Video Data Model, Audio & Handwritten Data, Geographic Information Systems (GIS).

WEB Database

Accessing Databases through WEB, WEB Servers, XML Databases, Commercial Systems – Oracle xxi, DB2.


BOOKS

  1. Elmarsi, “Fundamentals of Database Systems”, 4 th Edition, Pearson Education

  2. R. Ramakrishnan, “Database Management Systems”, 1998, McGraw Hill International Editions

  3. Elmagarmid.A.K. “Database transaction models for advanced applications”, Morgan Kaufman.

  4. Transaction Processing, Concepts and Techniques, J. Gray and A. Reuter, Morgan Kauffman..

  5. S. Abiteboul, R. hull and V. Vianu, “Foundations of Databases”, 1995, Addison – Wesley Publishing Co., Reading Massachusetts.

  6. W. Kim, “Modern Database Systems”, 1995, ACM Press, Addison – Wesley.

  7. D. Maier, “The Theory of Relational Databases”, 1993, Computer Science Press, Rockville, Maryland


MCADD-604 Theory of Computation


UNIT-I

Review of Mathematical Priliminaries : Set, Relations and functions, Graphs and trees, string, alphabets and languages. Principle of induction, predicates and propositional calculus.

Theory of Automation : Definition, description, DFA,NFA, Transition systems,2DFA, equivalence of DFA & NDFA, Regular expressions, regular grammer, FSM with output (mealy and moore models), Minimisation of finite automata.


UNIT-II

Formal Languages : Definition & description, Pharse structured grammars & their classification, Chomskey classification of languages, closure properties of families of language, regular grammar, regular set & their closure properties, finite automata, equivalence of FA and regular expression, equivalence of two way finite automata, equivalence of regular expressions.


UNIT -III

Context-Free grammar & PDA : Properties unrestricted grammar & their equivalence, derivation tree simplifying CFG, unambiguifying CFG, 7-productions, normal form for CFG, Pushdown automata, 2 way PDA, relation of PDA with CFG, Determinism & Non determinism in PDA & related theorems, parsing and pushdown automata.


UNIT-IV

Turing Machine : Model, design, representation of TM, language accepted by TM, universal turing machine, determine & non-determinism in TM, TM as acceptor/generator/algorithms, multidimentional, multitracks, multitape, Two way infinite tape, multihead, Halting problems of TM.


UNIT-V

Computability : Concepts, Introduction to complexity theory, Introduction to undecidaibility, recursively enumerable sets, primitive recursive functions, recursive set, partial recursive sets, concepts of linear bounded Automata, context sensitive grammars & their equivalence.


BOOKS

  1. Hopcroft & Ullman “Introduction to Automata theory, languages & Computation” , Narosha Publishing house.

  2. Lewish Papadimutrau “Theory of Computation” , Prentice Hall of India, New Delhi.

  3. Peter linz, “An Introduction to formal language and automata”, Third edition, Narosa publication.

  4. Marvin L. Minskay “Computation : Finite & Infinite Machines”, PHI.

  5. Mishra & Chander Shekhar “Theory of Computer Science (Automate, Language & Computations), PHI.


MCADD-605 Artificial Intelligence


UNIT-I


General Issues and Overview of AI


The AI problems, what is an AI technique, Characteristics of AI applications. Introduction to LISP programming: Syntax and numeric functions, Basic list manipulation functions, predicates and conditionals, input output and local variables, iteraction and recursion, property lists and arrays.

UNIT-II


Problem Solving, Search and Control Strategies


General problem solving, production systems, control strategies forward and backward chaining, exhausive searches depth first breadth first search.

Heuristic Search Techniques


Hill climbing, branch and bound technique, best first search & A* algorithm, AND / OR graphs, problem reduction & AO* algorithm, constraint satisfaction problems.


UNIT-III

Knowledge Representations

First order predicate calculus, skolemization, resolution principle & unification, interface mechanisms, horn's clauses, semantic networks, frame systems and value inheritance, scripts, conceptual dependency.

UNIT-IV

Natural Language processing

Parsing techniques, context free grammer, recursive transitions nets (RNT), augmented transition nets (ATN), case and logic grammers, symantic analysis.


Game playing

Minimax search procedure, alpha-beta cutoffs, additional refinments.

Planning

Overview an example domain the block word, component of planning systems, goal stack planning, non linear planning.

UNIT-V

Probabilistic Reasoning and Uncertainty


Probability theory, bayes theorem and bayesian networks, certainty factor.


Expert Systems


Introduction to expert system and application of expert systems, various expert system shells, vidwan frame work, knowledge acquisition, case studies, MYCIN.


Learning


Rote learning, learning by induction, explanation based learning.


BOOKS


  1. Elaine Rich and Kevin Knight “Artifical Intelligence” - Tata McGraw Hill.

  2. “Artifical Intelligence” 4 ed. Pearson.

  3. Dan W. Patterson “Introduction to Artifical Intelligence and Expert Systems”, Prentice India.

  4. Nils J. Nilson “Principles of Artifical Intelligence”, Narosa Publishing House.

  5. Clocksin & C.S.Melish “Programming in PROLOG”, Narosa Publishing House.

  6. M.Sasikumar,S.Ramani etc. “Rule based Expert System”, Narosa Publishing House.

>>>>>>> html