Module 1: Introduction to Algorithmic Analysis
• Characteristics of Algorithms: Efficiency, correctness, clarity, and scalability.
• Analysis of Algorithms:
o Asymptotic Analysis: Growth of functions (Big-O, Omega, Theta notations).
o Complexity Bounds: Best, Average, and Worst-case complexities.
o Performance Measurements: Execution time, space utilization, etc.
o Time and Space Trade-Offs: Balancing memory and speed in algorithms.
• Recursive Algorithms:
o Solving recurrence relations using substitution, recurrence tree, and Master
Theorem.
Module 2: Fundamental Algorithmic Strategies
• Techniques:
o Brute-Force: Exhaustive search (e.g., string matching).
o Heuristics: Approximate solutions when exact ones are computationally
expensive.
o Branch and Bound: Pruning suboptimal paths in problems like the TSP.
o Backtracking: Systematic search (e.g., N-Queens, Sudoku).
• Applications:
o Bin Packing: Minimizing bins for items of varying sizes.
o Knapsack Problem: Selecting items for maximum value under weight
constraints.
o Travelling Salesman Problem (TSP): Finding the shortest route visiting all cities.
Module 3: Greedy and Dynamic Programming
• Dynamic Programming (DP):
o Elements: Overlapping subproblems and optimal substructure.
o Examples:
▪ Rod Cutting: Maximizing profit from cuts.
▪ Matrix Chain Multiplication: Minimizing scalar multiplications.
▪ Longest Common Subsequence (LCS): Finding the longest subsequence
in two strings.
• Greedy Algorithms:
o Elements: Greedy choice and optimal substructure.
o Examples:
▪ Activity Selection: Maximizing non-overlapping activities.
▪ Knapsack Problem: Fractional version.
▪ Huffman Coding: Optimal prefix code generation.
o Fibonacci Heaps: Data structure for faster priority queue operations.
Module 4: Graph and Tree Algorithms
• Traversal Algorithms:
o Depth First Search (DFS) and Breadth First Search (BFS).
• Shortest Path Algorithms:
o Dijkstra's Algorithm, Bellman-Ford Algorithm, Floyd-Warshall Algorithm.
• Transitive Closure: Reachability in graphs using Floyd-Warshall.
• Minimum Spanning Tree: Kruskal’s and Prim’s algorithms.
• Topological Sorting: Ordering vertices of a directed acyclic graph (DAG).
• Network Flow: Maximum flow algorithms (Ford-Fulkerson).
Module 5: Tractable and Intractable Problems
• Computability of Algorithms: Identifying solvable problems.
• Complexity Classes:
o P: Polynomial-time problems.
o NP: Non-deterministic polynomial problems.
o NP-Complete and NP-Hard: Problems with no known polynomial-time solution.
• Reduction Techniques: Proving NP-completeness (e.g., SAT to 3-SAT).
• Standard NP-Complete Problems: TSP, Vertex Cover, etc.
Module 6: Approximation and Randomized Algorithms
• Approximation Algorithms:
o Performance Ratios: Approximation vs. optimal solutions.
o Approximation Scheme: Algorithms with adjustable error bounds.
o Examples:
▪ APPROX-VERTEX-COVER: Approximation for vertex cover.
▪ APPROX-TSP: Approximation for TSP.
▪ GREEDY-SET-COVER: Approximating set cover problems.
• Randomized Algorithms: Algorithms that use random numbers to influence results or
performance.
Module 7: Quantum Algorithms (2 hours)
• Introduction to Quantum Algorithms:
o Concepts of quantum computation.
o Examples: Shor’s Algorithm (factoring integers), Grover’s Algorithm (searching
unsorted data).
