Course Objectives:

1. 1.To develop proficiency in the specification, representation, and implementation of abstract data types and data structures.

1. 2.To get a good understanding of applications of data structures.

1. 3.To solve advanced computer science problems by making appropriate choice for intended applications.

UNIT-I

Algorithm Specification,  Performance Analysis and Measurement.

Arrays: Abstract Data Types and the C++ Class, Array as an Abstract Data Type, Polynomial Abstract Data Type, Sparse Matrices, Representation of Arrays, String Abstract Data Type.

UNIT-II

Stacks and Queues: Templates in C++, Stack Abstract Data Type, Queue Abstract Data type, Sub typing and Inheritance in C++, A Mazing Problem, Evaluation of Expressions.

.

UNIT-III

Linked Lists: Singly Linked Lists and Chains, Representing Chains in C++, Template Class Chain, Circular Lists, Available Space Lists, Linked Stacks and Queues, Polynomials, Doubly Linked Lists.

Hashing: Static Hashing, Hash Tables, Hash Functions, Overflow Handling, Theoretical Evaluation of Overflow Techniques

UNIT-IV

Trees: Introduction, Binary Trees, Binary Tree Traversal and Tree Iterators, Copying Binary Trees, Threaded Binary Trees, Heaps, Efficient Binary Search Trees: AVL Trees, m-way Search Trees, Introduction to Red Black tree & splay tree, B-tree.

Graphs: Graph Abstract Data Type, Elementary Graph operations (DFS and BFS), Minimum Cost Spanning Trees (Prim’s and Kruskal’s Algorithms).

UNIT-V

Sorting: Insertion sort, Quick sort, Best computing time for Sorting, Merge sort, Heap sort, shell sort, Sorting on Several Keys, List and Table Sorts, Summary of Internal Sorting.