III/IV B.TECH.(CSE) II - SEMESTER
CSE 3.2.1
COMPILER DESIGN Credits:4
Instruction: 3 Periods & 1 Week./Week Sessional Marks : 30
Univ_ Exam : 3 Hours Univ_ Exam Marks:70
The Theory of Automata: Definition and description, Transition systems, properties, Acceptability of string, NDFA, Equivalence in between DFA & NDFA. Grammars, Types of Grammars, Grammars and Automata, Regular expressions, Finite Automata and Regular expressions, Regular sets and Regular Grammars.
Overall view of Compilers: Brief discussion on various phases of Compilers.
Design of lexical analyzer.
Design of Parsers: Shift Reduce parser, Operator Precedence Parser, Predictive Parser, LR parser, SLR
parser. LALR parser.
Syntax Directed Translation: Syntax directed translation and implementation, Intermediate code, Postfix notation, parsing tree, Three address Code, Quadruples, Triples.
Intermediate Code Optimization: The principle sources of optimization, Loop Optimization, DAG, Global data flow analysis.
Code Generation: Problems, Machine model, A simple code generator, Register allocation and assignment, Code generation from DAG, Peep hole optimization.
Brief discussion on symbol tables, Run-time storage administration.
chapters: 1,2,3,4,5,6,7,9,10,11,12,15 of the text book.
Text Book
Principles of Compiler Design by Aho, D. Ullman
Reference Books:
Compiler Construction by Kenneth. C. Louden, Vikas Pub. House.
CSE 3.2.2 DESIGN AND ANALYSIS OF ALGORITHMS Credits:4
Instruction: 3 Periods & 1 Tut /week Sessional Marks: 30
Univ. Exam : 3 Hours Univ-Exam-Marks:70
Introduction – Fundamentals of algorithmic problem solving – important problem types –
fundamental data structures.
Fundamentals of analysis of algorithms and efficiency – Analysis framework – Asymptotic Notations and Basic Efficiency classes – Mathematical Analysis of Non-recursive Algorithms – Mathematical Analysis of recursive Algorithms – Empirical Analysis of Algorithms – Algorithm Visualization
Brute Force – Selection Sort and Bubble sort – Sequential Search and Brute – Force String
Matching – Closest Pair and Convex-Hull Problems by Brute Force – Exhaustive Search
Divide-and-Conquer – Mergesort – Quicksort – Binary Search – Binary Tree Traversals and Related Properties – Multiplication of large integers and Strassen’s Matrix Multiplication – Closest- Pair Convex-Hull Problems by Divide- and – Conquer
Decrease – and – Conquer – Insertion Sort – Depth-First Search and Breadth-First Search- Topological Sorting – Algorithms for Generating Combinatorial Objects – Decrease-by-a- Constant-Factor Algorithms – Variable-Size-Decrease Algorithms
Transform-and-Conquer – Presorting – Gaussian Elimination – Balanced Search Trees – Heaps and Heapsort – Horner’s Rule and Binary Exponentiation – Problem Reduction
Space and Time Tradeoffs – Sorting by Counting – Input Enhancement in string Matching – Hashing – B-Trees
Dynamic Programming – Computing a Binomial Coefficient – Warshall’s and Floyd’s Algorithm
– Optimal Binary Search Trees - The Knapsack Problem and Memory Functions.
Greedy Technique – Prim’s Algorithm – Kruskal’s Algorithm – Dijkstra’s Algorithm – Huffman Trees Limitations of Algorithm Power – Lower-Bound Arguments – Decision Trees – P, NP and NP – complete problems – Challenges of Numerical Algorithms
Coping with the Limitations of Algorithms Power – Backtracking – Branch-and-Bound – Approximation Algorithms for NP-hard Problems – Algorithms for solving Nonlinear Equations.
Text Book:
Introduction to Design & Analysis of Algorithms by Anany Levitin, Pearson Education, New
Reference Books:
1.
In
trodu
ction to Algorith
ms
by
Tho
mas
H.
Cor
man,
Ch
arle
s E.
L
eiserso
n,
Ron
ald
R. Rivest & Cliffo
rd
Stein,
Pren
tice Hall of Ind
ia,
New Delhi, New Delhi
2. The Design and Analysis of computer Algorithms, Aho, Hopcroft & Ullman, Pearson
Edu
catio
n, New Delhi,
20
03
3. Fundamentals of algorithmics, Gilles Brassard & Paul Bratley, Prentice Hall of India, New
CSE 3.2.3 DATABASE MANAGEMENT SYSTEMS Credits:4
Instruction: 3 Periods & 1 Tut /week Sessional Marks: 30
Univ. Exam : 3 Hours Univ-Exam-Marks:70
Introduction to DBMS: Overview, File system vs DBMS, Advantages of DBMS, Storage data, queries, Transaction Management, DBMS structure
E-R model: Entities, Attributes and Entity sets, Relation ship and Relation ship sets, Features of ER
model, Conceptual database design with ER model
Relational model: Integrity constraints over relations and enforcement, Querying relation data, Logical database design, views, destroying/altering tables and views
Relational Languages: algebra and calculus
SQL: Basic SQL, Query, union, interest, except, Nested Queries, Aggregated Operation, Null values, Embedded SQL, cursors, ODBC and JDBC, Triggers and Active database, designing active databases
Schema refinement and normal forms : Schema refinement, fds, reasoning normal forms, normalization up to 3rd & BC normal forms, lossless join & dependency preserving decomposition
Transaction management: Transaction concept, transactions and schedules, concurrent execution of transactions, lock – based concurrency control, crash recovery
Concurrency control : Lock management, specialized locking techniques, concurrency control without locking
Crash Recovery: Aries, recovering from a system crash, media recovery
Text Book:
Database Management Systems by Raghu Ramakrishnan and Johannes Gehrke, McGraw-Hill
CSE 3.2.4 DATA COMMUNICATIONS Credits:4
Instruction: 3 Periods & 1 Tut /week Sessional Marks: 30
Univ. Exam : 3 Hours Univ-Exam-Marks:70
1. An Introduction to Data Communications:
A Communications Model, Data Communications and Data Communications
Networking, Protocols and Protocol Architecture, Characteristics of Data Transmission: Concepts and Terminology, Analog and Digital Data Transmission, Transmission
Impairments
2. Transmission Media:
Guided Transmission Media, Wireless Transmission Data Encoding, Digital Data, Digital Signals, Digital
Data, Analog Signals, Analog Data, Digital Signals, Analog Data, Analog Signals
3. The Data Communication Interface
Asynchronous and Synchronous Transmission, Line Configurations, Interfacing.
Data Link Control Flow Control, Error Detection, Error Control, High-Level Data Link Control
(HDLC),Other Data Link Control Protocols.
4. Data Communications Hardware: Terminals
Introduction, Basic Terminal Components, Enhanced Terminal Components, General-Purpose Terminals, Remote Job Entry Terminals, Transaction Terminals, Clustering of Terminal Devices. Communications Processing Hardware Introduction, Switching Processors, Multidrop Lines, Multiplexers, Concentrators, Front-End Processors.
5. Modems:
Network Attachment and Regulations, Line Conditioning and Leased Lines, Modems and Modem Circuits. Multiplexing: Frequency-Division Multiplexing, Synchronous Time-Division Multiplexing: Characteristics, TDM Link Control, Digital Carrier Systems Statistical Time-Division Multiplexing: Characteristics.
TEXT BOOKS:
1. William Stallings, Data and Computer Communications, 7th Edition, Pearson Education Inc., 2004
2. Mary E.S. Loomis, Data Communications, PHI-N.J.,1983 (Capter 3, Chapter 5)
3. Paul Bates, Practical Digital and Data Communications, PHI-N.J, 1987(Chapter5)
REFERENCE BOOKS:
1.Behrouz A. Forouzan, Data Communications and Networking, 3rd EditionTMH, 2004
2.William A. Shay, Understanding Data Communications & Networks, 2nd Edition
Thomson-Brooks/Cole - Vikas publishing House, 1999
3. Michale A. Miller, Data & Network Communications, Thomson/Delmar - Vikas Publishing
House, 2000
CSE 3.2.5 ELECTIVE-II PRINCIPLES OF PROGRAMMING LANGUAGES Credits:4
Instruction: 3 Periods & 1 Tut /week Sessional Marks: 30
Univ. Exam : 3 Hours Univ-Exam-Marks:70
Language Design Issues: Why Study Programming Languages, A Short History of Programming
Languages, Role of Programming Languages, Programming Environments
Impact of Machine Architectures: The Operation of a Computer, Virtual Computers and Binding
Times
Language Translation Issues: Programming Language Syntax, Stages in Translation, Formal Translation
Models, Recursive Descent Parsing.
Modeling Language Properties: Formal Properties of Languages, Language Semantics.
Elementary Data Types: Properties of Types and Objects, Scalar Data Types, Composite Data Types Encapsulation: Structured Data Types, Abstract Data Types, Encapsulation by Subprograms, Type Definitions.
Inheritance: Abstract Data Types Revisited, Inheritance, Polymorphism
Sequence Control: Implement and Explicit Sequence Control, Sequence with Arithmetic Expressions, Sequence Control Between Statements, Sequencing with Nonarithmatic Expressions.
Subprogram Control: Subprogram Sequence Control, Attributes of Data Control, Parameter
Transmission, Explicit Common Environment.
Storage Management: Elements Requiring Storage, Programmer- and System - Controlled Storage, Static
Storage Management, Heap Storage Management
Distributed Processing: Variations on Subprogram Control, Parallel Programming, Hardware
Developments, Software Architecture.
Network Programming: Desktop Publishing, The World Wide Web
Text Book:
Programming languages – Design and Implementation by Terrence W. Pratt Marvin V. Zelkowitz.
3 rd Edition, Prentice Hall of India.
References:
1. Concepts of Programming Languages by Robert L. Sebesta, 4th Edition, Pearson
Education.
2. Fundamentals of Programming Languages, Design & Implementation by Seyed H.Roosta. Vikas publications.
3. Programming Languages by Paradigm and Practice – Doris Appleby Julius J. Vendekopple Tata
McGraw Hill Edition.
CSE 3.2.5 ELECTIVE-II BIOINFORMATICS Credits:4
Instruction: 3 Periods & 1 Tut /week Sessional Marks: 30
Univ. Exam : 3 Hours Univ-Exam-Marks:70
1. Introduction:
Definitions, Sequencing, Biological sequence/structure, Genome Projects, Pattern recognition an prediction, Folding problem, Sequence Analysis, Homology and Analogy.
2. Protein Information Resources
Biological databases, Primary sequence databases, Protein Sequence databases, Secondary databases, Protein pattern databases, and Structure classification databases.
3. Genome Information Resources
DNA sequence databases, specialized genomic resources
4. DNA Sequence analysis
Importance of DNA analysis, Gene structure and DNA sequences, Features of DNA sequence analysis, EST (Expressed Sequence Tag) searches, Gene hunting, Profile of a cell, EST analysis, Effects of EST data on DNA databases
5. Pair wise alignment techniques
Database searching, Alphabets and complexity, Algorithm and programs, Comparing two sequences, sub-sequences, Identity and similarity, The Dotplot, Local and global similarity, different alignment techniques, Dynamic Programming, Pair wise database searching.
6. Multiple sequence alignment
Definition and Goal, The consensus, computational complexity, Manual methods, Simultaneous methods, Progressive methods, Databases of Multiple alignments and searching
7. Secondary database searching
Importance and need of secondary database searches, secondary database structure and building a sequence search protocol
8. Analysis packages
Analysis package structure, commercial databases, commercial software, comprehensive packages, packages specializing in DNA analysis, Intranet Packages, Internet Packages.
Text Books:
1. Introduction to Bioinformatics, T K Attwood & D J Parry-Smith
Addison Wesley Longman
2. Bioinformatics- A Beginner’s Guide, Jean-Michel Claveriw, Cerdric Notredame
WILEY dreamlech India Pvt. Ltd
Reference Books:
1. In
trodu
ction
to Bio
in
format
ics
, Arthu
r M.Lesk,
OXFORD p
ub
lish
ers (Indian
Ed
itio
n)
CSE 3.2.5 ELECTIVE-II IMAGE PROCESSING Credits:4
Instruction: 3 Periods & 1 Tut. /Week Sessional Marks: 30
Univ.-Exam : 3 Hours Univ-Exam-Marks:70
1. Fundamentals of Image Processing
Image Acquisition, Image Model, Sampling, Quantization, Relationship between pixels, distance measures, connectivity , Image Geometry, Photographic film. Histogram: Definition, decision of contrast basing on histogram, operations basing on histograms like image stretching, image sliding, Image classification. Definition and Algorithm of Histogram equalization.
2. Image Transforms:-
A detail discussion on Fourier Transform, DFT,FFT, properties. A brief discussion on WALSH Transform , WFT, HADAMARD Transform, DCT.
3. Image Enhancement: (by SPATIAL Domain Methods)
a )Arithmetic and logical operations, pixel or point operations, size operations, b. Smoothing filters- Mean, Median, Mode filters – Comparative study, c.. Edge enhancement filters – Directorial filters, Sobel, Laplacian, Robert, KIRSCH, Homogeneity & DIFF Filters, prewitt filter, Contrast Based edge
enhancement techniques. Comparative study. d. Low Pass filters, High Pass filters,
sharp
en
ing
filters.
– Co
mp
arativ
e Stud
y.
e.
Co
mp
arativ
e study
o
f all filters.
f. Co
lo
r image
p
ro
cessin
g.
4. Image enhancement : (By FREQUENCY Domain Methods). Design of Low pass, High pass, EDGE Enhancement, smoothening filters in Frequency Domain. Butter worth filter, Homomorphic filters in Frequency Domain. Advantages of filters in frequency domain, comparative study of filters in frequency domain and spatial domain.
5. Image compression: Definition, A brief discussion on – Run length encoding, contour coding, Huffman code, compression due to change in domain, compression due to quantization, Compression at the time of image transmission. Brief discussion on:- Image Compression standards.
6. Image Segmentation: Definition, characteristics of segmentation. Detection of Discontinuities, Thresholding Pixel based segmentation method. Region based segmentation methods – segmentation by pixel aggregation, segmentation by sub region aggregation, histogram based segmentation, spilt and merge technique. Use of motion in segmentation (spatial domain technique only)
7. Morphology:-
Dilation, Erosion, Opening, closing, Hit-and-Miss transform, Boundary extraction,
Region filling, connected components, thinning, Thickening, skeletons , Pruning
Extensions to Gray – Scale Images Application of Morphology in I.P
Text Book:
Digital Image Processing , Rafael C. Gonzalez and Richard E. Woods, Addision Wesley
Reference books:
1. Fundamentals of Electronic Image Processing ,Arthur .R. Weeks, Jr. (PHI)
2. Image processing, Analysis, and Machine vision, Milan Sonka , Vaclav Hlavac, Roger Boyle, Vikas Publishing House.
CSE 3.2.5 ELECTIVE-II V H D L Credits:4
Instruction: 3 Periods & 1 Tut. /Week Sessional Marks: 30
Univ.-Exam : 3 Hours Univ-Exam-Marks:70
1. Overview of Digital Design with Vermilion HDL
2. Hierarchical Modeling Concepts
3. Basic Concepts
4. Modules and ports
5. Gate-Level Modeling
6. Dataflow Modeling
7. Behaviour Modeling
8. Tasks and Functions
Text Book:
1. Verilog HDL – A Guide to Digital Design and Synthesis, Samir Palnitkar, Pearson
Education Pte. Ltd. (chapters: 1,2,3,4,5,6,7,8), 2001
Reference Books:
1. Fundamentals of Digital Logic with Verilog Design, Stephen Brown and Zvonko Vranesic, Tata - McgrawHill, 2002
2. A Verilog HDL Primer, J. Bhasker, Second Edition, Star galaxy Pub., 1999
CSE 3.2.5 ELECTIVE-II WEB TECHNOLOGIES Credits:4
Instruction: 3 Periods & 1 Tut. /Week Sessional Marks: 30
Univ.-Exam : 3 Hours Univ-Exam-Marks:70
HTML Common tags- List, Tables, images, forms, Frames; Cascading Style sheets;
Java Script: - Introduction to Java Scripts, Objects in Java Script, Dynamic HTML with Java Script
XML: Document type definition, XML Schemas, Document Object model, Presenting XML, Using XML Processors: DOM and SAX
Java Beans: Introduction to Java Beans, Advantages of Java Beans, BDK, Introspection, Using Bound properties, Bean Info Interface, Constrained properties Persistence, Customizes, Java Beans API, Introduction to EJB’s
Web Servers and Servlets: Tomcat web server, Introduction to Servelets: Lifecycle of a Serverlet, The Servelet API, The javax.servelet Package, Reading Servelet parameters, Reading Initialization parameters. The javax.servelet HTTP package, Handling Http Request & Responses, Using Cookies-Session Tracking, Security Issues,
JSP Application Development: Generating Dynamic Content, Using Scripting Elements Implicit JSP Objects, Conditional Processing – Displaying Values Using an Expression to Set an Attribute, Declaring Variables and Methods Error Handling and Debugging Sharing Data Between JSP pages, Requests, and Users Passing Control and Date between Pages – Sharing Session and Application Data – Memory Usage Considerations
Database Access: Database Programming using JDBC, Studying Javax.sql.* package,Accessing a Database from Servlets & JSP Page , Application – Specific Database Actions,Deploying JAVA Beans in a JSP Page, Introduction to struts framework.
TEXT BOOKS:
1. Internet and World Wide Web – How to program by Dietel and Nieto PHI/Pearson Education Asia.
2. Advanced Java™ 2 Platform How to Program, Deitel/Deitel/Santry
3. Java Server Pages –Hans Bergsten, SPD O’Reilly
REFERENCE:
1. HTML Black Book: The Programmer's Complete HTML Reference Book-by Steven Holzner
2. Core SERVLETS ANDJAVASERVER PAGES VOLUME 2: CORE TECHNOLOGIES by Marty Hall and
Larry Brown Pearson
CSE 3.2.6 COMPUTER ARCHITECTURE Credits:4
Instruction: 3 Periods & 1Tut/Week Sessional Marks: 30
Univ_Exam:3 Hours Univ_ Exam Marks:70
Computer Evolution, Computational Models The Concept of Computer Architecture Introduction to Parallel Processing
Introduction to Instruction-Level Parallel Processors
Pipelined Processors VLIW Architectures Superscalar Processors
Processing of Control Transfer Instructions Code Scheduling of ILP-Processors Introduction to Data-Parallel Architectures Introduction to MIMD Architectures
Text Books:
1.Dezso Sima, Terence Fountain, Peter Kacsuk, Advanced Computer Architectures: A Design Space
Approach, Pearson Education Inc., 1997.
2. J. L. Hennessy and D. A. Patterson, Computer Architecture: A Quantitative Approach,
3rd Edition, Morgan Kaufmann Publishing Co., 2002.
Reference Text
1. William Stalling, Computer Organization & Architecture: Designing for Performance,
6th Edition, PHI, 2003.
2. Kai Hwang, Advanced Computer Architecture: Parallelism, Scalability, Programmability, TMH, 2001
CSE 3.2.7 MICROPROCESSOR-II LAB Credits:2
Lab: 3 Periods/week Sessional Marks: 50
Univ-Exam : 3 Hours Univ-Exam-Marks: 50
INTERFACING WITH 8085 TRAINER
1.1 MEMORY INTERFACE (Interfacing SRAM and EPROM)
1.2 TOGGLE SWITCH KEYBOARD AND LED DISPLAY INTERFACE
1.3 HEX KEYBOARD AND DOT MATRIX HEX LED DISPLAY INTERFACE
1.4 ASCII KEYBOARD INTERFACE
1.5 PUSH BUTTON KEYBOARD MATRIX (8x3) INTERFACE WITH 8085 ICE
1.6 8279-PROGRAMMABLE KEYBOARD/DISPLAY INTERFACE
1.7 CRT TERMINAL INTERFACE
INTERFACING WITH PC
2.1 STEEPER MOTOR CONTROLLER
2.2 DAC/ADC INTERFACE
2.3 8253 TIMER INTERFACE
2.4 MULTIPLEXED DOT MATRIX HEX LEDs INTERFACE
2.5 40-COL./80COL. D.M. PRINTER INTERFACE
2.6 8051 PROGRAMMING EXERCISES
2.7 TRAFFIC LIGHT CONTROLLER INTERFACE
CSE 3.2.8 DBMS LAB Credits:2
Lab: 3 Periods/week Sessional Marks: 50
Univ-Exam : 3 Hours Univ-Exam-Marks: 50
Study features of a commercial RDBMS package such as ORACLE/DB2, MS Access, MYSQL & Structured
Query Language (SQL) used with the RDBMS.( Select two of RDMSs)
Laboratory exercises should include defining schemas for applications, creation of a database, writing SQL queries, to retrieve information from the database, use of host languages, interface with the embedded SQL, use of forms & report writing packages available with the chosen RDBMS product.
Some sample applications, which may be programmed, are given below: Accounting package for a shop,
Database manager for a Magazine agency or a newspaper agency, Ticket booking for performances,
Preparing greeting cards & birthday cards,
Personal accounts - Insurance, loans, mortgage payments, etc., Doctor's diary & billing system,
Personal bank account, Class marks management, Hostel accounting,
Video Tape library, History of cricket scores,
Cable TV transmission program manager, Personal library.
