Analysis of Algorithms (BLGM371)
Definition and properties of Algorithms. Design, analysis, and representation of Algorithms. Data abstraction. Pseudo code conventions. Models of computation. Mathematical Foundations: Growth of functions, asymptotic notations. Study of recursive algorithms and associated recurrence relations (substitution method, iteration method, master method, recursion trees). Design paradigms for algorithms: Brute-Force (Exhaustive Search), Divide-and-Conquer (Merge Sort, Binary Search Tree) Dynamic Programming (Matrix-Chain multiplication, LCS-length, 01-Knapsack Problem). Greedy algorithms (Greedy Activity Selector, Fractional Knapsack Problem). Graph Algorithms: Representation of sets and graphs. Breadth-first search, depth-first search. Minimum spanning trees. Single-source shortest paths. All-pairs of shortest paths.