## BE Bachelor of Engineering Information Technology 4th Sem

*RTM Nagpur BE 4th Sem Information Technology Syllabus Classes Course for RTM Nagpur University*

Atlanta Computer Institute Nagpur conducts Tuition Classes Of Information technology for BE First Year , Second Year and BE Final Year for all universities in India . The Following syllabus is of RTM Nagpur University. Final Year Projects Training is also given to BE Students.

Subjects

## DISCRETE MATHEMATICS AND GRAPH THEORY

ALGORITHMS AND DATA STRUCTURES

THEORY OF COMPUTATION

COMPUTER ARCHITECTURE AND ORGANIZATION

OBJECT ORIENTED METHODOLOGY

Syllabus for

SYLLABUS FOR

## DISCRETE MATHEMATICS AND GRAPH THEORY

BE IV Semester (CS/CT/CE/IT)

Scheme (Theory: 4 hrs. & Tutorial:1 hr.)

UNIT-I: Mathematical Logic and Set Theory (08 Hrs)

Propositions and Logical Operations, Quantifiers, Conditional Statements and

Tautologies, Methods of Proof, Principle of Mathematical Induction. Basic

concepts of set theory, Operations on Sets, The power set.

UNIT-II: Relations and Functions(12 Hrs)

Relations: Ordered pairs and n-tuples, Product Sets and Partitions, Relations

and Digraphs, Matrix of Relation, Paths in Relations and Digraphs, Properties

of Relations, Equivalence Relations & Partitions, Compatible Relation,

Manipulation of Relations, Composition of Relations, Transitive Closure of a

relation, Partial order relation, Partially ordered set, Hasse Diagrams.

Functions: Definition, Composition of functions, Types of Functions, Invertible

Function, Permutation Function, Characteristics function of a set with

Theorems.

UNIT-III: Group Theory (12 Hrs)

Binary Operations, Properties, Semigroups,

Monoids,Subsemigroup,Submonoid, Isomorphism & Homomorphism, ,

Groups(only definitions and examples) Subgroups and Homomorphism, Cosets

and Lagrange’s Theorem, Normal subgroups.

Unit-IV:Rings, Lattices & Boolean Algebra(10 Hrs)

Rings, Fields, Integral Domain, Ring Homomorphism (definitions &

examples), Lattices: Properties, Types of Lattices, Sub lattices, Isomorphic

Lattices, Complemented & Modular Lattices (definitions & examples), Boolean

Algebra: Definition, Properties, Simplification of Switching Circuits.

Unit-V: Graph Theory (12 Hrs)

Basic concepts of Graph Theory, Digraphs, Basic definitions, Paths and

Circuits, Reachability and Connectedness, Matrix representation of graphs,

Subgraphs & Quotient Graphs, Isomorphic digraphs & Transitive Closure

digraph, Euler’s Path & Circuit (only definitions and examples). Trees, Binary

Tree, Labeled Trees, Undirected Trees, Spanning Trees of Connected Relations,

Prim’s Algorithm to construct Spanning Trees, Weighted Graphs, Minimal

Spanning Trees by Prim’s Algorithm & Kruskal’s Algorithm.

Unit-VI: Combinatorics(06Hrs)

Generating Functions, Recurrence Relations, Counting: Permutations &

Combinations, Pigeonhole Principle with Simple Applications.

Text Books

rd

1.

Discrete Mathematical Structures(3Edition) by Kolman, Busby & Ross

PHI.

2.

Discrete Mathematical Structures with Applications to Computer Science

byTremblay &Manohar, Tata McGraw-Hill.

3.

Combinatorial Mathematics, C.L.Liu (McGraw Hill)

Reference Books

1.

Discrete Maths for Computer Scientists & Mathematicians by Mott,

Kandel, Baker.

2.

Elements of Discrete Mathematics by C. L. Liu.

3.

Discrete Mathematics by Lipschutz.

4.

Discrete Mathematics by R.Johnsonbaugh.

th

5.

Higher Engineering Mathematics by B.S. Grewal, 40Edition, Khanna

Publication

.

BEIT402T

## ALGORITHMS AND DATA STRUCTURES

(Theory Credit: 05)

Teaching Scheme: Examination Scheme:

Lecture: 4 Hours/week Theory: T (U): 80 Marks T (I): 20 Marks

Tutorial: 1 Hour/week Duration of University Exam. : 03 Hours

===================================================

=

UNIT I:

An Introduction to data structure: Introduction, Definition, Classification of data

