5th Sem

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

PRINCIPLES OF OPERATIONS RESEARCH Course Title PRINCIPLES OF OPERATIONS RESEARCH

Course Code CS501

Credits-3C L 2

T 1

Theory Paper (ES) P -

Max. Marks- 50 Min. Marks- 18 Duration-3hrs.

Faculty Member : MCA/Civil/Mechanical/CSE/ECE Faculty OBJECTIVE : To expose the students to linear programming, CPM, PERT, Replacement problems inventory models. 1.Linear programming problems : Linear programming problems(LPP) - Formulation of a LPP - Graphical method - Simplex method - Revised simplex method - two phase method - Dual simplex method - Primal Dual problem (Emphasis should be on algorithms and problems). 2.Transportation and Assignment problems : Principles of duality - interpretation - sensitivity analysis degeneracy - Transporation and Assignment problems - Applications (Emphasis should be more on problems than theory). 3. CPM and PERT : CPM and PERT - Network diagram - Events and activities - Project planning Reducing critical events and activities - critical path calculations - Examples - Resources and man power levelling. Sequencing problems - Traveling salesman problems - machine scheduling problem (job-shop). 4. Replacement problems and Inventory models : Replacement problems - capital equipment - Discounting costs - Replacement in anticipation of failure - Group replacement - stochastic nature underlying the failure phenomenon. Inventory models - various costs - Deterministic inventory models - Economic lot size - Price break - Finite storage. 5. Inventory Model Applications and Dynamic Programming : Single period inventory model with shortage cost - stochastic models - Applications of Inventory models. Dynamic programming Formulation Investment problem - general allocation problem - stage coach problem - Production scheduling. TEXT : 1.

H.A.TAHA, Operations Research - An Introduction, Macmillan, 1976.

REFERENCES : 1. 2. 3.

B.E.GILLET , Introduction to operations Research - A computer oriented algorithmic approach, McGraw Hill, 1989. H.M.WAGNER , Principles of operations Research with Applications to Managerial Decisions, PH, Inc., 1975. K.SWARUP, P.K.GUPTA and A. MANMOHAN, Operations Research, Second Edition, Sultanchand, 1978.

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

DATA COMMUNICATION Course Title

Course Code

DATA COMMUNICATION CS502

Credits-3C L 2

T 1

Theory Paper (ES) P -

Max. Marks- 50 Min. Marks- 18 Duration-3hrs.

Faculty Member : CSE/ECE OBJECTIVE : To impart knowledge in information theory and coding, modulation systems, communication techniques and telephone systems an modems. 1. Information Theory and coding : Discrete Messages - concepts of amount information-Entropyinformation rate- Shannon's theorem- channel capacity - use of orthogonal signals - Introduction to coding parity check bit coding - Block codes - Coding and Decoding - Algebraic codes, burst error correction codes - Convolution coding. 2. Modulation Systems : Basics of AM, FM and PM - modulation and demodulation of AM, FM Frequency Translation. Pulse modulations systems - Basics of PAM, PCM, DM - Sampling and quantization of analog signals - Quantization error. 3. Digital Data Communication : Communication model - Analog and Digital Data Transmission Transmission impairments - Transmission media - Data encoding. 4. Communication Techniques : Synchronous and Asynchronous transmission - Interfacing. Data link control - Line configurations - Flow control and error control - Bit oriented link control - HDLC and SDLC - Multiplexing. 5. Telephone systems and modems : Basics telephone service - Dialing - Telephone Lines - Private Exchange - Role of Modems - Source specific modems - other specialized modems, Recent trends and developments. TEXT 1. 2.

H. TAUB and D.L. SCHILLING, Principles of Communication Systems, McGraw Hill, 1986. W. STALLINGS, Data and Computer Communications, Maxwell and Macmillan Press, 1997.

REFERENCE 1.

W.L. SCHWEBAR, Data Communications, McGraw Hill,1988.

RELATED LINKS

1. Telecommunication Electronics Page 2. University College London, Lecture notes for Data Communication Networks and Distributed Systems

3. University of Toronto,Course Notes for Data Communication

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

DESIGN AND ANALYSIS OF ALGORITHMS Course Title DESIGN AND ANALYSIS OF ALGORITHM

Course Code CS503

Credits-4C L 3

T 1

Theory Paper (ES) P -

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

