7th Sem

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING GOVERNMENT ENGINEERING COLLEGE, RAIPUR (C.G.)-492010

ARTIFICIAL INTELLIGENCE AND EXPERT SYSTEMS Course Title ARTIFICIAL INTELLIGENCE AND EXPERT SYSTEMS

Course Code CS701

Credits-3C L 3

T 1

Theory Paper (ES) P -

Max. Marks- 100 Min. Marks- 35 Duration-3hrs.

Faculty Member : CS\IT\ELEX OBJECTIVE : To expose the problems and techniques of artificial intelligence an d to introduce the concept in expert system and natural language understanding. 1. Search strategies : Production systems - Search strategies: Hill climbing, backtracking, graph search (algorithm A and A*) - Properties of A* algorithm, monotone restriction - Specialized production systems AO* algorithm. 2. Searching game trees : Minimax procedure, alpha-beta pruning - Introduction to predicate calculus Resolution refutation systems - Answer extraction. 3. Knowledge representation, reasoning : STRIPS robot problem solving system - Structured representations of knowledge: Semantic Nets, Frames, Scripts - Dealing with uncertainly: Non monotonic reasoning, certainty factors, Fuzzy reasoning. 4. An Introduction to Expert systems : An Introduction to Expert systems - Inference: Forward chaining, Backward chaining - Development Process - Languages and Tools - Explanation facilities - Knowledge acquisition. 5. Natural Language Processing : An Introduction to Natural language Understanding, Perception, Learning. TEXT 1. 2.

N.J. NILSSON, Principles of artificial Intelligence, Narosa Publishing House, 1980. D.W. ROLSTON, Principles of Artificial Intelligence and Expert systems Development, McGraw Hill International Edition, 1988. 3. E. RICH, Artificial Intelligence, McGraw Hill International, II Edition, 1991.

REFERENCES 1. 2.

R.FORSYTH, Expert systems, Principles and Case Studies, Chapman and Hill, 1985. R. KELLER, Expert system Technology Development and Application, Yourdon Press, 1987.

RELATED LINKS: • •

Where Intelligent Technology Meets the Real World Expert systems Expert systems www.aaai.org

1

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING GOVERNMENT ENGINEERING COLLEGE, RAIPUR (C.G.)-492010

PRINCIPLES OF COMPILER DESIGN Course Title PRINCIPLES OF COMPILER DESIGN

Course Code CS702

Credits-3C L 3

T 1

Theory Paper (ES) P -

Max. Marks- 100 Min. Marks- 35 Duration-3hrs.

Faculty Member : CS/IT/ET 1. Introduction : Introduction - The structure of a compiler - Different phases of a compiler - Finite Automata and Lexical Analysis. 2. The syntactic specification of programming languages : Context free grammars - Derivation and parse trees. Basic Parsing Techniques : Shift reduce parsing, Operator - precedence parsing, top down parsing, predictive parsing 3. LR Parser : SLR, Canonical LR, LALR - parsing table construction - Syntax Directed translation schemes - various forms of intermediate code. Translation of assignment statements, Boolean expressions, statements that alter flow of control 4. Translation of array references, symbol tables : Translation of array reference in arithmetic expressions, procedure calls, declarations, case statements. Symbol tables - run time storage administration - error detection and recovery 5. Code optimization and generation : Code optimization - Loop optimization - The DAG representation of basic blocks. Code generation - A simple code generator - Code generation from DAG's. Compilers compilers : YACC, Attributed parser generators. TEXT 1.

A.V. AHO and J.D. ULLMAN, Principles of compiler design, Addison - Wesley, 1977. REFERENCES

1. 2. 3. 4.

J.P. TREMBLAY and P.G. SORRENSON, The theory and practise of compiler writing, McGraw Hill, 1985. A.V. AHO, R.SETHI and J.D.ULLMAN , Compilers, Principles, Techniques and Tools, Addision Wesley, NewYork, 1985. A.V.AHO and J.D.ULLMAN, Theory of parsing translation and compiling, Prentice Hall of India, 1973. D.GRIES, Compiler construction for Digital computers, Wiley International, 1971.

2

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING GOVERNMENT ENGINEERING COLLEGE, RAIPUR (C.G.)-492010

Course Title ADVANCED SOFTWARE ENGINERING

Course Code CS703

Credits-3C L 3

T 1

Theory Paper (ES) P -

Max. Marks- 100 Min. Marks- 35 Duration-3hrs.

