# BPUT B.Tech 4th Semester Information Technology Syllabus

**Information Technology**

**Discrete Mathematics**

**Module- I (14 Hours)**

Propositional logic, Propositional Equivalence, Predicates and Quantifiers, Nested Quantifiers, Rules of Inference, Proof methods and Strategies, Sequences and Summations, Mathematical Induction, Recursive definition and structural induction, Program Correction

Recurrence relation, Solution to recurrence relation, Generating functions, Inclusion and exclusion, Application of Inclusion and Exclusion Principle, Relation and their properties, Closure of relations, Equivalence relations, Partial orderings.

*Module-II (13 hours)*

Introduction to graph theory, Graph terminology, Representation of graphs, Isomorphism, Connectivity, Euler and Hamiltonian paths, Shortest path problems, Planar graph, Graph coloring, Introduction to trees, Application of trees, Tree Traversal, Minimum Spanning tree.

*Module-III (13 hours)*

Semi groups, Monoids, Groups, Subgrorups, Cosets, Lagrange theorem, Permuation groups, Group codes, isomorphism, Homomorphisms, Normal subgroups, Rings, Integral Domain and Fields.

Algebraic systems, Lattices, Distributive and Complemented Lattices, Boolean Lattices and Boolean Algrebra, Boolean Functions and Boolean Expressions.

**Text Books:**

**Kenneth H. Rosen**, “*Discrete Mathematics and its Applications*”, Sixth Edition, 2008, Tata McGraw Hill Education , New Delhi. Chapters: 1, 2(2.4), 4, 6(6.1, 6.2, 6.4-6.6), 7, 8, 9

**L. Liu and D. Mohaptra**, “*Elements of Discrete Mathematics*”, Third Edition, 2008, Tata McGraw Hill Education, New Delhi Chapters: 10 (10.1- 10.10), 11(11.1 – 11.7)

**Reference Books:**

- Ralph P. Grimaldi, ”Discrete and Combinatorial Mathematics”, Fifth Edition, 2005, Pearon Education, New Delhi.
- Kolman, Busby, Ross, “Discrete Mathematics”, Fifth Edition, PHI Publication.
- L. Gersting, “ Mathematical Structure for Computer Science: A modern treatment to Discrete Mathematics’ Sixth Edition, W. H. Freeman and Macmillan (India).
- Eric Gossett, ‘ Discrete Mathematics with Proof, Second Edition, Wiley India Pvt Ltd
- Thomas Koshy, “ Discrete Mathematics and Applications:, Second Edition, Elsevier Publication (India), New Delhi.
- L. Mott, A.Candell & I. Bekar, Discrete Mathematics for Computer Scientists and Mathematicians, PHI.

**System Programming**

**Module I** **(10 Hrs)**

Introduction: System Software, Application Software, Machine Structure, Evolution of components of a programming system (Assembler, Loader, Macros, Compiler, Formal Systems), Evolution of Operating Systems, Functions of Operating System.

Machine Structure: General Machine Structure, Approach to a new machine, Memory Registers, Data, Instructions, special features.

Machine Language: Long Way, No looping, Address Modification, Looping Introduction to Assembly Language Program

**Module II** **(10 Hrs)**

Assemblers: Design Procedure, Design of Assembler, Table Processing.

Macros Language and Macro Processor: Macro Instructions, Features of a Macro Facility, Implementation.

Loaders: Loader Schemes, Design of an Absolute Loader, Direct Linking loader, Bootstrap Loader.

**Module III** **(12 Hrs)**

Programming Languages: Importance of High Level Languages, Features, Data Types and Data Structures, Storage Allocation and Scope Name, Accessing Flexibility, Functional Modularity, Asynchronous Operations, Extensibility and Compile time Macros.

Formal Systems: Uses of Formal Systems, Formal Specification, Formal Grammars, Backus-Naur Form, Canonic Systems, Canonic Systems vs Formal Systems

