DATA STRUCTURES AND ALGORITHMS (SEMESTER III)

ANNA UNIVERSITY :: CHENNAI 600 025
UNIVERSITY DEPARTMENTS
REGULATIONS – 2008
CURRICULUM FROM III TO VIII SEMESTERS AND ELECTIVES FOR
B.TECH. INFORMATION TECHNOLOGY

---

 

DATA STRUCTURES AND ALGORITHMS

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 –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