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:
1. Implement List ADT
2. Linked list implementations of List
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:
7. Tree representation and traversal algorithms
8. Implementation of Binary Search Trees
9. Implementation of Heaps
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:
10. Graph representation and Traversal algorithms
11. Implementation of single source shortest path algorithm
12. Implementation of minimum spanning tree algorithms
Reference Book:
Lee, KentD., Hubbard, Steve, “Data Structures and Algorithms†Springer Edition2015
Rance D.Necaise, “Data Structures and Algorithmsâ€, John Wiley & Sons, 2011
Aho, Hopcroft, and Ullman,“DataStructuresandAlgorithmsâ€,PearsonEducation,1983.
Thomas H. Cormen, Charles E. Leiserson, Ronald L.Rivest, and Clifford Stein, “Introduction to Algorithms", Second Edition,McGrawHill,2002.
Mark Allen Weiss, “Data Structures and Algorithm Analysis in Câ€, Fourth Edition, Pearson Education, 2014
Text Book:
MichaelT.Goodrich,RobertoTamassia,andMichaelH.Goldwasser,“DataStructures& Algorithmsâ€, An Indian Adaptation, John Wiley & Sons Inc., 2021