Compilers: Introduction to Compilers, Phases of a compiler(Lexical Phase, Syntax Phase, Interpretation Phase, Optimization, Code Generation, Assembly, passes of a compiler), Intermediate Form, Storage Allocation, Code Generation, Data Structure

**Text Book:**

Systems Programming by John J Donovan (McGraw-Hill Education)

**Reference Book:**

- System Software: An Introduction to systems programming by Leland Beck (Pearson)
- System Software : Nityashri,( McGraw-Hill Education)
- Operating System and System Programming – Dhamdhere ( McGraw-Hill Education)
- System Programming with C and Unix.- Hoover (Pearson Education)

**Design and Analysis of Algorithm**

**Module- I** **(12 Hours)**

Introduction to design and analysis of algorithms, Growth of Functions (Asymptotic notations, standard notations and common functions), Recurrences, solution of recurrences by substitution, recursion tree and Master methods, worst case analysis of Merge sort, Quick sort and Binary search, Design & Analysis of Divide and conquer algorithms.

Heapsort : Heaps, Building a heap, The heapsort algorithm, Priority Queue, Lower bounds for sorting.

**Module – II** **(16 Hours)**

Dynamic programming algorithms (Matrix-chain multiplication, Elements of dynamic programming, Longest common subsequence)

Greedy Algorithms – (Assembly-line scheduling, Achivity- selection Problem, Elements of Greedy strategy, Fractional knapsac problem, Huffman codes).

Data structure for disjoint sets:- Disjoint set operations, Linked list representation, Disjoint set forests.

**Module – III** **(12 Hours)**

Graph Algorithms: Breadth first and depth-first search, Minimum Spanning Trees, Kruskal and Prim’s algorithms, single- source shortest paths (Bellman-ford and Dijkstra’s algorithms), All-pairs shortest paths (Floyd – Warshall Algorithm). Back tracking, Branch and Bound.

