DETAILED LESSONS – DESIGN AND ANALYSIS OF ALGORITHMS (DAA)
1. INTRODUCTION TO ALGORITHMS
- An algorithm is a finite set of step-by-step instructions to solve a problem.
- Properties: correctness, finiteness, definiteness, input/output, efficiency.
- Pseudocode: a structured, human-readable way of writing algorithm steps.
- Algorithm vs program: algorithm is logic; program is implementation.
2. ALGORITHM COMPLEXITY
Time Complexity:
- Measures the runtime growth as input size increases.
- Big O: upper bound (worst case).
- Big Θ: tight bound (average case).
- Big Ω: lower bound (best case).
- Common complexities: O(1), O(log n), O(n), O(n log n), O(n²), O(2■).
Space Complexity:
- Memory used by algorithm including input + extra (auxiliary) space.
3. MATHEMATICAL ANALYSIS TECHNIQUES
Growth of Functions:
- Comparing rates like polynomial vs exponential.
Recurrence Relations:
- Expressing runtime in terms of smaller subproblems.
Example: T(n) = 2T(n/2) + n.
Master Theorem:
For T(n) = aT(n/b) + f(n):
- Case 1: if f(n) < n^(log_b a) → T(n) = n^(log_b a)
- Case 2: if f(n) = n^(log_b a) → T(n) = n^(log_b a) log n
- Case 3: if f(n) > n^(log_b a) → T(n) = f(n)
4. ALGORITHM DESIGN TECHNIQUES
Divide and Conquer:
- Break problem → solve recursively → combine results.
Examples:
- Merge Sort (O(n log n))
- Quick Sort (O(n log n) average)
- Binary Search (O(log n))
Greedy Algorithms:
- Make the best local choice at each step.
Examples:
- Activity Selection (choose earliest finishing activity)
- Fractional Knapsack (choose highest value/weight ratio)
- Kruskal’s and Prim’s for MST
Dynamic Programming (DP):
- Solve subproblems once and store results (memoization/tabulation).
Examples:
- Fibonacci DP (O(n))
- Longest Common Subsequence (O(nm))
- Matrix Chain Multiplication (optimal parenthesization)
- 0/1 Knapsack (O(nW))
Backtracking:
- Try solutions, backtrack if not valid.
Examples:
- N-Queens (place queens row by row)
- Sudoku solver (fill cells using constraints)
- Generating permutations and combinations
Branch and Bound:
- Optimized backtracking using bounds to prune branches.
Examples:
- Traveling Salesman Problem (TSP)
- Branch and bound knapsack
5. GRAPH ALGORITHMS
- BFS (Breadth-First Search) – level-order exploration.
- DFS (Depth-First Search) – deep exploration using recursion/stack.
- Shortest Path: Dijkstra, Bellman-Ford.
- Minimum Spanning Tree: Prim, Kruskal.
6. SORTING AND SEARCHING
Sorting Methods:
- Bubble Sort, Insertion Sort, Selection Sort (O(n²))
- Merge Sort, Quick Sort (O(n log n))
Searching:
- Linear Search (O(n))
- Binary Search (O(log n))
7. NP-COMPLETENESS
- P, NP, NP-hard, NP-complete definitions.
- Polynomial time vs exponential time problems.
- Famous NP-complete problems: TSP, SAT, 3-coloring, subset sum.
- Reduction: transform one problem into another.
8. ADVANCED TOPICS
- Amortized Analysis (dynamic array resizing)
- Randomized Algorithms (Randomized QuickSort)
- Approximation Algorithms (for NP-hard problems)
END OF DOCUMENT