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.
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
b must be an iterator, a data structure that supports iteration.
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
b, the list comprehension
produces the list
where are the terms
b iterates over.
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
%%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.