Branch: Computer Science and Engineering Unit I Object Oriented Software Engineering : The Object Oriented Paradigm Identifying the Elements of An Object Model, Management of object-Oriented Software Project Advanced Topics : Software Complexity, Software Reliability, Measuring Techniques Unit II Object-Oriented Analysis (OOA) : Domain analysis, Generic Components of 00 Analysis Model OOA Process, Object Relationship Model Object Behaviour Model Unit III Object-Oriented Design (OOD) : Design Issues, Generic Components of 00 Design Model, The System Design Process,The Object Design process, Design Pattems, Object-Oriented Programning. Unit IV Object-Oriented Testing : Testing OOA and OOD Models, Object Oriented Testing strategies, Test Case Design for 00 Software,Testing Methods, Interclass Test Case Design Unit V Computer Aided Software Engineering (CASE)& UML : Building Blocks of CASE, A Taxonomy of CASE tools, Integrated CASE Environments, Integration Architecture, The CASE Repository UML Case Study and Modeling. Suggested List of Experiments: Select any problem and using CASE tools (if needed) 1 Do object oriented analysis of the problem. 2.Do object oriented design of the problem. 3.Implement the problem in any object-oriented language. 4.Perform object oriented test methods on the product. 5.Explore the maintenance responsibilities. 6.Find software complexity of the software product. 7.Find software reliability of the software product. Text Book: 1. Software Engineering: A Practitioner's Approach - by R. S. Pressman Fourth edition 1997, McGraw-Hill pub.

3

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING GOVERNMENT ENGINEERING COLLEGE, RAIPUR (C.G.)-492010

Reference Books: 2. An Integrated Approach to Software Engineering – Pankaj Jalote. 3. Fundamentals of Software Engineering, Leon & Leon, Vikas Publishing House Pvt. Ltd. 4. Software Engineering, Sommervile, AWL (Pearson Education).

Course Title

Course Code

OPEN ELECTIVE-I CS704

Credits-3C L 3

T 1

Theory Paper (ES) P -

Max. Marks- 100 Min. Marks- 35 Duration-3hrs.

A. COMBINATORICS AND GRAPH THEORY Faculty Member : OBJECTIVE : To impart knowledge in permutations, combinations, recurrence relations, graph theory and representation of graphs. 1.Permutations and Combinations : Permutations and Combinations - Distribution of Distinct objects, Nondistinct objects - Generating Functions for Combinations, Enumerators for Permutations - Distributions of Distinct objects into Nondistinct cells, Portion of Integers, Ferrers Graph. 2. Recurrence Relations : Recurrence Relations- Linear Recurrence Relations with constant coefficients Solution by the Technique of Generating Functions - Recurrence Relations with Two Indices. Principles of Inclusion and Exclusion - General Formula Derangements - Permutations with Restrictions on Relative Positions. 3. Graph Theory: Basic Definitions - Trees and Fundamental Circuits - cut-sets and cut-vertices Connectivity and Separability - Network Flows - 1 and 2 isomorphisms. 4. Planar and Dual Graphs : Planar and Dual Graphs - Kuratowski's graphs - Representations of a Planar Graph - Detection of Planarity - Geometric dual - Combinatorial dual. Vector space associated with a graph - Subspaces - Orthogonal vectors and spaces. 5.Matrix Representation of Graphs : Matrix Representation of Graphs - Circuit Matrix - cutset Matrix Path Matrix - Adjacency Matrix - Coloring, Covering and Partitioning - Matching - covering - Coloring Problems - Algorithms for fundamental circuits, Cut-Vertices and separability. TEXT 1. C.L LIU, Introduction to Combinatorial Mathematics, McGraw Hill, 1976. 2. N. DEO, Graph Theory with Applications to Engineering and Computer Science, Prentice Hall of India, 1986. TEXT : 1.

C.L.Liu, Introduction to Combinatorial Mathematics, McGraw Hill, 1976.

4

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING GOVERNMENT ENGINEERING COLLEGE, RAIPUR (C.G.)-492010

2.

N.Deo, Graph Theory with Applicatopns to Engineering and Computer Science, Prentice Hall of India, 1986.

REFERENCES : 1. 2. 3. 4.

E.S.PAGE and L.B.WILSON, An introduction to computational Combinatorics, Cambridge University Press, 1979. H.M.BLAISDEL, Combinatorial Theory, 1967. H.J.RYER , Combinatorial Mathematics, John Wiley, 1963. M.N.S.SWAMY and K.THULASIRAMAN, Graphs, Networks and Algorithms, Wiley Interscience, 1981.

RELATED LINKS: • • • •

