Data Structures and Algorithms(IT2201) Syllabus

AIM

To master the design and applications of linear, tree, and graph structures. To

understand various algorithm design and analysis techniques.

Syllabus 

UNIT I LINEAR STRUCTURES

Abstract Data Types (ADT) – List ADT – array-based implementation – linked list

implementation – cursor-based linked lists – doubly-linked lists – applications of lists –

Stack ADT – Queue ADT – circular queue implementation – Applications of stacks and

queues

UNIT II TREE STRUCTURES

Tree ADT – tree traversals – left child right sibling data structures for general trees –

Binary Tree ADT – expression trees – applications of trees – binary search tree ADT –

AVL trees – binary heaps

UNIT III HASHING AND SETS

Hashing – Separate chaining – open addressing – rehashing – extendible hashing –

Disjoint Set ADT – dynamic equivalence problem – smart union algorithms – path

compression – applications of Sets

UNIT IV GRAPHS

Definitions – Topological sort – breadth-first traversal - shortest-path algorithms –

minimum spanning tree – Prim's and Kruskal's algorithms – Depth-first traversal –

biconnectivity – Euler circuits – applications of graphs

UNIT V ALGORITHM DESIGN AND ANALYSIS

Introduction to algorithm design techniques: Greedy algorithms, Divide and conquer,

Dynamic programming, backtracking, branch and bound, Randomized algorithms –

Introduction to algorithm analysis: asymptotic notations, recurrences – Introduction to

NP-complete problems

                                                         

 TEXT BOOK:

1. M. A. Weiss, “Data Structures and Algorithm Analysis in C”, Second Edition,

Pearson Education, 1997.

 REFERENCES:

1. A. V. Aho, J. E. Hopcroft, and J. D. Ullman, “Data Structures and Algorithms”,

Pearson Education, 198UNIT III

2. R. F. Gilberg, B. A. Forouzan, “Data Structures”, Second Edition, Thomson India

Edition, 2005.

3. A. M. Tenenbaum, Y. Langsam, and M. J. Augenstein, “Data Structures using C”,

Pearson Education, 1998.

4. K.S. Easwarakumar, Object Oriented Data Structures using C++, Vikas Publishing

House pvt. Ltd., 2000

5. Sara Baase and A. Van Gelder, “Computer Algorithms”, Third Edition, Pearson

Education, 2000.

6. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "Introduction to

algorithms", Second Edition, Prentice Hall of India Ltd, 2001.