### 4IT-22 DISCRETE MATHEMATICS AND GRAPH THEORY

**UNIT-I:**

Mathematical Logic and Set Theory: Statement and Notation, Negotiation, Conjunction, Disjunction, Tautologies, Truth tables, Basic concepts of set theory, Inclusion and equality of sets, The power set, Ordered pairs and n-tuples.

**UNIT-II:**

Relations and Functions: Relation and ordering, Properties of Binary Relations in a set Relation Matrix and the Graphs a Relation, Partition and Covering of a set. Equivalence relation, Partial ordering, Partially ordered set, Functions (definition and introduction), Composition of functions, Inverse functions, Characteristics function of a set.

**UNIT-III:**

Group Theory: Semigroups and Monoids(defininitions and examples), Homomorphism of semigroups and monomoids, Subsemi groups and submonoids, Groups(definitions and examples) Subgroups and Homomorphisms, Cosets and Lanranges theorem, Normal

subgroups, Codes and group codes.

**UNIT-IV:**

Rings(definition and examples): Integral domains ring homomorphisms, Ideas of Ring polynomial.

**UNIT-V:**

Graph Theory: Basic concepts of Graph Theory, Basic definitions, Paths and circuits. Rechability and connectedness, Matrix representation of graphs, Trees and their representation and operations, Rooted trees, Path lengths in rooted trees, Multi graphs and weighted graphs, Shortest paths in weighted graphs.

**TEXT BOOKS:**

1. Discrete Mathematics Structures with application to Computer Science by J. P.

Tremblay & R. Manohar.

2. Discrete Maths for Computer Scientists & Mathematicians. (Chapter 2, 5, 7) by J. L. Mott, A. Kandel, T. P. Baker

**REFERENCES:**

Elements of Discrete Mathematics by C. L. Liu.

Discrete Mathematics by Lipschutz

Discrete Mathematics by R.Johnsonbaugh.

### 4IT23 ALGORITHM AND DATA STRUCTURES

**UNIT-I:**

Introduction to algorithm: Analysis of algorithms. The asymptotic notations, Features of structured program, Recursion, Top down and bottom-up programming techniques, Divide and conquer strategy. Stacks and Queues: Fundamentals, Evaluation of expressions, Polish expressions and their compilation,

Application of stacks, Multiple stacks and queues, Priority queues.

**UNIT-II:**

Linked list: Single linked list, linked stacks and queues, The polynomial addition, Example on linked list, Equivalence relation, Circular linked list, Doubly linked list and Generalized list.

**UNIT-III:**

Sorting Methods: Internal and external sort, bubble sort, exchange, insertion, selection, merge, heap, radix and quick sort, Comparision with respect to their efficiency. Searching Methods: Sequential, binary, indexed search, Hashing techniques and collision handling mechanism.

**UNIT-IV:**

Trees: Definition and terminology, Representation, Tree traversal examples on trees, Threaded trees, Binary tree, Binary search tree, Operation on multi-way trees, B trees and B+ trees.

**UNIT-V:**

Graph and their applications: Computer representation of Graphs, Traversal techniques like Breadth first search, Depth first search, Greedy algorithms-study with respect to shortest path, minimum cost spanning tree.

PRACTICALS based on above syllabus.

**TEXT BOOKS:**

1. An introduction to Data structures with Applications by Trembley J.P. & Sorenson P. G.

2. Algorithm, Data Structures & Programs by Niclaus Worth.

3. Data structures using C/C++ by Tanenbaum.

### 4IT24 COMMUNICATION ELECTRONICS

**UNIT-I:**

Analog Systems: Frequency spectrum of electromagnetic waves, Their properties,

Properties of Fourier transform, Convolution in time and frequency domain,

Sampling theorem, Noise types, Sources.

**UNIT-II:**

Mechanism of amplitude modulation and detection, SSB, SSB-SC, DSB, Various techniques of generation and detection of FM, Comparision of various system based on SNR.

**UNIT-III:**

Digital Systems: Bandwidth and rate of pulse transmission, Pulse spreading and interference, PSD of digital signals, Line coding, Digital multiplexing.

**UNIT-IV:**

Pulse Modulation: PAM, PWM, PCM and PPM systems, quantization and noise, Delta modulation.

**UNIT-V:**

Digital Carrier System, Salient features of ASK, FSK, PSK and DPSK systems, M-ary communication system.

PRACTICAL based on above syllabus:

**TEXT BOOKS:**

1. Modern Digital and Analog Communication System by B. P. Lathi.

2. Communication System by B. P. Lathi.

3. Digital Communication by Proakis.

**REFERENCES:**

1. Communication Systems by A. B. Carlson.

2. Principle of Communication System by Taub & Schilling.

3. Communication Electronics by Kennedy.

### 4IT25 DATA PROCESSING AND FILE OIRGANIZATION

**UNIT-I:**

Structural Organization of COBOL: Character set, Words, Sentences, Identification Division, Environment Division, Data Division, Data types – numerical, Alphabetic & alphanumeric, Input-output sections, Working

storage sections, PROCEDURE division features: ACCEPT, DISPLAY, MOVE, Arithmetic & COMPUTE verbs, Sample programs, PERFORM & GOTO verbs, STRING, UNSTRING, INSPECT & COPY verbs, Sample programs using PERFORM, Miscellaneous COBOL statements.