PREREQ : BCS304 DATA STRUCTURES Faculty Member : CSE 1. Algorithms : properties & basic concepts correctness, average and worst-case analysis, time and space complexity, notion of optimality. Examples: Finding the largest and Second largest entries in a list, The Tournament Method, Evaluating Polynomial functions, preprocessing of coefficients. 2. Divide and Conquer and Greedy Algorithms : Divide and Conquer method : Finding the maximum an minimum - Quick Sort - Selection - Strassen's matrix multiplication. Greedy Method : Knapsack problemJob sequencing with deadlines- Minimum Spanning trees. 3. Dynamic Programming and Algebraic Transformation : Dynamic Programming : Multistage graphs- All pairs shortest paths- Optimal binary search trees - traveling salesman problem. Algebraic simplification and transformations : Fast Fourier Transform- Modular arithmetic. 4. Backtracking and Branch and bound : Backtracking : Eight Queen Problem- Sum of subsets- graph colouring. Branch and Bound : 15 - Puzzle Problem - traveling salesman problem- Efficiency considerations. 5. Introduction to NP-Completeness : NP-Hard and NP- complete problems : Basic concepts- Reducibility Cook's theorem (without proof) - Turing Machines - NP-Hard Graph Problems TEXT 1. 2.

T.H.CORMEN, C.E. LEISERSON, R.L.RIVEST, Introduction to Algorithms, The MIT press, Cambridge, Massachussets and McGraw Hill, 1990. E.HOROWITZ and S.SAHNI, Fundamentals of Computer Algorithms, Galgotia,1988.

REFERENCES 1. 2. 3. 4.

A.V. AHO, J.E.HOPCROFT and J.D.ULLMAN, The Design and Analysis of Computer Algorithms, Addison Wesley,1974. S. BAASE , Algorithms - Introduction to Design and Analysis, Addison Wesley, 1983. H.S.WILF, Algorithms and Complexity, Prentice Hall, Inc., 1986. R.E.REAPOLITAN & K. NAIMIPOUR, Foundations of algorithms, D.C.Health and Company, 1996

RELATED LINKS

1. Introduction to Algorithms , Second Edition by Thomas H. Cormen, Charles E. Leiserson, Donald L. Rivest and Clifford Stein

2. Algorithms Dictionary by Paul Black

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

3. The Stony Brook Algorithms Repository MICROPROCESSORS AND INTERFACING TECHNIQUES Course Title MICROPROCESSORS AND INTERFACING TECHNIQUES

Course Code CS504

Credits-4C L 3

T 1

Theory Paper (ES) P -

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

Faculty Member : CSE Faculty OBJECTIVE : To introduce the Principles of Microprocessor architecture using 8085 and to illustrate the interface design practice using various chips. 1. Introduction to 8085 Microprocessor: 8085 Microprocessor, Architecture, Bus Organization, Registers, ALU, Control section, Instruction set of 8085, Instruction format, Addressing modes, Types of Instructions. 2. Assembly Language Programming and Timing Diagram: Assembly language programming in 8085, Macros, Labels and Directives, Microprocessor timings, Micro instructions, Instruction cycle, Machine cycles, T states, State transition diagrams, Timing diagram for different machine cycles. 3. Serial I/O, Interrupts and Comparison of Contemporary Microprocessors: Serial I/O using SID, SOD. Interrupts in 8085, RST instructions, Issues in implementing interrupts, Multiple interrupts and priorities, Daisy chaining, Interrupt handling in 8085, Enabling, disabling and masking of interrupts. Brief comparison of contemporary 8-bit microprocessors like Z-80, M68000 with 8085. 4. Data Transfer techniques: Data transfer techniques, Programmed data transfer, Parallel data transfer using 8155. Programmable parallel ports and handshake input/output. Asynchronous and Synchronous data transfer using 8251A. Programmable interrupt controller 8259A. DMA transfer, cycle stealing and burst mode of DMA, 8257 DMA controller. 5.Microprocessor Interfacing Techniques: Interfacing memory and I/O devices, Addressing memory, interfacing static RAMs, Interfacing and refreshing dynamic RAMs, Interfacing a keyboard, Interfacing LED and seven segment displays, Interfacing a printer, Interfacing A/D converters, D/A converters. TEXT 1. 2.

R.S. GAONKAR, Microprocessor Architecture, Programming and applications with the 8085/8080A, Wiley Eastern Ltd, Second Edition, 1986. A.H.MUHOPADHYAY, "Microprocessor Based Laboratory Experiments and Projects", Wheeler Publishing, 1997

REFERENCES 1.

