Design and Analysis of Algorithm
Subject Overview
Design and Analysis of Algorithm formalizes algorithmic problem-solving — time/space complexity and asymptotic notation, the Divide & Conquer technique (binary search, merge/quick sort, Strassen's matrix multiplication), the Greedy technique (Knapsack, Prim's/Kruskal's/Dijkstra's algorithms), and Dynamic Programming (Fibonacci, Floyd-Warshall, 0/1 Knapsack) plus graph algorithms. A 3-credit core theory paper.
Unit-wise Syllabus
4 units — click WhatsApp below to get the full notes for each
Unit 1: Complexity analysis and recursion
Design and performance analysis of algorithms, time and space complexity, asymptotic notations (O, Ω, Θ), analysis of sequential search/bubble sort/selection sort/insertion sort/matrix multiplication, recursion basics, analysis of recursive algorithms, Master's theorem
Unit 2: Divide and Conquer
General concept, binary search, finding maximum and minimum, merge sort, quick sort, best/worst case analysis, Strassen's matrix multiplication, lower bound for comparison-based sorting
Unit 3: Greedy technique
General concept, general Knapsack problem, minimum weight spanning trees via Prim's and Kruskal's algorithms, Dijkstra's algorithm for single-source shortest paths
Unit 4: Dynamic Programming and graph algorithms
General concept, Fibonacci series and binomial coefficient computation, all-pairs shortest paths (Floyd-Warshall), 0/1 Knapsack problem, finding connected components, topological sorting