**UNIT-II:**

Conditional Statements & Handling: Relation conditions, Nested conditions, Class conditions, Conditionname conditions, Structured programming forms of program structure, Structural flow charts, Subscripting, OCCURS clause, Multidimensional tables, Table handling with PERFORM verb.

**UNIT-III:**

Business Files: Operation on files, Master files, Transaction file, Report file, Batch processing, On-line processing, case studies. Sequential Access Files: Principles of magnetic storage & accessing, Blocking, Inter record gap, Label records, COBOL language instructions for sequential files.

**UNIT-IV:**

Direct Access Files: Characteristics of disk storage & timing index, Indexed sequential files, COBOL instruction for indexed sequential files, relative file organization, Division-Remainder method, digital-analysis method, COBOL instructions for handling relative files.

**UNIT-V:**

Sorting, Searching & merging: Linear search sort, Merge sort, Chained record sort, Linear search, Binary search, File sorting & Merging using sequential files. Report Generation: Output layout design, Heading, Date & Detailed summaries.Control breaks, Language specifications for COBOL report writing.

PRACTICALS based on above syllabus.

**TEXT BOOKS:**

1. Information System through COBOL by S. Philiphakis, Leenard.

2. COBOL Programming by M. K. Roy, D. Ghosh Dastidar.

### 4IT26 THEORY OF COMPUTATION

**UNIT-I:**

Strings, Alphabet, Language, Operations, Finite state machine, definitions, Finite automation model, Acceptance of strings and languages, 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 Melay machines.

**UNIT-II:**

Regular sets, Regular expressions, Identify rules, Manipulation of regular expressions. Equivalence between RE and FA, Inter conversion, Pumping lemma, Closure properties of regular sets (proofs not required), Regular grammars, Right linear and left linear grammars, Equivalence between regular linear grammar and F.A. 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 , Interconversion, enumeration of properties of CFL. (proofs omitted).

**UNIT-IV:**

Turing Machine, Definition, Model, Design of TM, Computable functions, Recursive ensumerable language, Church’s hypothesis, Counter machine, Types of TM’s (Proofs not required). Chomsky hierarchy of languages, Linear bounded automata and context sensitive language, Introduction of DCFL and DPDA, LR(0), grammar, Desidability of problems.

**UNIT-V:**

Undecidability: Properties of recursive & non-recursive ensumarable languages, Universal Turing Machine, Post-correspondence problem, Introduction to recursive function theory.

**TEXT BOOK:**

1. Introduction to Automata Theory, Languages and Computation by Hopcraft H. E. & Ulman J.

2. An Introduction to formal Languages and Automata by Peter Linz (Chapter 1 to 12 except 6.3 and 7.4)

**REFERENCES:**

1. Introduction to Languages and the Theory of Automata by John C. Martin

2. Elements of Theory of Computation by Lewis H. P. and Papadimiton C. H.

3. Theory of Computation by Mishra and Chandrashekharan

### 4IT27 COMPUTER ARCHITECTURE AND ORGANIZATION

**UNIT-I:**

Basic Structure of Computer Hardware & Software: Functional unit, Basic operational concepts, Bus structures, Software performance, Distributed computing Addressing Methods & Machine Program sequencing: Memory locations, Addresses & encoding of information, Main memory operations, Instructions

& instruction sequencing, Addressing modes, Assembly language, Basic input-output operations, Stacks, Subroutines.

**UNIT-II:**

The 68000 example: Registers & addressing Instructions, Assembly language. Program flow control, Sorting example, Logic instructions, Program controlled I/O, Subroutines. Power PC examples: Basic power PC organization, Load and storing instruction, Arithmetic and logical instructions, flow control instruction, Compare instructions Subroutines.

**UNIT-III:**

The Processing Unit: Some fundamentals concepts, Execution of complete instruction, Hardware control, Performance considerations, Microprogrammed control Input-Output Organization: Accessing I/O devices, Interrupts, DMA.

**UNIT-IV:**

Arithmetic: Number representations, Addition of positive numbers, Logic design of fast adders, Addition & subtraction, Arithmetic & branching conditions, Multiplication of positive numbers, Signed operand multiplication, Fast multiplication, Fast multiplication, Integer division.

**UNIT-V:**

The Main Memory: Some basic concepts, Semiconductors RAM memories, Memory system consideration, Semiconductor ROM memories, Multiple-module memories and interleaving, Cache memories, Virtual memories, Memory management requirements Pipelining: Basic concepts, Instruction queue, Branching, Data Dependency, Influence of pipelining on instruction set design, Multiple execution units, Performance considerations, Examples of CISC, RISC & stack processors.

**TEXT BOOKS:**

Computer Organization by V. C. Hamacher, Z. G. Vranesic and S. G. Zaky.

Fourth Edition, McGraw Hill Publ.

**REFERENCES:**

Computer Organization & Architecture by William Stalling.

Computer Architecture & Organization by J. P. Hayes, Third Ed., McGraw Hill Publ.

### 4IT28 COMPUTER WORKSHOP-II

1. Introduction to Networking accessories.

2. Introduction to UNIX Operating System.

3. Introduction to MS-WORD & POWER-POINT.

4. Familiarity with Internet and World Wide Web.

Hey do you have syllabus for 4th sem CS Nagpur University?

yes