IT209
Course Name:
Data Structures and Algorithms (IT209)
Programme:
Semester:
Category:
Credits (L-T-P):
Content:
Elementary Data Types and Abstract data types. Computational model and complexity of algorithms (running time and space metrics), Introduction to Asymptotic notation; Worst- case, Best -case, Average-case and amortized analysis. Arrays, Linear search and Binary search on sorted arrays. List ADT and its implementation using arrays and linked lists. Types of linked lists: Single, Double, circular linked lists and their applications. Stack ADT and Queue ADT implementations with applications. Dynamic set ADT and Dictionary ADT. Hash tables – collisions, open and closed hashing, choosing good hash functions. Trees: Definitions and Representations; Tree traversals and their applications. Binary Search Trees. AVL trees, Red-black trees, B-trees; Priority Queue ADT and its implementations using Binary heaps. Applications of Priority Queues. Sorting algorithms: Merge sort and Quicksort. Randomized Quick sort and its analysis. Linear-time sorting algorithms like Radix and Counting sort. Graphs: Definitions and representations. Depth first and breadth-first search and their applications. Basic Graph algorithms like Dijkstra's shortest path algorithm and Kruskal's MST algorithm.