structure, Concept of data, Data types, Abstract data Types (ADT), Features of

structured program. Introduction to algorithms: Definition and Characteristics of an

Algorithm, Apriori analysis, Time and space complexity, Average , Best and Worst case

complexities, Big „O. Notations, Asymptotic notations, Top-Down and bottom-up

programming techniques, Recursion, Divide and conquer strategy. ( e.g. Quick sort,

Tower of Hanoi)

.

UNIT II:

Stacks and Queue: Definition and Terminology, Concept of stack, Stack

implementation, Operation on stack, Algorithms for push and pop, Implementing stack

using pointers, Application of stacks, Evaluation of polish notation, multiple stack.

Queue: Queue as ADT Implementation of queue, Operation on queue, Limitations,

Circular queue, Double ended queue (dequeue), Priority queue, Application of queues,

multiple queues.

UNIT III:

Linked List : Introduction, Linked list, Representation of linear linked list, Operation on

linked list, Types of linked list, Singly linked list, Circular linked list, Doubly linked list,

Circular doubly linked list, Application: Addition of Two polynomials, Generalized linked

list, Sparse matrix.

UNIT IV:

Tree: Introduction to Non Linear Data Structures, Binary tree Concept and terminology,

Representation of binary trees, Algorithm for tree traversals (recursive and non

recursive). Conversion of general tree to binary tree (Implementation not expected)

.

Binary search trees, Extended binary tree, Threaded binary tree. Height balanced and

weight balanced binary trees, B-Tree, B+ Tree, AVL tree, Multiway tree, 2-3 Tree.

UNIT V:

Graphs: Concepts and terminology, Representation of graphs using adjacency matrix,

adjacency list, Depth First search and Breadth First Search Algorithms, Spanning trees,

Minimal cost spanning tree and Shortest path algorithm ( Single Source-all pairs)

.

UNIT VI:

Searching and sorting Techniques: Importance of searching. Sequential, Binary,

Sorting : Bubble sort, selection sort, quick sort, Merge sort, heap sort, Shell sort,

Analysis of these algorithms in worst and average cases. Hashing techniques and

collision handing mechanism.

Text Books:

1. Data Structures with C by SEYMOUR LIPSCHUTZ [TMH].

2. Data Structure using C by ISRD Group [TMH].

3. Data Structure through C by G. S. BALUJA [Dhanpat Rai & co.].

4. Introduction to Data Structure in C by Ashok N. Kamthane [Pearson].

5. Data structures using C and C++ by Tenenbaum [Pearson].

6. Data structures Pseudocode with C by Gilberg/Foruzen, Cengage Learning

*****

BEIT402P ALGORITHMS AND DATA STRUCTURES

(Practical Credit: 01)

Teaching Scheme: Examination Scheme:

Practical: 2 Hours/week Practical: P (U): 25 Marks P (I): 25 Marks

Duration of University Exam. : 02 Hours

====================================================

Note:

1.

Practicals are based on ALGORITHMS AND DATA STRCUTURES syllabus

(subject code: BEIT402T)

2.

Practicals have to be performed using „C.

language

3.

There should be at the most two practicals per unit

4.

Minimum ten practicals have to be performed

5.

Do not include study experiments

******

BEIT403T

## THEORY OF COMPUTATION

(Theory Credit: 05)

Teaching Scheme: Examination Scheme:

Lecture: 4 Hours/week Theory: T (U): 80 Marks T (I): 20 Marks

Tutorial: 1 Hour/week Duration of University Exam. : 03 Hours

===================================================

=

UNIT I:

Strings, Alphabet, Language operations, Finite state machine definitions, Finite

automation model, Acceptance of strings and language, Non deterministic finite

automation, Deterministic finite automation, Equivalence between NFA and DFA,

Conversion of NFA into DFA, Minimization of FSM, Equivalence between two FSM.s Moore

and Mealy machines

UNIT II:

Regular sets, Regular expressions, Identity rules, Manipulation rules, Manipulation of

regular expressions, Equivalence between RE and FA, Inter conversion, Pumping lemma,

Closure properties of regular sets(proofs not required), Chomsky hierarchy of languages,

Regular grammars, Right linear and left linear grammars, Equivalence between regular

linear programming and FA, Inter conversion between RE and RG.

UNIT III:

Context free grammar, Derivation trees, Chomsky normal form, Greibach normal form,

Push down automata, Definition, Model acceptance of CFL, Equivalence of CFL and PDA,

