MCA-203 DATA STRUCTURE SYLLABUS

RAJIV GANDHI PROUDYOGIKI VISHWAVIDYALAYA

  (University of Technology of Madhya Pradesh)

COURSE OF STUDY AND SCHEME OF EXAMINATION

MASTER OF COMPUTER APPLICATIONS (MCA)

W.E.F. 2005-2006

MCA-203 DATA STRUCTURE SYLLABUS

Prerequisites: Array, Structure, pointers, pointer to structure, functions, parameter passing, recursion.

UNIT-I

Stack and Queue: contiguous implementations of stack, various operations on stack, various polish notations-infix, prefix, postfix, conversion from one to another-using stack; evaluation of post and prefix expressions. Contiguous implementation of queue: Linear queue, its drawback; circular queue; various operations on queue; linked implementation of stack and queue- operations

UNIT-II

General List: list and it’s contiguous implementation, it’s drawback; singly linked list-operations on it; doubly linked list-operations on it; circular linked list; linked list using arrays.

UNIT-III

Trees: definitions-height, depth, order, degree, parent and children relationship etc;

Binary Trees- various theorems, complete binary tree, almost complete binary tree;

Tree traversals-preorder, in order and post order traversals, their recursive and non recursive implementations; expression tree- evaluation; linked representation of binary tree-operations. Threaded binary trees; forests, conversion of forest into tree. Heap-definition.

UNIT-IV

Searching, Hashing and Sorting: requirements of a search algorithm; sequential search, binary search, indexed sequential search, interpolation search; hashing-basics, methods, collision, resolution of collision, chaining; Internal sorting- Bubble sort, selection sort, insertion sort, quick sort, merge sort on linked and contiguous list, shell sort, heap sort, tree sort.

UNIT-V

Graphs: related definitions: graph representations- adjacency matrix, adjacency lists, adjacency multilist; traversal schemes- depth first search, breadth first search; Minimum spanning tree; shortest path algorithm; kruskal & dijkstra algorithm.

Miscellaneous features Basic idea of AVL tree- definition, insertion & deletion operations; basic idea of B-tree- definition, order, degree, insertion & deletion operations;

B+-Tree- definitions, comparison with B-tree; basic idea of string processing.

BOOKS

1.      Kruse R.L. Data Structures and Program Design in C; PHI

2.      Aho “Data Structure & Algorithms”.

3.      Trembly “Introduction to Data Structure with Applications”.

4.      TennenBaum A.M. & others: Data Structures using C & C++; PHI

5.      Horowitz & Sawhaney: Fundamentals of Data Structures, Galgotia Publishers.

6.      Yashwant Kanetkar, Understanding Pointers in C, BPB.

Note : Paper is to be set unit wise with internal choice.