tutorials for combinatorics graph theory tutorials www.utm.edu mathforum.org links for research on algo's ,combinatorics and theory of computing Research Group on Graph Theory and Combinatorics

B. INTRODUCTION TO PARALLEL ARCHITECTURE Faculty Member : OBJECTIVE : To provide an introduction to the recent theory, trends and technique as related to parallel architecture. 1. Parallel computer models : Introduction -Flynn's Classification, Parallel & Vector Computer system Attributes to Performance - Implicit & Explicit Parallelism - Shared memory multiprocessors : Uniform & Non uniform memory access and Cache only memory access models - Distributed Memory Multicomputers multivector & SIMD computers - PRAM and VLSI models. 2. Program and network properties : Data dependance & Control dependance - Hardware & Software parallelism, Program participating & scheduling - Static multiprocessor scheduling system Interconnection architectures. 3. Performance Laws: Performance metrics & measures - Standard performance laws: Amdahl's law for fixed Workload - Bounded speedup model scalability analysis and approaches. 4. Processors and memory hierarchy : CISC & RISC Architectures - CISC family - RISC scalar processors - Super scalar processors and their features - Very long instruction word Architecture Vector & symbolic processors - Memory Hierarchy. 5. Pipelined processors : Basic considerations in Linear pipeline processors - Basics of Nonlinear pipeline processors - Design of pipelined architecture - Various considerations. Recent trends and developments. TEXT

5

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING GOVERNMENT ENGINEERING COLLEGE, RAIPUR (C.G.)-492010

1.

K. HWANG, Advanced computer architecture, Parallelism, scalability, programmability, McGraw Hill, NewYork, 1993.

REFERENCES 1. 2. 3.

K. HWANG & F. A. BRIGGS, Computer architecture and Parallel processor, McGraw Hill, NewYork, 1984. H. S. STONE, High performance computer architecture, Addison Wesley, Reading, MA, 1990. W. STALLINGS, Computer Organisation & Architecture, IV Edition, PHI, 1990

C. COMPUTER GRAPHICS Faculty Member : OBJECTIVE : To introduce the basic principles for the design, use and understanding of graphics systems. 1. Graphics systems : Graphics Hardware-Display devices-Hard copy Devices. Interaction Hardware Interaction Tasks - Basics and Composite - GKS - SRGP - Line drawing algorithms, Circle Generation Algorithms - Character Generation. 2. Raster Graphics : Basic Raster graphics algorithms - Scan conversion - Filling - Clipping - Antialiasing Halftoning 3. Geometrical Transformations : 2D and 3D transformations - Window to viewport transformation, Viewing in 3D - Projections - Specifying an arbitrary 3D views. 4. Modeling : 3D objects representation - Polygon surfaces - Curves and surfaces - Splines representation Modeling techniques - solid Fractals - Procedural - Grammar based models - Color models. 5. Visual realism and animation : Hidden line and Hidden surface removal algorithm - Illumination and Shading - shading models - Animation - Languages and rules for animationl, Recent trends and developments TEXT : 1.

J.D. FOLEY, A.VANDAM, S.K. FIENER and J.F. HUGHES, Computer Graphics : Principles and Practice, Second Edition, Addison - Wesley, 1996.

REFERENCES : 1. 2. 3. 4.

D.F. ROGERS, Procedural elements for computer Graphics, Mc-Graw Hill, 1985. D. HEARN and M.P.BAKER, Computer graphics, Second Edition, Prentice Hall of India, 1986. W.M. NEWMAN and R.F. SPROULL, Principles of Interactive Graphics, McGraw Hill International student Edition, 1991. PLASTOCK, Schaum's Outline Series, Computer graphics, Tata McGraw Hill, 1986.

6

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING GOVERNMENT ENGINEERING COLLEGE, RAIPUR (C.G.)-492010

PROFESSIONAL ELECTIVE-I Course Title

PROFESSIONAL ELECTIVE-I

Course Code

Credits-3C L

CS705

T

Theory Paper (ES) P

Max. Marks- 100 Min. Marks- 35 Duration-3hrs.

