DESIGN AND ANALYSIS OF ALGORITHM

Course Code- CS402

MODULE-I
INTRODUCTION & ANALYSIS:
Analyzing Algorithms, Recurrence Equations, Growth Function: Asymptotic Notation, Standard
Notation & Common Functions, Recurrence Relation, Different Methods of Solution of Recurrence
Equations with Examples.
MODULE-II
DIVIDE AND CONQUER & BACKTRACKING PARADIGM:
Introduction to Divide and Conquer Paradigm, Quick and Merge Sorting Techniques, Linear Time
Selection Algorithm, The Basic Divide and Conquer Algorithm for Matrix Multiplication,
Backtracking & Recursive Backtracking, Applications of Backtracking Paradigm, Heaps.
MODULE-III
GREEDY PARADIGM & DYNAMIC PROGRAMMING:
Greedy Paradigm: The Basic Greedy Strategy & Computing Minimum Spanning Trees, Algorithms
of Kruskal and Prim, Union to Find Algorithm & Their Applications, Disjoint Set, The Relationship
in Dijkstra’s and Prim’s Algorithms, Use of Greedy Strategy in Algorithms for the Knapsack
Problem and Huffman Trees. The Basic Dynamic Programming Paradigm, Dynamic Programming
Solution to the Optimal Matrix Chain Multiplication and the Longest Common Subsequence
Problems.
MODULE-IV
GRAPHS ALGORITHMS & STARING MATCHING ALGORITHMS:
Representational Issues in Graphs, Depth First Search & Breath First Search on Graphs,
Computation of Bi-connected Components and Strongly Connected Components Using DFS,
Topological Sorting & Applications, Shortest Path Algorithms on Graphs: Bellman-Ford Algorithm,
Dijkstra’s Algorithm & Analysis of Dijkstra’s Algorithm Using Heaps, Floyd-Warshall’s all Pairs
Shortest Path Algorithm and its Refinement for Computing the Transitive Closure of a Graph. The
General String Problem as a Finite Automata, Kunth Morris and Pratt Algorithms.
MODULE-V
NP-COMPLETE PROBLEMS:
Solvable Problems, Types of Problems, The Notion of a Non-Deterministic Algorithm and its Basic
Relationship to Backtracking, Polynomial Time Non-Deterministic Algorithms for Problems Like
Satisfiability, Clique Problem, Hamiltonian Path Problems etc. The Definition of NP-Hardness and
NP-Completeness, The Statement of Cook’s Theorem and a Discussion of its Implication, The
Notion of Polynomial Transformation, Vertex Cover, Subset Sum and Hamiltonian Cycle Problems
are NP-Complete, Other Models for Computations.
Text Books:
1. Introduction to Algorithms (Second Edition); Cormen, Leserson, Rivert; PHI.
2. Fundamentals of Algorithms, Sahni& Horowitz; Galgotia.
Reference Books:
1. The Design & Analysis of Computer Algorithms, Hopcroft-Aho-Ullman, AWL.
2. Handbook of Algorithms & Data Structures, G.H. Gonnet, AWL.
3. Introduction to Design & Analysis of Algorithms, Levitin, PE-LPE.

Course Code- CS403
(3-CREDIT) (L-T-P/3-1-0)

