Data Structures

Abstract Data Types (specification, performance implications), growth of functions and asymptotic analysis, Master's theorem (without proof). Analysis of array vs linked representations, Sparse Matrices (transpose and multiplication), Comparison-based sorting: insertion, shell, merge, quick, heap sort — algorithm and comparisons, Time and space complexity, Stability and adaptivity of sorts, Sorting in practice: library sorting functions, Sorting linked lists, Divide and conquer review via mergesort/quick sort, Introduction to non- comparison-based sorting (counting, radix — concept only).

Binary trees: traversal techniques, recursive vs non-recursive, Binary Search Trees (BST): insertion, deletion, search, AVL Trees: balancing, rotations, complexity, Heaps and priority queues: heapify, build-heap, insert/delete, Applications: expression trees, interval trees, use of recursion and stack in tree processing, Performance trade-offs among tree variants. Multi-way search trees: m-ary search tree, B-Trees (order, height, node structure, insertion, deletion), B+ Trees (leaf-level chaining, indexing applications), Search operations in B+ Trees

Hash tables: hash function design, collision handling (chaining, open addressing), Load factor, rehashing strategies, Dictionary ADT and map APIs, Trie data structure: insertion, search, memory model, Disjoint Sets (Union-Find) with path compression and union by rank, Bit-fields and memory efficiency

Graph representations: adjacency list, adjacency matrix, edge list, Graph traversal algorithms (BFS, DFS) and applications (cycle detection, component labeling), Minimum Spanning Tree (Kruskal, Prim), Shortest paths (Dijkstra, Bellman-Ford), Graph design for real applications (idea of social networks, compiler dependency graphs)