CLRS Solutions

Introduction

The word “algorithm” itself is quite interesting; at first glance it may look as though someone intended to write “logarithm” but jumbled up the first four letters. -DEK

This collection of pages contains solutions to problems in Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (3e), as well as supplementary notes on the material covered in the textbook. Occasional references are made to Sedgewick/Flajolet, Introduction to the Analysis of Algorithms (2e) and TAOCP, The Art of Computer Programming (3e) by Donald E. Knuth.

Notational Remarks

Note that the CLRS adopts the 1-first indexing convention, with containing to , inclusive. The solutions are largely written under the 0-first indexing convention, with containing to .

We also use for logarithm base 2, which the textbook denotes by .

All algorithms are implemented in Python 3, restricted to a narrow subset that more or less resembles pseudocode. As a general rule, we have chosen a longer implementation with plain-English keywords over a more elegant implementation that makes use of Python-specific features. Below, we present a brief overview of the less obvious aspects of the Python-as-pseudocode language.

for a in b iterates over each element a of b. b must be an iterator, a data structure that supports iteration.

Given integers a, b, and c, the object range(a, b, c) is an iterator that goes through

where is the largest nonnegative integer such that . If , then range(a, b, c) is the empty object.

Given an iterator b and a function f on b, the list comprehension

produces the list

where are the terms b iterates over.

Tests

Code execution examples typically take the following form:

>>> for i in range(a, b, c):
...     some code
...     if some statement:
...         more code
...     else:
...         more code
... return something
printout of the result

Occasionally, the %%timeit feature of iPython is used to compare the execution time of contrasting examples. All tests have been conducted on Intel Core i7-6700K CPU @ 4.00GHz x 8 and 62.9 GiB DDR3 RAM, running Debian GNU/Linux 9 (Stretch) 64-bit.

If you wish to run the examples yourself, visit the source code directory.

Contents