Module I: Fundamentals & Finite Automata:
Alphabet, Strings, Language, Operations, Mathematical proving techniques, Finite state machine,
definitions, finite automaton model, acceptance of strings, and languages, Deterministic Finite
Automaton (DFA) and Non deterministic Finite Automaton (NFA), transition diagrams and
Language recognizers. Equivalence of DFA and NFA, NFA to DFA conversion, NFA with ɛ -
transitions - Significance, acceptance of languages. Equivalence between NFA with and without ɛ -
transitions, minimization of FSM, Finite Automata with output- Moore and Mealy machines and
conversion of Mealy to Moore and vice-versa.
Module II: Regular Expression and Languages:
Regular sets, regular expressions, identity rules, Constructing finite Automata for a given regular
expressions, Conversion of Finite Automata to Regular expressions. Regular grammars-right linear
and left linear grammars, conversion of right linear grammar to left linear and vice-versa,
equivalence between regular grammar, regular expression and FA, Pumping lemma of regular sets,
closure properties of regular sets.
Module III: Context Free Grammars and Push Down Automata:
Context free grammar, derivation trees, sentential forms. Right most and leftmost derivation of
strings. Ambiguity in context free grammars. Reduction of Context Free Grammars. Chomsky
normal form(CNF), Greiback normal form(GNF), Pumping Lemma for Context Free Languages.
Simplification of CFL.
Push down automata(PDA) definition, model, acceptance of CFL, Acceptance by final state and
acceptance by empty state and its equivalence. Equivalence of CFG and PDA, interconversion.
Introduction to DCFL and DPDA. DPDA Vs NPDA.
Module IV: Turing Machine:
Turing Machine definition, representation of Turing Machines model, Variants of TM, design of TM,
linear bounded automata,
Module V: Computational Complexity & Decidability, Recursively Enumerable Languages:

Complexity : Growth rate of a function, class P and NP, polynomial time reduction and NP-
Completeness, NP-Complete problems(SAT, CSAT,Hamiltonian circuit, travelling salesman, vertex

cover). Decidability: decidability, decidable language, undecidable language, halting problem of
Turing Machine.Computability: primitive recursive function and recursive function.
TEXT BOOKS:
1. Theory of Computer Science (Automata Language and Computation) K.L.P. Mishra and N.
Chandrasekran, PHI.
2. Introduction to Automata Theory, Language and Computation, John E, Hopcropt and Jeffery
D. Ullman, Narosa Publishing House.
REFERENCE BOOKS:
1. Theory of Automata and Formal Language, R.B. Patel & P. Nath, Umesh Publication.
2. An Introduction and Finite Automata Theory, Adesh K. Pandey, TMH.
3. Theory of Computation AM Natrajan, Tamilarasi, Bilasubramani, New Age International
Publishers, Chhattisgarh Swami Vivekan.
4. An introduction to Formal Languages and Automata by Peter Linz, Narosa Publ

DISCRETE MATHEMATICS
Course Code- BSC401
(3-CREDIT) (L-T-P/3-1-0)

MODULE-I
Mathematical Logic:
Introduction, Statements and Notation, Connectives, Normal Forms, Theory of Inference for the
Statement Calculus, The Predicate Calculus, Inference Theory of the Predicate Calculus.

MODULE-II
Set Theory:
Introduction, Basic Concepts of Set Theory, Representation of Discrete Structures, Relations and
Ordering, Functions.
Algebraic Structures:
Introduction, Algebraic Systems, Semi Groups and Monoids, Groups, Lattices as Partially Ordered
Sets, Boolean Algebra.

MODULE-III
Elementary Combinations:
Basic of Counting, Combinations and Permutations, Enumeration of Combinations and
Permutations, Enumerating Combinations and Permutations with Repetitions, Enumerating
Permutations with Constrained Repetitions, Binomial Coefficients, The Binomial and Multi-Nominal
Theorems, The Principle of Inclusion-Exclusion.

MODULE-IV
Recurrence Relations:
Generating Functions of Sequences, Calculating Coefficients of Generating Functions, Recurrence
Relations, Solving Recurrence Relations by Substitution and Generating Functions, The Method of
Characteristic Roots, Solutions of Inhomogeneous Recurrence Relations.

MODULE-V
Graphs and Trees:
Basic Concepts, Isomorphisms and Subgraphs, Trees and Their Properties, Spanning Trees, Directed
Trees, Binary Trees, Planar Graphs, Euler’s Formula, Multigraphs and Euler Circuits, Hamiltonian
Graphs, Chromatic Numbers, The Four-Color Problem.
TEXT BOOKS:
1. Discrete Mathematical Structures with Applications to Computer Science, J.P. Tremblay, R.
Manohar, McGraw Hill Education (India) Private Limited (Units-I, II).
2. Discrete Mathematics for Computer Scientists & Mathematicians, Joe L. Mott, Abraham
Kandel, Theodore P. Baker, Pearson, 2

