
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.
BE Bachelor of Engineering Information Technology 4th Sem
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.)
UNITI: 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.
UNITII: Relations and Functions(12 Hrs)
Relations: Ordered pairs and ntuples, 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.
UNITIII: 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.
UnitIV: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.
UnitV: 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.
UnitVI: 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 McGrawHill.
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, TopDown and bottomup
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, BTree, B+ Tree, AVL tree, Multiway tree, 23
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 Sourceall
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 wordlength 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:
Microprogrammed 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 objectoriented 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 LABII
(Practical Credit: 02)
Examination Scheme:
Practical: P (U): 25 Marks P (I): 25 Marks
Duration of University Exam. : 02 Hours
====================================================
G01.
Experiment based on MS Office macro programming.
G02.
Installation of OS and Configuring a Desktop for– the Windows Operating System
(XP and 7) and the Linux Operating System (Ubuntu/Fedora/Mint).
G03.
Introduction to UNIX Operating System, The UNIX architecture and Command
Usage, The File System, PIPES, Filters using Regular Expressions.
G04.
Introduction to Linux Operating System, flavors of Linux vi Editor, vim Editor
G05.
The Shell Shell Variables; Scripts; Meta Characters and Environment; if and
case Statements; for, while and until loops; Essential Shell Programming.
G06.
AWK (The PatternAction Language) BEGIN and END Patterns; Variables,
Records and Fields; Loops; Handling Text; String Manipulations.
G07.
Introduction to MATLAB Simulator and Programming based on MATLAB Simulator.
Note:
1.
Practical sessions based on Any Four/Five groups from G01 to G06 may be
planned.
2.
Practical Group G07 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++ ,
TestingSoftware
Testing,
Hardware & Networking CCNA, MCSE, Hardware,
Networking  