### 44CS1: Discrete Mathematics and Graph theory

**Unit 1 :**

Set Theory Operation of Sets – relation and functions, partial order, equivalence relation peano axioms and inductions.

**Unit 2 :**

Mathematical Logic Propositions, predicate logic, formal mathematical system, algebra, Homomorphism, Automorphism.

**Unit 3 :**

Groups Element of theory of some Algebras, semi group, monoid groups.

**Unit 4 : **

Rings Rings, fields, lattices, Boolean Algebra.

**Unit 5 : **

Graph Theory Graphs, Hyper Graph, Transitive Closure, Spanning Trees.

**Unit 6 :**

Combinatorics Generating Functions, recurrences, counting theorem and applications

**Text Books:**

· Discrete Mathematical Structures for computer science, Kolman / Rahman Pearson education.

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

· (Common to CS/CT/CE/IT)44CS2: Data Structures And Program Design In ‘C’

·

### 44CS2: Data Structures & Program Design

**UNIT I**

General concepts and linear data structures: Abstract data structure as an organization of data with specified properties and operations, Time and space analysis of algorithms, Big oh and theta notations and omega notations, Average, best and worst case analysis, Representation of Arrays -Single and Multi dimensional-Address calculation using column and row major ordering, Representation of Stacks and queues using arrays – Circular queues, Priority Queues, Dequeue, Application of stacks, Conversion from infix to post fix and pre-fix expressions, Evaluation of postfix expression using stacks, Multiple stacks

**UNIT II**

Linked list: Linked Lists, Simply linked list, Implementation of linked list using static and dynamic memory allocationdynamic memory allocation, operations on list linked stacks and queues, polynomial representations and manipulations are using linked list, circular linked list, doubly linked list, Generalized list.

**UNIT III**

Trees: General and binary trees, Representations and traversals, General trees as binary trees, Binary search trees, Applications, The concept of balancing and its advantages, B-Trees, B+ Trees, AVL Trees, Threaded Binary Trees.

**UNIT IV**

Hashing: Hash functions, Collision resolution, Expected behavior, Applications

**UNIT V**

Graphs and digraphs: Representations, Breadth and depth first searches, Connectivity algorithms, shortest path, Minimal spanning tree, The union find problem, Hamiltonian path

**UNIT VI**

Sorting: Elementary sorts: selection, insertion, bubble sort, shell sort, Radix sort, Quick sort, merge sort, heapsort, Bucket sorting, External sorting, Worst case and average behavior, Lower bound for sorting using comparisons

**Textbooks:**

· Data Structures using C and C++ by Y. Langsam, Pearson Education

· Data Structures using C by Tenenbaum, Pearson Education

· Data Structures using C by S. K. Bandyopadhyay, Pearson Education

· S. Sahani, Data Structures in C,

· D.Samantha, Classic Data Structure, PHI Publications

· Data structures -Robert Kruse

**44CS3: Business Data Processing**

**UNIT-I:**

Structural Organization of COBOL: Character set, Words, Sentences, dentification Division, Environment Division, Data Division, Data types – numerical, lphabetic & alphanumeric, Input-output sections, Working storage sections, PROCEDURE division features: ACCEPT, DISPLAY, MOVE, Arithmetic & COMPUTE verbs, levels ,Error Handling, Sample programs, PERFORM & GOTO verbs, Sample programs using PERFORM, Miscellaneous COBOL statements.

**UNIT-II:**

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

**UNIT-III:**

Business Files: Structured Flow charts, 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.

**UNIT VI :**

Advanced Tool manipulators like STRING, UNSTRING, INSPECT & COPY verbs, COBOL Subprogram and main Program.

For Practical: 10-12 experiments on COBOL based on above syllabus.

**TEXT BOOKS:**

· COBOL Programming with business application – N.L.Sarda

· Information Systems through COBOL – Philippakis & Kazmier

· Structured COBOL Programming – Stern & Stern

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

### 44CS4: Theoretical Foundations of Computer Science

**UNIT I**

Mathematical preliminaries – Sets, operations, relations, strings, transitive closure, countability and diagonalisation, induction and proof methods- pigeon-hole principle and simple applications – concept of language – grammars and

production rules –Chomsky hierarchy.

**UNIT II**

Finite State machine, regular languages, deterministic finite automata, ,conversion to deterministic automata, E-closures –regular expressions, finite automata, minimization of automata , Moore and Mealy machine and their equivalence.

