44CS1: Discrete Mathematics and Graph theory
Unit 1 :
Set Theory Operation of Sets – relation and functions, partial order, equivalence relation peano axioms and inductions.
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.
Mathematical Logic Propositions, predicate logic, formal mathematical system, algebra, Homomorphism, Automorphism.
Unit 3 :
Groups Element of theory of some Algebras, semi group, monoid groups.
Groups Element of theory of some Algebras, semi group, monoid groups.
Unit 4 :
Rings Rings, fields, lattices, Boolean Algebra.
Rings Rings, fields, lattices, Boolean Algebra.
Unit 5 :
Graph Theory Graphs, Hyper Graph, Transitive Closure, Spanning Trees.
Graph Theory Graphs, Hyper Graph, Transitive Closure, Spanning Trees.
Unit 6 :
Combinatorics Generating Functions, recurrences, counting theorem and applications
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’
·
· 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
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.
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.
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
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
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
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
· 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-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.
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.
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.
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.
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.
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.
· 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.
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.
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
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
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.
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
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
· 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.
· 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.
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
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.
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,
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.
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
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
· 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
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)
· 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)
No comments:
Post a Comment