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.

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,

Basic Programming

C / C++ ,

Testing

Software Testing,

Hardware & Networking

CCNA, MCSE, Hardware, Networking