**UNIT III**

Pumping lemma for regular sets- closure properties of regular sets- decision properties for regular sets, equivalence between regular language and regular grammar. Context – free languages – parse trees and ambiguity , reduction of

CFGS ,Chomsky and Griebach normal forms

**UNIT IV**

Push – down Automata (PDA) – non Determinism – acceptance by two methods and their equivalence ,conversion of PDA to CFG CFLs and PDAs- closure and decision properties of CFLs

**UNIT V**

Turing machines – variants – recursively enumerable (r.e.) set – recursive sets

TM as computer of function – decidability and solvability – Halting Problem – reductions – Post correspondence Problem (PCP) and unsolvability of ambiguity problem of CFGs, Church’s hypothesis.

**UNIT VI**

Introduction to recursive function theory – primitive recursive and partial recursive functions , Parsing: top down and bottom up approach, derivation and reduction

**Text Books**

· Introduction to formal languages and automata – Peter Linz Norasa,2000.

· Theory Of Computer Science –Mishra and Chandrashekharan, PHI

**Reference Books**

· Introduction Of Automata Theory, Languages and computation- J.E. Hopcroft , J.D.Ulman, Pearson education.

**44CS5: Computer Architecture & Organization**

UNIT I

BASIC STRUCTURE OF COMPUTERS: Functional units, Basic operational concepts, Bus structures Addressing modes, subroutines: parameter passing, Instruction formats, expanding opcodes method. BASIC PROCESSING UNIT: bus architecture, Execution of a Complete Instruction, sequencing of control signals, Hardwired control, Microprogrammed Control, microinstruction format, Bit slice concept.

**UNIT II**

ARITHMETIC: Number representations and their operations, Design of Fast Adders, Signed multiplication, Booth’s Algorithm, bit-pair recoding, Integer Division, Floating point numbers and operations, guard bits and rounding.

**UNIT III**

THE MEMORY SYSTEM: various technologies used in memory design, higher order memory design, multimodule memories and interleaving, Associative Memory, Cache memory, Virtual Memory

**UNIT IV**

INPUT/OUTPUT ORGANIZATION: I/O mapped I/O and memory mapped I/O, interrupts and interrupt handling mechanisms, vectored interrupts, synchronous vs. asynchronous data transfer, Direct Memory Access COMPUTER PERIPHERALS: I/O devices such as magnetic disk, magnetic tape, CDROM systems.

**UNIT V**

RISC philosophy, pipelining, basic concepts in pipelining, delayed branch, branch prediction, data dependency, influence of pipelining on instruction set design, multiple execution units, performance considerations,

**UNIT VI**

Basic concepts in parallel processing & classification of parallel architectures. Vector Processing, Array Processors.

**BOOKS:·**

V.C.Hamacher,Z.G.Vranesic and S.G.Zaky, Computer Organisation, McGraw Hill,5thed,2002.

· Computer Architecture & Organization III Ed- J.P.Hayes.

· A.S.Tanenbaum, “Structured Computer Organization” 4th Edition, Pearson Education

**REFERENCES BOOKS:**

· M Mano, “Computer System and Architecture”, Pearson Education

· W. Stallings, “Computer Organization & Architecture”,Pearson Education

**44CS6: Internet Technologies**

Practical to be conducted based on following topics:

1) HTML: Standard use for www documents on internet, GML, SGML, HTML tags, special characters, Fonts, Lists,

Images, Tables, Forms and Frames.

2) DHTML: Introduction to CSS, Fonts in CSS, Text in CSS, Boxes in CSS, CSS positioning, Tables in CSS, Generated

content and lists in CSS.

3) XML: XML basics, understanding markup languages, structures and syntax, valid Vr well formed XML, DTD

(document type Definition) classes. Scripting XML, XML processor, parent child relationship, XML as a data, data type in

XML, XML namespaces, linking with XML simple link, the HTML way, XSL with style: style sheet basics, XSL basics,

XSL style sheets.

4) FRONTPAGE:

5) SECURITY:

6) Scripting Language: Perl Scripts, Java Scripts:

7) PHP

**TEXT BOOKS**

· XML in action web technology by William J. Pardi (PHI) Pub.

· Web Technology by Ramesh Bangia (Firewall Media)

· Programming the web using XML by Ellen Pearlman (Tata McGraw – Hill)