nd Edition (Units- III, IV, V).

REFERENCE BOOKS:
1. Discrete Mathematics and its Applications, Kenneth H. Rosen, 7

th Edition, McGraw Hill

Education (India) Private Limited.
2. Discrete Mathematics D.S. Malik & K. K. Sen, Revised Edition Cengage Learning.
3. Elements of Discrete Mathematics, C.L. Liu and D.P. Mohapatra, 4

th Edition, McGraw Hill

Education (India) Private Limited.
4. Discrete Mathematics with Applications, Thomas Koshy, Elsevier.
5. Discrete and Combinatorial Mathematics, R. P. Grimaldi, Pearson.
6. Discrete Mathematical Structures by Bernard Kolman, Robert C. Busby and Sharon Cutler
Ross, Pearson Education.

DATABASE MANAGEMENT SYSTEMS

Course Code- IT401

Module I
Introduction: Overview, Database System vs File System, Database System Concept and
Architecture, Data Model Schema and Instances, Data Independence and Database Language and
Interfaces, Data Definitions Language, DML, Overall Database Structure. Data Modeling Using the
Entity Relationship Model: ER Model Concepts, Notation for ER Diagram, Mapping Constraints,
Keys, Concepts of Super Key, Candidate Key, Primary Key, Generalization, Aggregation, Reduction
of an ER Diagrams to Tables, Extended ER Model, Relationship of Higher Degree.
Module II
Relational data Model and Language: Relational Data Model Concepts, Integrity Constraints,
Entity Integrity, Referential Integrity, Keys Constraints, Domain Constraints, Relational Algebra,
Relational Calculus, Tuple and Domain Calculus. Introduction on SQL: Characteristics of SQL,
Advantage of SQL. SQl Data Type and Literals. Types of SQL Commands. SQL Operators and
Their Procedure. Tables, Views and Indexes. Queries and Sub Queries. Aggregate Functions. Insert,
Update and Delete Operations, Joins, Unions, Intersection, Minus, Cursors, Triggers, Procedures in
SQL/PL SQL
Module III
Data Base Design & Normalization: Functional dependencies, normal forms, first, second, 8 third
normal forms, BCNF, inclusion dependence, loss less join decompositions, normalization using FD,
MVD, and JDs, alternative approaches to database design
Module IV
Transaction Processing Concept: Transaction System, Testing of Serializability, Serializability of
Schedules, Conflict & View Serializable Schedule, Recoverability, Recovery from Transaction
Failures, Log Based Recovery, Checkpoints, Deadlock Handling. Distributed Database: Distributed
Data Storage, Concurrency Control, Directory System.
Module V
Concurrency Control Techniques: Concurrency Control, Locking Techniques for Concurrency
Control, Time Stamping Protocols for Concurrency Control, Validation Based Protocol,
Multiple Granularity, Multi Version Schemes, Recovery with Concurrent Transaction, Case Study of
Oracle.
References:
1. Korth, Silbertz, Sudarshan,” Database Concepts”, McGraw Hill
2. Date C J, “An Introduction to Database Systems”, Addision Wesley
3. Elmasri, Navathe, “ Fundamentals of Database Systems”, Addision Wesley
4. O’Neil, Databases, Elsevier Pub.
5. RAMAKRISHNAN"Database Management Systems",McGraw Hill
6. Leon & Leon,”Database Management Systems”, Vikas Publishing House
7. Bipin C. Desai, “ An Introduction to Database Systems”, Gagotia Publications
8. Majumdar & Bhattacharya, “Database Management System”, TMH
9. R.P. Mahapatra, Database Management System, Khanna Publishing House