Neural Network & Fuzzy Logic Unit I Introduction & Fundamentals of Artificial Neural Networks : Biological Prototype, artificial neuron, single layer artificial networks. Pereceptrons : Perceptron representation, perceptron learning, pereeptron training algorithm. Unit II Back Propagation .. Introduction to Back propagation and back propagation training algorithm, counter propagation networks. Unit III Kohonen Self Organizing Networks : Introduction, the Kohonen algorithm, weight training, Grossberg layer, training the Grossberg layer. Unit IV Hopfield Networks : Introduction, the Hopfield Model, Hopefield Network algorithm Boltzman's Machine applications of Hopfield networks, associative memories, bidirectional associative memories. Unit V Adaptive Resonance Theory : Architecture of adaptive resonance theory, algorithm, applicability of artificial neural network to pattern recognition and image processing, dimensionality of neural networks for pattern recognition. Suggested further readings : 1. Neural Computing : Theory and Practice : Waserman 2. "An Introduction to Neural Computing", 1. Alexander & Helen Marton William Jackson.

7

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING GOVERNMENT ENGINEERING COLLEGE, RAIPUR (C.G.)-492010

Optimization Methods Unit-I Introduction; optimal problem formulation, design variables, constraints, objective function, variable bounds, engineering optimization problems; optimal design of a transit schedule, optimal design of a car suspension, optimization algorithms, single variable optimization algorithms, optimality criteria, bracketing methods, fibonacci search method, golden section search method, point-estimation method, successive quadratic estimation method, gradient-based methods; Newton-Raphson method, bisection method, secant method, cubic search method, root-finding using optimization techniques. Unit-II Multivariable optimization algorithms; optimality cirteria, unidirectional search, direct search methods, evolutionary optimization method, simplex search method, hooke-jeeves pattern search method, Powell's Conjugate direction method, gradientbased methods, Cauchy's steepest descent method, Newton, method, Marquardt’s methods, Conjugate gradient method variable-metric method. Constrained optimization algorithms; Kuhu-Tucker conditions, Transformation methods; penalty funciton method, method of multipliers, sensitivity, direct search for constrained minimization; variable elimination method, complex search method, random search methods, linearized search techniques, Frank-wolfe method, cutting plane method, feasible direction method, generalized reduced gradient method, gradient projection method. Unit-III Specialized algorithms; integer programining; penalty function method, branch and bound method, geometric programming. Linear programming algorithms, linear programming problem; simlex method, artificial variables and dual phase method. Unit-IV Non traditional optimization algorithms, geometric algorithims, working principles, differences and similarities between GAs and traditional methods, GAs for constrained optimization, other GA operators, real-coded Cas advanced GAs.. Simulated annealing, global optimization using the steepest descent method, GAs, using simulated annealing Unit-V Queuing models, concept of queuing models and,. their general-,applicability to a broad range of situations, specification and measure of queuing systems, structures of basic queuing systems, definition and classification of stochastic processes, discrete-time markov chains, continuous markov chains, brith-death processes. Suggested Further Readings

8

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING GOVERNMENT ENGINEERING COLLEGE, RAIPUR (C.G.)-492010

12345-

Optimization for engineering design – kalyanmoy Deb. –PHI Pvt. Ltd. Engineering Optimization – Methods & Applications- G.V. reklaitis, Aravindaran & K.M. Ragsdell – John Wiley,New York. Optimization theory and application – S.S. Rao – Wiley Eastern New Delhi Linear Algebra and its applications – G. Strang – Academic Press Orlando.

Telecommunication Network Unit I Introduction and examples of telemetric, analog versus digital switching, functional stricture of digital exchange, exchange termination for analog and digital trunk lines and terminals, line coding, digital private branch exchange, rural exchange, and interference. Time and space switching, switch matrices, TSI, combination of time and space switching, traffic and trunking. Unit II Basic elements of ISDN, construction of ISDN, modelling, fundamental of ISDN architecture, ISDN services, transmission technique, protocols, synchronization and switching, interface between PABX and computer equipment. user network interference. Elements of digital television, HDTV, video text, teletext, i-nobile communication (cellular concept). Unit III Introduction to digital telegraph transmission, switch and forward telegraphy, dum and intelligent teleprinter, FAX transmission and reception, electronic mail system. Unit IV Introduction to spread spectrum modulation, direct sequence (DS) spread spectrum, spreads spectrum with code division multiple access (CSMA), ranging, frequency hopping (FH) spread spectrum, PN sequence generation acquisition, and tracking of FH signal signals. Unit-V Local access Techniques Improvement in cable bandwidth XDSL, ADSL, etc. wire less local loop, radio trunking fibres in local loop. Suggested Further Reading: 1. 2.

Telecommunication Switching System by Thygrajan & Vishwanathan. Cellular Mobile System by Lee.

Fault Tolerants & Real Time Systems Unit I Introduction to real-time system ; Definition, components of a real time system sensor and transducers, signal conditioning, computer input and output, the processor output conditioning and power control, actuators. Computer hardware requirements for real time system, general purpose