Fast Fourier Transform, string matching (Rabin-Karp algorithm), NP – Completeness (Polynomial time, Polynomial time verification, NP – Completeness and reducibility, NP-Complete problems (without Proofs), Approximation algorithms (Vertex-Cover Problem, Traveling Salesman Problem).

**Text Book:**

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C.Stein : Introduction to algorithms -2nd edition, PHI,2002. Chapters: 1,2,3,4 (excluding 4.4), 6, 7, (7.4.1), 8 (8.1) 15 (15.1 to 15.4), 16 (16.1, 16.2, 16.3), 21 (21.1,21.2,21.3), 22(22.2,22.3), 23, 24(24.1,24.2,24.3), 25 (25.2), 30,32 (32.1, 32.2) 34, 35(35.1, 35.2)

**Reference Books:**

- Algorithms – Berman, Cengage Learning
- Computer Algorithms: Introduction to Design & Analysis, 3
^{rd}edition-by Sara Baase, - Fundamentals of Algorithm-by Horowitz & Sahani, 2
^{nd}Edition, Universities Press. - Algorithms By Sanjay Dasgupta, Umesh Vazirani – McGraw-Hill Education
- Algorithm Design – Goodrich, Tamassia, Wiley India.

**Database Engineering**

__Module1:__**(12 Hrs)**

Introduction to database Systems, Basic concepts &Definitions, Data Dictionary, DBA, File-oriented system vs. Database System, Database Language.

Database System Architecture-Schemas, Sub Schemas & Instances, 3-level database architecture, Data Abstraction, Data Independence, Mappings, Structure, Components & functions of DBMS, Data models, Mapping E-R model to Relational, Network and Object Oriented Data models, types of Database systems,

Storage Strategies**:** Detailed Storage Architecture, Storing Data, Magnetic Disk, RAID, Other Disks, Magnetic Tape, Storage Access, File & Record Organization, File Organizations & Indexes, Order Indices, B+ Tree Index Files, Hashing

**Module 2:** **(16 Hrs)**

Relational Algebra, Tuple & Domain Relational Calculus, Relational Query Languages: SQL and QBE.

Database Design :-Database development life cycle(DDLC),Automated design tools, Functional dependency and Decomposition, Dependency Preservation & lossless Design, Normalization, Normal forms:1NF, 2NF,3NF,and BCNF, Multi-valued Dependencies, 4NF & 5NF.

Query processing and optimization: Evaluation of Relational Algebra Expressions, Query optimization.

**Module 3: (12 Hrs) **

Transaction processing and concurrency control: Transaction concepts, concurrency control, locking and Timestamp methods for concurrency control.

Database Recovery System: Types of Data Base failure & Types of Database Recovery, Recovery techniques

Advanced topics: Object-Oriented & Object – Relational Database, Parallel & Distributed Database, Introduction to Data warehousing & Data Mining.

__Text Books:__

- Database System Concepts by Sudarshan, Korth (McGraw-Hill Education)
- Fundamentals of Database System By Elmasari &Navathe- Pearson Education

__References Books:__

- An introduction to Database System – Bipin Desai, Galgotia Publications
- Database System: concept, Design & Application by S.K.Singh (Pearson Education)
- Database management system by leon &leon (Vikas publishing House).
- Database Modeling and Design: Logical Design by Toby J. Teorey, Sam S. Lightstone, and Tom Nadeau, “”, 4
^{th}Edition, 2005, Elsevier India Publications, New Delhi - Fundamentals of Database Management System – Gillenson, Wiley India

**Digital Electronics Circuit**

**MODULE – I** **(11 Hours)**

**Number System:**Introduction to Binary Numbers, Data Representation, Binary, Octal, Hexadecimal and Decimal Number System and their Conversion. (2 Hours)

**Boolean Algebra and Logic Gates:**Basic Logic Operation and Identities, Algebraic Laws, NOR and NAND Gates, Useful Boolean Identities, Algebraic Reduction, Complete Logic Sets, Arithmetic Operation using 1’s and 2`s Compliments, Signed Binary and Floating Point Number Representation. (4 Hours)

**Combinational Logic Design:**Specifying the Problem, Canonical Logic Forms, Extracting Canonical Forms, EX-OR Equivalence Operations, Logic Array, K-Maps: Two, Three and Four variable K-maps, NAND and NOR Logic Implementations. (5 Hours)

**MODULE – II ****(15 Hours)**

**Concepts in VHDL:**Basic Concepts, Using a Hardware Description Language, Defining Module in VHDL, Structural and Combinational Modelling, Binary Words, Libraries, Learning VHDL. (4 Hours)

**CMOS Logic Circuits:**Voltages as Logic Variables, Logic Delay Times: Output Switching Times, Propagation Delay, Fan-In and Fan-out, Extension to other Logic Gate. C-MOS Electronics, MOSFETS, The NOT Function in C-MOS: Complimentary Pairs and the C-MOS Invertors, Logic Formation Using MOSFETS: the NAND and NOR Gate, C-MOS Logic Connection, Complex Logic Gates in C-MOS: 3-input Logic Gates, A general 4-input Logic Gate, Logic Cascades. (6 Hours)

**Introduction to VLSI:**Introduction, Lithography and Patterning, MOSFET Design Rules, Basic Circuit Layout, MOSFET Arrays and AOI Gates, Cells, Libraries, and Hierarchical Design, Floor Plans & Interconnect Wiring. (5 Hours)

**MODULE – III ****(16 hours)**

**Logic Components:**Concept of Digital Components, An Equality Detector, Line Decoder, Multiplexers and De-multiplexers, Binary Adders, Subtraction and Multiplication. (5 Hours)

**Memory Elements and Arrays:**General Properties, Latches, Clock and Synchronization, Master-Slave and Edge-triggered Flip-flops, Registers, RAM and ROMs, C-MOS Memories. (6 Hours)**Sequential Network:**Concepts of Sequential Networks, Analysis of Sequential Networks: Single State and Multivariable Networks, Sequential Network Design, Binary Counters, Importance of state machine. (5 Hours)

__Text Books:__

- A First Course in Digital System Design: An Integrated Approach, India Edition, John P. Uyemura, PWS Publishing Company, a division of Thomson Learning Inc.
- Digital Systems – Principles and Applications, 10
^{th}Edition, Ronald J. Tocci, Neal S. Widemer and Gregory L. Moss, Pearson Education. - Digital Design, Robert K. Dueck, CENGAGE Learning
**.**

**Reference Books:**

- Digital Principles and Applications, 6
^{th}Edition, Donald P. Leach, Albert Paul Malvino and Goutam Saha, Tata McGraw Hill Publishing Company Ltd., New Delhi. - Digital Fundamentals, 5
^{th}Edition, T.L. Floyd and R.P. Jain, Pearson Education, New Delhi. - Digital Electronics, Principles and Integrated Circuit, Anil K. Jain, Wiley India Edition.
- Digital Design, 3
^{rd}Edition, Moris M. Mano, Pearson Education.

**Digital Electronics Circuit Lab**

__List of Experiments:__

*(Atleast 10 experiments should be done, Experiment No. 1 and 2 are compulsory and out of the balance 8 experiments atleast 3 experiments has to be implemented through both Verilog/VHDL and hardware implementation as per choice of the student totaling to 6 and the rest 2 can be either through Verilog/VHDL or hardware implementation.)*

- Digital Logic Gates: Investigate logic behavior of AND, OR, NAND, NOR, EX-OR, EX-NOR, Invert and Buffer gates, use of Universal NAND Gate.
- Gate-level minimization: Two level and multi level implementation of Boolean functions.
- Combinational Circuits: design, assemble and test: adders and subtractors, code converters, gray code to binary and 7 segment display.
- Design, implement and test a given design example with (i) NAND Gates only (ii) NOR Gates only and (iii) using minimum number of Gates.
- Design with multiplexers and de-multiplexers.
- Flip-Flop: assemble, test and investigate operation of SR, D & J-K flip-flops.
- Shift Registers: Design and investigate the operation of all types of shift registers with parallel load.
- Counters: Design, assemble and test various ripple and synchronous counters – decimal counter, Binary counter with parallel load.
- Memory Unit: Investigate the behaviour of RAM unit and its storage capacity – 16 X 4 RAM: testing, simulating and memory expansion.
- Clock-pulse generator: design, implement and test.
- Parallel adder and accumulator: design, implement and test.
- Binary Multiplier: design and implement a circuit that multiplies 4-bit unsigned numbers to produce a 8-bit product.
- Verilog/VHDL simulation and implementation of Experiments listed at Sl. No. 3 to 12.

**Design and Analysis of Algorithms Lab**

- Using a stack of characters, convert an infix string to postfix string.(1 class)
- Implement insertion, deletion, searching of a BST. (1 class)
- (a) Implement binary search and linear search in a program

- Implement a heap sort using a max heap.

- (a) Implement DFS/ BFS for a connected graph.

- Implement Dijkstra’s shortest path algorithm using BFS.

- (a) Write a program to implement Huffman’s algorithm.

- Implement MST using Kruskal/Prim algorithm.

- (a) Write a program on Quick sort algorithm.

- Write a program on merge sort algorithm.

- Implement Strassen’s matrix multiplication algorithm.
- Write down a program to find out a solution for 0 / 1 Knapsack problem.
- Using dynamic programming implement LCS.
- (a) Find out the solution to the N-Queen problem.

- Implement back tracking using game trees.

**Database Engg. Lab**

- Use of SQL syntax: insertion, deletion, join, updation using SQL. (1 class)
- Programs on join statements and SQL queries including where clause. (1 class)
- Programs on procedures and functions. (1 class)
- Programs on database triggers. (1 class)
- Programs on packages. (1 class)
- Programs on data recovery using check point technique. (1 class)
- Concurrency control problem using lock operations. (1 class)
- Programs on ODBC using either VB or VC++. (1 class)
- Programs on JDBC. (1 class)
- Programs on embedded SQL using C / C++ as host language. (1 class)

Get the eBooks for information technology from Kopykitab.

## Recent Comments