Inter conversion, Closure properties of CFL(Proofs omitted),Pumping Lemma of CFL,

Introduction of DCFL and DPDA

UNIT IV:

Turing Machine: Definition, Model of TM, Design of TM, Universal Turing Machine,

Computable function, Recursive enumerable language, Types of TM.s (proofs not

required), Linear bounded automata and Context sensitive language, Counter machine

UNIT V:

Decidability and Undecidability of problems, Properties of recursive & recursively

enumerable languages, Halting problems, Post correspondence problem, Ackerman

function, and Church.s hypothesis.

UNIT VI:

Recursive Function: Basic functions and operations on them, Bounded Minimalization,

Primitive recursive function, µ-recursive function, Primitive recursive predicates, Mod and

Div functions, Unbounded Minimalization, Equivalence of Turing Computable function and

µ-recursive function.

Text Books:

1.

Introduction to Automata Theory, Languages and Computation by J. E.

Hopcraft,R. Motwani, J. D Ullman, second Edition, Pearson Education, Aisa

2.

An Introduction to Formal Languages and Automata by Peter Linz

3.

Introduction to Langauges and the theory of Automata by John Martin, Third

Edition(TMH)

Reference Books:

1.

Theory of Computer Science, Automata, Languages and Computation by K. L. P.

Mishra and N. Chandrasekaran, Third Edition, PHI Learning.

2.

Elements of Theory of Computation by Lewis H.P and Papadimition C.H.

*****

BEIT404T

## COMPUTER ARCHITECTURE AND ORGANIZATION

(Theory Credit: 05)

Teaching Scheme: Examination Scheme:

Lecture: 4 Hours/week Theory: T (U): 80 Marks T (I): 20 Marks

Tutorial: 1 Hour/week Duration of University Exam. : 03 Hours

===================================================

=

UNIT I:

Basic Structure of Computers:

Functional Units, Basic Operational Concepts, Bus Structures, Software, Multiprocessors

and Multicomputers.

Machine Instructions:

Memory Locations and Addresses, Memory Operations, Machine program sequencing,

addressing modes and encoding of information, Assembly Language ,Stacks, Queues and

Subroutine.

UNIT II:

Instruction Sets:

Instruction Format, limitations of Short word-length machines, High level language

Considerations, Motorola 68000 architecture.

Processing Unit:

Some fundamental concepts, Execution of a complete instruction, Single, two, three bus

organization, Sequencing of control Signals.

UNIT III:

Micro-programmed Control:

Microinstructions, grouping of control signals, Micro program sequencing, Micro

Instructions with next Address field, Perfecting microinstruction, Emulation, Bit Slices,

Introduction to Microprogramming, Macro Processor.

UNIT IV:

Arithmetic: Number Representation, Addition of Positive numbers, Logic Design for fast

adders, Addition and Subtraction, Arithmetic and Branching conditions, Multiplications of

positive numbers, Signed Operand multiplication, fast Multiplication, Booth.s Algorithm,

Integer Division, Floating point numbers and operations.

UNIT V:

The Memory System:

Some Basic Concepts, Semiconductor RAM Memories, Memory system considerations,

Semiconductor ROM Memories, Memory interleaving, Cache Memory, Mapping

techniques, Virtual memory, Memory Management requirements.

UNIT VI:

Computer Peripherals:

I/O Devices, DMA, Interrupt handling, online storage, File services.

Processors:

Families of microprocessors Chips, Introduction to RISC & CISC Processors, Introduction

to Pipelining.

Text Books:

1.

Computer Organization 4 th Edition, 2001 V. Carl Hamacher Mc GrawHill.

2.

Computer Organization and Design (The Hardware/Software Interfaces) 4th

Edition David A. Patterson & John L. Hennessy Morgan Kaufmann.

*****

BEIT405T

## OBJECT ORIENTED METHODOLOGY

(Theory Credit: 05)

Teaching Scheme: Examination Scheme:

Lecture: 4 Hours/week Theory: T (U): 80 Marks T (I): 20 Marks

Tutorial: 1 Hour/week Duration of University Exam. : 03 Hours

===================================================

=

UNIT I:

Introduction object-oriented development,Object Oriented Methodology, three Models,

object oriented terms, object modeling Technique, object and classes links and

associations, generalization and inheritance, grouping constructs a sample object

module. Advanced object modeling; aggregation abstract classes, multiple, inheritance,

metadata, candidate keys.

UNIT II:

Dynamic modeling, events and states, nested state diagrams, concurrency, advanced

