Assess learners' ability to formulate NP-hard graph problems (e.g., Max‑Cut, graph partitioning, community detection) as quadratic/semidefinite programs, derive and analyze semidefinite relaxations (primal/dual viewpoints), implement randomized rounding schemes (e.g., hyperplane rounding), prove or compute approximation guarantees (e.g., Goemans–Williamson bound), and evaluate practical considerations such as solver selection, scaling, and empirical performance on benchmark graphs.