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.

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