Analysis of Algorithms

The Analysis of Algorithms course is designed to deeply engage you with algorithmic problem-solving techniques and the formal analysis of algorithms, combined with detailed, intense, and complex assignments that challenge your understanding at every step. Beginning with the fundamentals of algorithmic thinking and loop invariants, the course progressively covers time complexity, recursion, and the divide-and-conquer approach through real-world examples like stock investment and various sorting algorithms. Advanced topics such as graph theory, dynamic programming, and randomized algorithms are also covered in depth, leading up to critical concepts like P vs NP problems and geometric algorithms. Alongside these rigorous topics, each section is accompanied by comprehensive tutorials that guide you through the complex assignments, ensuring you grasp both the theoretical and practical aspects of algorithm design and analysis. This course is perfect for those looking to master the intricacies of algorithms and computational efficiency.

Module 1: Introduction to Algorithmic Thinking

1. Lecture 1: Algorithmic Problem Solving & Analysis of Algorithms
   • Basic concepts of algorithms, problem-solving strategies, and algorithm efficiency.
   • Introduction to algorithm complexity.
   • Problem-solving examples.
2. Lecture 2: Loop Invariant and Iterative Code Correctness
   • Correctness of algorithms using loop invariants.
   • Example: Binary Search Overflow Handling.
   • Bubble Sort, Selection Sort, and Insertion Sort proofs using loop invariants.

Module 2: Understanding Time Complexity

3. Lecture 3: Time Complexity Notations
   • Big O, Big Omega, Little O, Big Theta.
   • Limit definitions, logarithmic functions.
   • Examples and proofs.
4. Lecture 4: Practical Time Complexity Analysis
   • Applying time complexity concepts to various algorithms.
   • Analyzing multiple problem sets for real-world relevance.

Module 3: Recursion and Recurrence Relations

5. Lecture 5: Introduction to Recursion
   • Fibonacci Numbers and recursive formulations.
   • TriSum Series, Slow and Fast Power, Recursive Bubble Sort.
6. Lecture 6: Solving Recurrences and the Master Theorem
   • T(N) = aT(N/b) + Nc and its applications.
   • Examples of recursive algorithms.
   • Tower of Hanoi and QuickSort recurrences.

Module 4: Divide and Conquer Strategies

7. Lecture 7: Divide and Conquer – Stock Investment and Merge Sort
   • Maximum Contiguous Subarray Problem.
   • Iterative vs. Recursive Merge Sort.
8. Lecture 8: Sorting Lower Bounds & Karatsuba Algorithm
   • Karatsuba’s Multiplication Algorithm.
   • Lower bounds of sorting algorithms and their impact.
9. Lecture 9: QuickSort – Randomized and Deterministic
   • Partitioning techniques in QuickSort.
   • Randomized partitioning and finding the Kth smallest element.

Module 5: Pseudo Algorithms and Advanced Techniques

10. Lecture 10: Pseudo Algorithms
    • Stable Count Sort, Radix Sort, Bucket Sort.
    • Applications in Range Searching, Skyline, and Closest Pair Problems.

Module 6: Graph Algorithms and Applications

11. Lecture 11: Introduction to Graphs
    • Graph terminology and representations (Adjacency Matrix, Adjacency List).
    • Depth-First Search (DFS) applications.
12. Lecture 12: DFS Applications in Directed Graphs
    • DFS edge classification.
    • Detecting strongly connected components using DFS.
13. Lecture 13: Topological Sorting and BFS
    • Topological sorting in directed acyclic graphs (DAGs).
    • Breadth-First Search (BFS) and its applications in shortest path algorithms.

Module 7: Advanced Graph Techniques

14. Lecture 14: DFS, Strongly Connected Components & Heaps
    • Kosaraju’s Algorithm for SCCs.
    • Introduction to heaps and priority queues.
15. Lecture 15: Shortest Path Algorithms
    • Dijkstra and Bellman-Ford algorithms.
    • Handling negative weights and universal sink problems.
16. Lecture 16: Minimum Spanning Trees
    • Prim’s and Kruskal’s algorithms.
    • Applications of minimum spanning trees in real-world problems.

Module 8: Dynamic Programming

17. Lecture 17: Introduction to Dynamic Programming
    • Smart recursion and memoization techniques.
    • Examples: Catalan Numbers, Fibonacci sequences.
18. Lecture 18: Dynamic Programming II – Subarrays and Subsequences
    • Kadane’s Algorithm for Largest Sum Subarray.
    • Longest Increasing Subsequence and DAG representations.
19. Lecture 19: Rod Cutting Problem
    • Solving the Rod Cutting problem using top-down and bottom-up approaches.
20. Lecture 20: Dynamic Programming in Grid-Based Problems
    • Edit Distance, Longest Common Subsequence.
    • Efficient grid-based pathfinding with DP techniques.

Module 9: Complexity and Reductions

21. Lecture 21: P vs NP and Introduction to Reductions
    • Understanding the P vs NP problem.
    • Basic reductions and examples from graph theory.
22. Lecture 22: P vs NP and Advanced Reductions
    • More on reductions and complexity classes.

Module 10: Special Topics

23. Lecture 23: Geometric Algorithms
    • Sweep Line Algorithm and its applications.
    • Introduction to geometric problem-solving in computational geometry.
24. Lecture 24: Randomized Algorithms
    • Randomized QuickSort and its performance guarantees.
    • Applications of randomized algorithms in real-world problems.
25. Lecture 25: Number Theoretic Algorithms
    • Efficient algorithms for number theory problems.
    • Use cases in cryptography and computer security.