CSCI 256 - Fall 2026

Algorithm Design and Analysis

Home | Lectures | Problem Sets | Handouts | CS@Williams

Home

Course Description

This course is about mathematical modeling of computational problems, developing common algorithmic techniques to solve them, and about analyzing the correctness and running time of the algorithms. By clearly formulating and carefully analyzing the structure of a problem, it is often possible to dramatically decrease the computational resources needed to solve it. In addition, by analyzing algorithms you can provide provable guarantees of their performance. We will study several algorithm design strategies that build on data structures and programming techniques introduced in CS 136 and mathematical tools introduced in MATH 200. The course will roughly cover the following topics in order: graph algorithms, greedy algorithms, divide-and-conquer, dynamic programming, network flows, NP completeness and problem reductions. At the end of the course, the students should be able to:

• Analyze worst-case running time and space usage of algorithms using asymptotic analysis.
• Formulate real-world optimization problems mathematically (using concepts like sets and graphs) and apply algorithmic paradigms such as divide-and-conquer and dynamic programming to solve them.
• Identify and prove that certain computational problems are NP-hard or NP-complete, that is, show that they are unlikely to admit an efficient solution.

Readings

The primary text for the course is Algorithm Design by Jon Kleinberg and Éva Tardos, Addison-Wesley 2006. There will be secondary, optional readings from the Algorithms textbook by Jeff Erickson freely available online.

Course Evaluation and Grading

Detailed breakdown of these as well other course policy and procedures are provided in the syllabus. Also read academic integrity policies for a detailed discussion of the academic integrity policies of this course.

Course Calendar