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.



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.



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.



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. 



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.



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.

Articles View Hits
   Fri, 23-Aug-2019, 05:45 PM DATA STRUCTURES .
Powered by Joomla 1.7 Templates
Developed by MVSREC