BCA 3 SEMESTER DATA STRUCTURE SYLLABUS

 

 DATA STRUCTURE

 SYLLABUS: 

 Basic concepts of data representation Abstract data types: Fundamental and derived data types. Representation, Primitive data Structures. Introduction to algorithms Design and Data Structures Design and analysis of algorithm: Algorithm definition, comparison of algorithms. Top-down and bottom up approaches to algorithm Design. Analysis of algorithm; Frequency count, complexity measures in terms of time and space, structured approach to programming. 

 

Arrays: Representation of arrays: single and multidimensional arrays, Address calculation using column and row major ordering, various operations on Arrays. Vectors. Application of arrays: Matrix multiplication, sparse polynomial representation and addition. 

 

Stacks and Queues: Representation of stacks and queues using arrays and linked list. Circular queues, Priority Queue and DQueue, Applications of stacks: Conversion from infix to postfix and prefix expressions, Evaluation of postfix expression using stacks.

 Linked Lists: Singly linked list; operations on list, Linked, stacks and. queues. Polynomial representation and manipulation using linked lists. Circular linked lists, Doubly linked lists. Generalized list structure. Sparse Matrix representation using generalized list structure. 

 

Trees: Binary tree traversal methods: Preorder. In-order Post ordered traversal. Recursive and non-recursive Algorithms for above mentioned Traversal methods. Representation of trees and its applications; Binary, tree representation of a tree. Conversion of forest into tree. Threaded binary trees; Lexical binary trees. Decision and game trees. Binary search tree: Height balanced (AVL) tree, B-trees. 

 

Searching, Sorting and complexity Searching: Sequential and binary searches, Indexed search, Hashing Schemes. Sorting: Insertion, Selection, bubble. Quick, merge, radix shell, Heap son. Comparison of time complexity. 

 

Graphs Graph representation: Adjacency matrix, Adjacency list Adjacency Multicasts. Traversal schemes: Depth first search, Breadth first search. Spanning tree: Definition, Minimal spanning tree algorithms. Shortest Patch algorithms (Prime's and Kruskal's). 

 

References: 

 

1. Y. Langsam, M.J. Augenstein and A.M. Tanebaum, "Data Structures Using C and C++", Second Edition, 2000 Prentice Hall of India. 2.   R.Kruse, C.L. Tonodo and B.Leung, "Data Structures and Program Design in C", Second  Edition 1997, Pearson Education. 3.   S.Chottopadhyay. D. Ghoshdastidar & M.ChottQpadhyay," Data Structures through,"C"  Language", First Edition, 2001 BPB Publication. 4.  G.L.   Heileman",   Data   Structures,   algorithms and Object Oriented programming," First Edition, 2002 Tata McGraw Hill. 5. E. Horowitz, Sahni and D Mehta," Fundamentals of Data Structures in C++", 2002, Galgotia Publication 2002.