With effect from Academic Year 2015-2016

CS 201

                 DATA STRUCTURES USING C++

Instruction                                                                               4 Periods per week

Duration of University Examination                                      3 Hours

University Examination                                                          75 Marks

Sessional                                                                                 25 Marks

Course Objectives:

• To introduce the concepts of Abstract data Type, data structure, performance measurement, time and space complexities of algorithms.
• To discuss the implementation linear data structures such as stacks, queues and lists and their applications.
• To discuss the implementation of different non linear data structures such as trees and graphs.
• To introduce various search data structures such as hashing, binary search trees, red black trees, splay trees and b-trees.
• To introduce various internal sorting techniques and analyze their  time complexities.

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 Data Stuctures 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.