Divide and Conquer, Sorting and Searching, and Randomized Algorithms Course Syllabus

This course provides a rigorous introduction to fundamental algorithm design techniques, focusing on divide-and-conquer strategies, sorting and searching methods, and randomized algorithms. Through four core modules, learners will build a strong theoretical foundation and practical problem-solving skills essential for coding interviews, systems design, and advanced study. The curriculum is structured over approximately 4 weeks with 6–8 hours of work per week, combining conceptual understanding with hands-on implementation. Lifetime access ensures flexible, self-paced learning aligned with Stanford-level rigor.

Module 1: Introduction and Asymptotic Analysis

Estimated time: 7 hours

• Analyze algorithm efficiency using Big-O notation and asymptotic growth rates
• Implement recursive algorithms like integer multiplication (Karatsuba)
• Study the recursive structure and correctness of merge sort
• Apply recurrence relations to analyze divide-and-conquer algorithms

Module 2: Divide and Conquer Algorithms

Estimated time: 7 hours

• Count inversions in an array using divide-and-conquer
• Implement Strassen’s algorithm for matrix multiplication
• Solve closest pair of points problem with recursive techniques
• Master the master method for solving recurrence relations

Module 3: Randomized Algorithms and QuickSort

Estimated time: 7 hours

• Implement and analyze randomized QuickSort
• Understand probability fundamentals in algorithm design
• Compare worst-case vs. expected running time
• Evaluate performance guarantees of randomized algorithms

Module 4: Linear-Time Selection and Graph Algorithms

Estimated time: 7 hours

• Design linear-time selection algorithms for order statistics
• Apply randomized techniques to find min-cut in graphs
• Implement and analyze graph contraction algorithms

Module 5: Final Project

Estimated time: 10 hours

• Design and implement a divide-and-conquer solution to a complex sorting or searching problem
• Incorporate randomized techniques to optimize performance
• Write a technical report analyzing algorithm efficiency and correctness

Prerequisites

• Proficiency in a programming language (e.g., Python, Java, C++)
• Familiarity with basic data structures (arrays, lists, trees)
• Basic mathematical fluency (proofs, discrete math, probability)

What You'll Be Able to Do After

• Analyze algorithm efficiency using Big-O notation and recursion
• Build efficient algorithms using divide-and-conquer techniques like merge sort and matrix multiplication
• Implement randomized algorithms including QuickSort and graph contraction
• Solve problems involving sorting, searching, and selection in linear or near-linear time
• Apply algorithmic thinking to mathematical and real-world computing challenges