DATA STRUCTURES -----SEM II

Data Structures

UNIT I

Abstract data types - asymptotic notations – complexity analysis – Arrays- representation of arrays – operations on arrays – ordered lists – polynomials.

UNIT II

Linked lists: Singly linked list- circular linked lists - doubly linked lists – general lists – stacks -queues - circular queues – Evaluation of expressions.

UNIT III

Trees – Binary Trees – Binary Tree Traversals – Binary Tree Representations – Binary Search Trees – Threaded Binary Trees – Application of Trees (Sets) – Representation of Graphs – Graph Implementation – Graph Traversals- Application of Graph Traversals- Minimum Cost Spanning Trees – Shortest Path Problem

UNIT IV

Internal Sorting – Optimal Sorting Time – Sorting Large Objects – Sorting with Tapes- Sorting with Disks.

UNIT V

Hashing – AVL Trees - Red-Black Trees – Splay Trees – B-Trees.

Text Books

(i) E.Horowitz, S. Sahni and Mehta, 1999, Fundamentals of Data Structures in C++, Galgotia, New Delhi

Reference Books

(i) G. L. Heileman, 1996, Data Structures, Algorithms and Object Oriented Programming, Tata McGraw-Hill, New Delhi. (ii) A.V.Aho, J.D. Ullman, J.E. Hopcraft, 1983, Data Structures and Algorithms, Addison Wesley, Boston. (iii) S. Sahni , 2001, Data structures , Algorithms & Applications, Tata McGraw-Hill, New Delhi. (iv) Yedidyah Langsam Augensteil, Tanenbaum, Data Structures using C and C++ , PHI, New Delhi (v) Gilberg , Forouzan, 2002, Data Structures,Thomson Asia, Singapore.