CS305

Algorithm Design & Analysis

Powerful design paradigms: divide and conquer, greedy algorithms, dynamic programming, and graph algorithms.

10 modules · 50 lessons · Practice after every lesson

Take first

Leads to

Syllabus

  1. Module 1

    Analysis Techniques

    • Asymptotic Bounds with Multiple Parameters
    • Recurrence Solving and Akra–Bazzi Intuition
    • Amortized Analysis with Potentials
    • Lower Bounds and Adversary Arguments
    • Randomized Analysis

  2. Module 2

    Advanced Divide-and-Conquer

    • Selection and Median Algorithms
    • Fast Integer and Polynomial Multiplication
    • Fast Fourier Transform
    • Geometric Divide-and-Conquer
    • Parallel Divide-and-Conquer

  3. Module 3

    Greedy Structures

    • Exchange Arguments
    • Matroids and Greedy Correctness
    • Scheduling Algorithms
    • Huffman Coding
    • Greedy Failure Modes

  4. Module 4

    Dynamic Programming

    • State Design and Optimal Substructure
    • Sequence Dynamic Programming
    • Interval Dynamic Programming
    • Tree and Graph Dynamic Programming
    • DP Optimization Techniques

  5. Module 5

    Advanced Graph Algorithms

    • Strong Connectivity and Condensation
    • Advanced Shortest Paths
    • Minimum Cuts and Maximum Flows
    • Matching Algorithms
    • Eulerian and Hamiltonian Structure

  6. Module 6

    Network Optimization

    • Circulations with Demands
    • Minimum-Cost Flow
    • Bipartite and General Matching
    • Assignment and Transportation Problems
    • Flow Duality and Cut Certificates

  7. Module 7

    String Algorithms

    • Prefix Functions and KMP
    • Rolling Hash and Rabin–Karp
    • Tries and Suffix Structures
    • Longest Common Prefix and Range Queries
    • Pattern Matching with Automata

  8. Module 8

    Computational Geometry

    • Orientation and Robust Predicates
    • Convex Hulls
    • Line-Segment Intersection
    • Sweep-Line Algorithms
    • Voronoi Diagrams and Delaunay Triangulation

  9. Module 9

    Approximation and Online Algorithms

    • Approximation Ratios and Lower Bounds
    • Greedy Approximation
    • LP Relaxation and Rounding
    • Online Algorithms and Competitive Analysis
    • Streaming and Sketching: An Introduction

  10. Module 10

    Parameterized and Exponential Algorithms

    • Backtracking and Branch-and-Bound
    • Meet-in-the-Middle
    • Fixed-Parameter Tractability
    • Kernelization
    • Choosing Exact, Approximate, and Heuristic Methods

Start Algorithm Design & Analysis.

No setup, nothing to install. Try the first lessons before you sign up.

Start Learning
Try first