01
Unit 1: Foundations of Algorithm Analysis
The Algorithm as a concept, Measuring Performance. Time and Space Complexity. Asymptotic Notations: Big-O (Upper Bound), Big-Omega (Lower Bound), and Big-Theta (Tight Bound). Best, Average, and Worst-Case Analysis. Analysis of Iterative Algorithms. Analysis of Recursive Algorithms using Recurrence Relations: Substitution Method, Recursion Tree Method, and the Master Theorem for solving recurrences.
02
Unit 2: Divide and Conquer & Greedy Algorithms
The Divide and Conquer strategy: Recurrence relation and analysis. Classic Algorithms: Binary Search, Merge Sort, and Quicksort (including randomized versions). The Greedy Method: General approach, proof of correctness (Greedy Choice Property, Optimal Substructure). Applications: Fractional Knapsack Problem, Job Sequencing with Deadlines, Huffman Coding, and Minimum Spanning Tree algorithms (Prim's and Kruskal's).
03
Unit 3: Dynamic Programming
The Dynamic Programming paradigm, comparison with Divide and Conquer. Overlapping Subproblems and Optimal Substructure properties. Design approaches: Memoization (Top-Down) vs. Tabulation (Bottom-Up). Applications: 0/1 Knapsack Problem, Longest Common Subsequence (LCS), Matrix Chain Multiplication, and the All-Pairs Shortest Path problem (Floyd-Warshall Algorithm).
04
Unit 4: Backtracking and Advanced Graph Algorithms
Backtracking: The general method, constructing the state-space tree. Applications: N-Queens Problem, Sum of Subsets, and Graph Coloring. Branch and Bound as an optimization of backtracking. Single-Source Shortest Paths: Dijkstra's Algorithm (using Priority Queues) and the Bellman-Ford Algorithm for handling negative edge weights.
05
Unit 5: Complexity Theory and String Matching
Introduction to Computational Complexity. The complexity classes P (Polynomial time) and NP (Nondeterministic Polynomial time). Understanding NP-Completeness and the concept of reduction. Introduction to NP-Complete problems (e.g., TSP, SAT). String Matching Algorithms: Naive approach, Rabin-Karp Algorithm, and the Knuth-Morris-Pratt (KMP) Algorithm.