2.

D.V.HALL , Microprocessors and Digital Systems, McGraw Hill International students Edition, 1986. A.P.MATHUR, Introduction to Microprocessor, Tata McGraw Hill, 1980.

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

PRINCIPLES OF PROGRAMMING LANGUAGES Course Title PRINCIPLES OF PROGRAMMING LANGUAGES

Course Code CS505

Credits-4C L 3

T 1

Theory Paper (ES) P -

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

Faulty Member: cse OBJECTIVE : To expose the students to different paradigms of programming techniques such as imperative, Object- Oriented , logic and Parallel Programming. 1. Introduction : Language Paradigms - Criteria for a good Language design. Data types, Abstraction Imperative languages: Algol, Pascal, C - Trouble spots - design issue - Parameter passing methods - type system.. 2.Object-Oriented Programming : Object-oriented programming - Data Encapsulation, Classes in C++, Over Loading, Derived classes and Information hiding, Inheritance and Polymorphism, Generic Functions. 3.Functional Programming : Functional Programming - Introduction to LISP, Lists, Storage allocation for lists, some useful functions, ML - Static type checking, Exception handling in ML. 4. Logic Programming : Logic programming - Computing with relations, Introduction to Prolog, Data structures in Prolog, Programming techniques, Control in Prolog, Cuts. 5. Parallel Programming : Parallelism - Synchronisation - Concurrency - deadlocks - mutual exclusion monitors. Concurrent programming - communicating sequential processes: introduction, concepts and notation, parallel, input-output commands, guarded commands, alternation, classical problems. TEXT 1.

R. SETHI, Programming Languages: Concepts and Constructs, Addison Wesley, 1990.

REFERENCES 1. 2. 3.

C.A.R.HOARE , "Communicating Sequential processes," Communications of ACM, Vol.21, No.8, August 1978. E.HOROWITZ , Fundamentals of Programming Languages, Galgotia, 1983. D. APPLEBY, Programming Languages, Paradigm and Practice, McGraw Hill, 1991.

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

COMPUTER GRAPHICS & MULTIMEDIA Course Title COMPUTER GRAPHICS & MULTIMEDIA

Course Code CS506

Credits-4C L 3

T 1

Theory Paper (ES) P -

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

Faculty Member: CSE/ECE Unit I Introduction to Raster Graphics, Graphics System Architecture, Concept of scan Conversion of Drawing Primitive 2D and 3D Geometrical transformation, Concept of Windows and View port, 3D Viewing and perspective transformation Unit II Illumination and shading models, colors & colors models, geometric transformation of images & image composing filling algorithm, managing windows with bitable Unit III Multimedia: Definition, component text, audio, graphics, video & hypertext Multimedia Hardware: Peripherals Connection: SCSI, IDE, MCI Unit IV Memory: Optical Storage, CDs, Video Disc Players Input Methodology: Pens, Image Scanners, Digital Camera, Digital Audio, Full motion Video, video camera devices Multimedia data & File format standards: RTF, TIFF, MIDI, JPEG-, DIB, JPEG-AVI, MPEG Unit V Multimedia Software: Basic Tools, Presentation tools Multimedia Authoring tools: Types Of Authoring Tools, Card and Page based Authoring tools, illustrations through some authoring tools like author ware Professional (Window based): Editing, Authoring, Presentations, Object Oriented Authoring tools. Suggested Experiments: Image Processing & Pattern Recognition Animation of an object Program 2D & 3D image program Other related program Text books Tay Vaughan “ Multimedia: making it work” Tata McGraw Hill 1999, 4th edition Prabhat k Andleigh, Kiran Thakral “Multimedia System Design”, PHI Folay Vandam, Feiner, Hughes “Computer Graphics Principle & Practice” Adison Wesley,2/e. 1997

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

MICROPROCESSORS AND INTERFACING TECHNIQUES LABARATORY Faculty Member: CSE Faculty • • • • • • •

Solving problems using 8085 Interfacing various devices with the microprocessor such as A/D converter, D/A converter Seven Segment displays Stepper motor External keyboard Interrupt Controller and 8251 for serial data transfer Interfacing using Micro Controller Trainer Kits.

PROGRAMMING LANGUAGES LABORATORY Faculty Memer: CSE Problems using • • • •

Functional programming techniques through LISP. Object-oriented programming methods through C++/Java/COM . logic programming techniques throuogh PROLOG. Prallel programming techniquesthrough OCCAM / Parallel C.