dynamic modeling concepts, functional models, data flow diagram, constraints, a sample

functional module

UNIT III:

Design methodology overview of analysis, problem statement, ATM network, object

modeling, various phases, dynamic modeling, various phases

UNIT IV:

System design, overview, sub systems, allocating subsystems, management of data

stores, choosing software control, implementation, handling boundary condition

UNIT V:

Object design, overview, designing algorithms, design optimization, optimization of

control, adjustment of inheritance, design of associations, object representation, physical

packaging,

UNIT VI:

Implementation, programming languages, database systems, object oriented style,

reusability, extensibility, robustness.

Text Books:

1.

Object Oriented Modeling and Design by James Rumbaugh, Michal Blaba, William

Premerlani, Frederic Eddy, William Lorerson, PHI, 1997

2.

Object –oriented Programing Using C++ and Java by Ramesh Vasappanavar,

Anand Vasappanavar , Gautam Vasappanavar, PEARSON, 2011

Reference Books:

1.

Mastering C++ by A.R.Venugopal, Rajkumar, T. Ravishanker ,TMH, 1997.

2.

Computer Science A Structured Approach Using C++ by Behrouz A. Forouzan ,

Richard F. Gilberg, Second Edition, CENGAGE Learning.

3. Object Oriented Programming with C++ by E Balagurusamy, Fifth Edition, TMH.

*****

BEIT405P OBJECT ORIENTED METHODOLOGY

(Practical Credit: 01)

Teaching Scheme: Examination Scheme:

Practical: 2 Hours/week Practical: P (U): 25 Marks P (I): 25 Marks

Duration of University Exam. : 02 Hours

====================================================

Note:

1.

Practicals are based on OBJECT ORIENTED METHODOLOGY syllabus

(subject code: BEIT405T)

2.

Practicals have to be performed using „C++

.

language

3.

There should be at the most two practicals per unit

4.

Minimum ten practicals have to be performed

5.

Do not include study experiments

*****

BEIT406P

Teaching Scheme:

Practical: 2 Hours/week

COMPUTER LAB-II

(Practical Credit: 02)

Examination Scheme:

Practical: P (U): 25 Marks P (I): 25 Marks

Duration of University Exam. : 02 Hours

====================================================

G-01.

Experiment based on MS Office macro programming.

G-02.

Installation of OS and Configuring a Desktop for– the Windows Operating System

(XP and 7) and the Linux Operating System (Ubuntu/Fedora/Mint).

G-03.

Introduction to UNIX Operating System, The UNIX architecture and Command

Usage, The File System, PIPES, Filters using Regular Expressions.

G-04.

Introduction to Linux Operating System, flavors of Linux vi Editor, vim Editor

G-05.

The Shell -Shell Variables; Scripts; Meta Characters and Environment; if and

case Statements; for, while and until loops; Essential Shell Programming.

G-06.

AWK (The Pattern-Action Language) -BEGIN and END Patterns; Variables,

Records and Fields; Loops; Handling Text; String Manipulations.

G-07.

Introduction to MATLAB Simulator and Programming based on MATLAB Simulator.

Note:

1.

Practical sessions based on Any Four/Five groups from G-01 to G-06 may be

planned.

2.

Practical Group G-07 is compulsory.

Reference Books:

1.

Sumitabha Das, “UNIX – Concepts and Applications”, Fourth Edition, Tata McGraw

Hill, 2006.

2.

Behrouz A. Forouzan and Richard F. Goldberg, “UNIX and Shell Programming”,

Thomson Publishing, 2005.

3.

Guide to Unix and Linux by Harley Hahn.s 1st edition, TMH publication, 2011.

4.

Microsoft Office Programming: A Guide for Experienced Developers by Rod

Stephens, Apress,2003

5.

Dale Dougherty and Arnold Robbins, “sed and awk”, Second Edition, O.Reilly

Media, 1997

6.

“A concise Introduction to MATLAB”, by William J. Palm III, First Edition, Tata

McGraw Hill.

7.

“MATLAB and Simulink for Engineers” by Agam Kumar Tyagi, Oxford University

Press.

8. “MATLAB for Engineers”, by Holly Moore, Prentice Hall, Third Edition

9.

5th Semester Syllabus BE Information Technology

6th Semester Syllabus BE Information Technology

BCA Bachelor Of Computer Application, BCCA, Bachelor of Commerce & Computer Application BE IT/CS, Information technology/Computer Science MCA, Master of Computer Application MCM, Master of Computer Management Diploma , Polytechnic Others,