# 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.