9

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING GOVERNMENT ENGINEERING COLLEGE, RAIPUR (C.G.)-492010

computer, CPU, memory RAM, ROM, Cache memory DMA, selection of memory, buses computer input and output. Real time operating system : Concepts basic elements of an operating system, operating systems facilities, real time operating systems, tasks and task scheduling, task synchronization and data transfer factors in selecting a realtime operating system.

Unit II Design of real-time systems : Prelude to the design process General approach, the system components, the design specifications, the development environment, hardware development system software. Analysis and design : Analysis of required documents, response-time specification on human interface, preliminary system design, block diagram, representation of control flow and data flow, functional decomposition and relationship among them, modular design, estimation of cost, required development time, program length, execution time and required memory. Software Design Structural flowcharts, stepwise development and programming, testing the model. Unit III Selection of programming languages Machine' and assembly languages, limitations of assembly language, high-level languages, advantages and disadvantages of high level languages, real time languages, choosing a language. Integrating assembly-language components Processor background information required, subroutine calls and returns, subroutine parameters, linking high and low level programs, start up routines, computer interrupt systems and service routines. Unit IV Interface and control : Parallel input and output interfaces, D to A and A to D conversion interface, digital representation of analog voltage full scale voltage, successive approximation A/0, dual slope A/D, flash converter sample and hold circuit, the multiplexer, real time clock interfaces, direct memory access interfaces. Input Systems : Sensors with binary-state supports, sensors that produces, continuous analog signals, signal conditioning circuits, transmission circuitry, bus compatible input systems. Output Systems : output systems involving two state actuators, output systems with continuous actuators. Unit V Board-based microcomputer systems, The Backplane Bus : Address and data lines, data transfer lines interrupt lines, and microprocessor control lines. Power supply lines, characteristics boards or bus systems CPU board, memory board, peripheral device controller and 1/0 boards, selecting a bus system, Study of fault tolerant systems : Concept of fault tolerant in A system different characteristics and features of fault tolerant systems. Suggested further readings 1. Principles of real time systems By Levi and Agrawala.

Data Mining and Warehousing. Information, Theoretic Approach to knowledge discovery – Data explosion in the Internet Age, Knowledge discovery in databases (KDD), Verification-Based Methods of Data Mining, Feature Selection Methods, Learning issues, Information theory-the data mining perspective, Data Modeling, Book Organization. Automated data pre-processing – Discretization of Ordinal Features, Static Discretization Algorithms, The Partitioning Procedure, Computational Complexity of the static Algorithm, Static Discretization and Dimensionality Reduction.

10

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING GOVERNMENT ENGINEERING COLLEGE, RAIPUR (C.G.)-492010

Information-Theoretic Connectionist Networks- A Unified Approach to Data Modeling, Constant Structure information-Theoretic Networks, Multi-Layer Information-Theoretic Network, Dynamic Discretization of Ordinal Attributes. Post-Processing of Data Mining Results-Rule Extraction and Reduction, Prediction, From Local to Global Modeling. Methodology of Application- Overview of the Discovery Process, Understanding the Problem Domain, Obtaining and Understanding the Data, Preparation of the Data, Construction of the Knowledge Model from Data, Evaluation of the Model, Using the Model (Interpreparation and Post – Processing) Advanced data mining methods-Anytime Algorithm for Knowledge Discovery, Data Reliability. Summary and Some Open Problems- Methods Benefits and Limitations Future Research. References-Knowledge Discovery and Data Mining. By oded Maimon & Mank last. Kluwer Academic Publisher.

COMPILER DESIGN LAB Faculty Member : Lab Excercises involving • • • •

Design of lexical analysers. Design of parsers like recursive-descent parser for a block structured language with typical constructs. Typical exercises using LEX and YACC.

Quadrapules / Triples generation using LEX and YACC for a subset of a block structured language. e.g. PASCAL

NETWORK ENGINEERING LABORATORY 11

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING GOVERNMENT ENGINEERING COLLEGE, RAIPUR (C.G.)-492010

Faculty Member : Lab Excercises involving • • • • • • • • • • •

Familiarisation with configuring and installing a LAN Experimenting with network protocols for achieving communication between computers Experimenting with interconnection software for communication between two different network architectures Experimenting using TCP/ICP protocol suit Using protocols such POP, emails, http, etc., To design and implement a web server and web client Knowing internet/web browser implementation details To design a mini search engine Web programming using HTML/XML/Perl/Java Network Security : email security/web security Firewall design

12