Abstract Data Types (ADTs) –Introduction to analysis of algorithms – asymptotic notations – Non recursion & recursion – analyzing recursive algorithms- List ADT – array-based implementations – linked list implementations – singly linked lists – circularly linked lists – doubly linked lists Exercise: Implement List ADT Linked list implementations of List

Stack ADT – Applications of Stack: Infix to Postfix conversion-Postfix Evaluation- Balanced parentheses -Function Call. Queue ADT – Circular Queue- double ended queues – applications Queue Exercise: 3.ImplementationofStackandQueueADTs 4.Applications of Stack and Queue ADTs

Bubble sort – selection sort – insertion sort – divide & conquer- merge sort – quick sort – analysis of sorting algorithms – linear search – binary search – hashing – hash functions – collision handling – load factors, rehashing, and efficiency Exercise: 5.Implementationofsortingandsearchingalgorithms 6.ImplementationofHashtables

Tree ADT – Binary Tree ADT – tree traversals – Back Tracking - binary search trees – AVL trees – heaps – multi- way search trees- Branch & Bound: Knapsack Problem Exercise: Tree representation and traversal algorithms Implementation of Binary Search Trees Implementation of Heaps

23ITB201 DATA STRUCTURES & ALGORITHMS L T P J C B.Tech-IT,AI&DS 3 0 2 0 4 COURSEOBJECTIVE 1 To understand the analysis of algorithms and efficiency 2 To understand the concepts of ADTs 3 To design linear data structures –lists, stacks, and queues 4 To understand sorting, searching, and hashing algorithms 5 To apply Tree and Graph structures UNITI LIST ADT 9+6 Abstract Data Types (ADTs) –Introduction to analysis of algorithms – asymptotic notations – Non recursion & recursion – analyzing recursive algorithms- List ADT – array-based implementations – linked list implementations – singly linked lists – circularly linked lists – doubly linked lists Exercise: Implement List ADT Linked list implementations of List UNITII STACK ADT & QUEUE ADT 9+6 Stack ADT – Applications of Stack: Infix to Postfix conversion-Postfix Evaluation- Balanced parentheses -Function Call. Queue ADT – Circular Queue- double ended queues – applications Queue Exercise: 3.ImplementationofStackandQueueADTs 4.Applications of Stack and Queue ADTs UNITIII SORTING, SEARCHING & HASHING 9+6 Bubble sort – selection sort – insertion sort – divide & conquer- merge sort – quick sort – analysis of sorting algorithms – linear search – binary search – hashing – hash functions – collision handling – load factors, rehashing, and efficiency Exercise: 5.Implementationofsortingandsearchingalgorithms 6.ImplementationofHashtables UNITIV TREE ADT 9+6 Tree ADT – Binary Tree ADT – tree traversals – Back Tracking - binary search trees – AVL trees – heaps – multi- way search trees- Branch & Bound: Knapsack Problem Exercise: Tree representation and traversal algorithms Implementation of Binary Search Trees Implementation of Heaps UNITV GRAPH ADT 9+6 Graph ADT – representations of graph – graph traversals – DAG – topological ordering –dynamic programming: shortest paths – greedy algorithms: minimum spanning trees – Limitations of Algorithm Power-P, NP and NP-Complete Problems Exercise: Graph representation and Traversal algorithms Implementation of single source shortest path algorithm Implementation of minimum spanning tree algorithms L:45 T:0 P:30 TOTAL:75 PERIODS