CS-251 — Design and Analysis of Algorithms

Course Description

This course covers the fundamental paradigms of algorithm design — divide and conquer, dynamic programming, and greedy strategies — together with the mathematical tools used to analyze algorithm correctness and asymptotic time/space complexity. Applications span sorting and searching, graph algorithms (shortest paths, minimum spanning trees, network flow), and an introduction to NP-completeness as a way of recognizing computationally hard problems.

Emphasis is placed on developing the ability to design a correct, efficient algorithm from first principles for a novel problem, and to rigorously justify both its correctness and its running time.

Course Outcomes / Objectives

Analyze the time and space complexity of an algorithm using asymptotic notation.
Design algorithms using divide-and-conquer, dynamic programming, and greedy strategies.
Apply graph algorithms to solve shortest-path, spanning-tree, and connectivity problems.
Prove the correctness of an algorithm using techniques such as induction and loop invariants.
Recognize NP-complete problems and reason about their computational intractability.

Text Books

Introduction to Algorithms (3rd ed.) — Cormen, Leiserson, Rivest & Stein (CLRS) — primary textbook
Algorithm Design — Jon Kleinberg & Éva Tardos — supplementary reference