Data Structures Syllabus

A Hunt for Reaching Horizon of Science

Syllabus

UNIT-I

Algorithm Specification, Performance Analysis and Measurement. Arrays: Abstract Data Types and the C++ Class, The Array as an Abstract Data Type, The Polynomial Abstract Data Type, Sparse Matrices, Representation of Arrays, The String Abstract Data Type.

 

UNIT–II

Stacks and Queues: Templates in C++, The Stack Abstract Data Type, The Queue Abstract Data type, Subtyping and Inheritance in C++, A Mazing Problem, Evaluation of Expressions, Additional Exercises.

UNIT-III

Linked Lists: Singly Linked Lists and Chains, Representing Chains in C++, The Template Class Chain, Circular Lists, Available Space Lists, Linked Stacks and Queues, Polynomials, Equivalence Classes, Sparse Matrices, Doubly Linked Lists, Generalized Lists. 
 

UNIT-IV

Hashing: Static Hashing.

Trees: Introduction, Binary Trees, Binary Tree Traversal and Tree Integrators, Copying Binary Trees, Threaded Binary Trees, Heaps, Binary Search Trees. 
Efficient Binary Search Trees: AVL Trees, Red-Black Trees, Splay Trees, m-way Search Trees, B-Trees.

 

UNIT-V

Sorting: Insertion sort, Quick sort, How Fast Can We Sort, Merge sort, Heap sort, Sorting on Several Keys, List and Table Sorts, Summary of Internal Sorting.
Graphs: The Graph Abstract Data Type, Elementary Graph operations (dfs and bfs), Minimum Cost Spanning Trees (Prim’s and Kruskal’s Algorithms).

Suggested Reading:

1.Ellis Horowitz, Dinesh Mehta, S. Sahani. Fundamentals of DataStuctures in C++, Universities Press. 2007.

 2.T.H. Cormen, C.E. Leiserson, and R.L. Rivest.Introduction toAlgorithms,Prentice Hall of India 1996.

3.Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, Pearson Education 2006.