About Course
The Analysis of Algorithms course is designed to deeply engage you with algorithmic problemsolving 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 divideandconquer approach through realworld 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
 Lecture 1: Algorithmic Problem Solving & Analysis of Algorithms
 Basic concepts of algorithms, problemsolving strategies, and algorithm efficiency.
 Introduction to algorithm complexity.
 Problemsolving examples.
 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
 Lecture 3: Time Complexity Notations
 Big O, Big Omega, Little O, Big Theta.
 Limit definitions, logarithmic functions.
 Examples and proofs.
 Lecture 4: Practical Time Complexity Analysis
 Applying time complexity concepts to various algorithms.
 Analyzing multiple problem sets for realworld relevance.
Module 3: Recursion and Recurrence Relations
 Lecture 5: Introduction to Recursion
 Fibonacci Numbers and recursive formulations.
 TriSum Series, Slow and Fast Power, Recursive Bubble Sort.
 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
 Lecture 7: Divide and Conquer – Stock Investment and Merge Sort
 Maximum Contiguous Subarray Problem.
 Iterative vs. Recursive Merge Sort.
 Lecture 8: Sorting Lower Bounds & Karatsuba Algorithm
 Karatsubaâ€™s Multiplication Algorithm.
 Lower bounds of sorting algorithms and their impact.
 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
 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
 Lecture 11: Introduction to Graphs
 Graph terminology and representations (Adjacency Matrix, Adjacency List).
 DepthFirst Search (DFS) applications.
 Lecture 12: DFS Applications in Directed Graphs
 DFS edge classification.
 Detecting strongly connected components using DFS.
 Lecture 13: Topological Sorting and BFS
 Topological sorting in directed acyclic graphs (DAGs).
 BreadthFirst Search (BFS) and its applications in shortest path algorithms.
Module 7: Advanced Graph Techniques
 Lecture 14: DFS, Strongly Connected Components & Heaps
 Kosarajuâ€™s Algorithm for SCCs.
 Introduction to heaps and priority queues.
 Lecture 15: Shortest Path Algorithms
 Dijkstra and BellmanFord algorithms.
 Handling negative weights and universal sink problems.
 Lecture 16: Minimum Spanning Trees
 Primâ€™s and Kruskalâ€™s algorithms.
 Applications of minimum spanning trees in realworld problems.
Module 8: Dynamic Programming
 Lecture 17: Introduction to Dynamic Programming
 Smart recursion and memoization techniques.
 Examples: Catalan Numbers, Fibonacci sequences.
 Lecture 18: Dynamic Programming II – Subarrays and Subsequences
 Kadaneâ€™s Algorithm for Largest Sum Subarray.
 Longest Increasing Subsequence and DAG representations.
 Lecture 19: Rod Cutting Problem
 Solving the Rod Cutting problem using topdown and bottomup approaches.
 Lecture 20: Dynamic Programming in GridBased Problems
 Edit Distance, Longest Common Subsequence.
 Efficient gridbased pathfinding with DP techniques.
Module 9: Complexity and Reductions
 Lecture 21: P vs NP and Introduction to Reductions
 Understanding the P vs NP problem.
 Basic reductions and examples from graph theory.
 Lecture 22: P vs NP and Advanced Reductions
 More on reductions and complexity classes.
Module 10: Special Topics
 Lecture 23: Geometric Algorithms
 Sweep Line Algorithm and its applications.
 Introduction to geometric problemsolving in computational geometry.
 Lecture 24: Randomized Algorithms
 Randomized QuickSort and its performance guarantees.
 Applications of randomized algorithms in realworld problems.
 Lecture 25: Number Theoretic Algorithms
 Efficient algorithms for number theory problems.
 Use cases in cryptography and computer security.
Course Content
Intro to Analysis of Algorithms

Algorithmic Problem solving and Analysis of Algorithms
01:25:56 
Loop Invariant – Iterative Codes Correctness Proof
01:11:00