Algorithm Design and Analysis

This course trains students to reason rigorously about computation: analyzing algorithm efficiency through asymptotic notation, proving correctness through formal methods, and decomposing unfamiliar problems by identifying structural properties and matching them to appropriate solution paradigms including Divide and Conquer, Greedy methods, Dynamic Programming, and Backtracking. The course culminates in complexity theory, where students distinguish tractable from intractable problems, verify NP membership, and establish NP-hardness through reduction from known NP-complete instances.