1.6 Code Samples

The code samples in this book are written in pseudocode. These should be easy enough to read for anyone who has any programming experience in any of the most common programming languages of the last 40 years. To get an idea of what the pseudocode in this book looks like, here is a function that computes the average of an array, $\ensuremath{\ensuremath{\mathit{a}}}$:

As this code illustrates, assigning to a variable is done using the $\gets$ notation. We use the convention that the length of an array, $\ensuremath{\ensuremath{\mathit{a}}}$, is denoted by $\ensuremath{\mathrm{length}(\ensuremath{\mathit{a}})}$ and array indices start at zero, so that $\ensuremath{0,1,2,\ldots,\mathrm{length}(\ensuremath{\mathit{a}})-1}$ are the valid indices for $\ensuremath{\ensuremath{\mathit{a}}}$. To shorten code, and sometimes make it easier to read, our pseudocode allows for (sub)array assignments. The following two functions are equivalent:

The following code sets all the values in an array to zero:

When analyzing the running time of code like this, we have to be careful; statements like $\ensuremath{\ensuremath{\mathit{a}}[\ensuremath{0,1,\ldots,\ensuremath{\mathrm{length}(\ensuremath{\mathit{a}})-1}]} \gets \ensuremath{1}}$ or $\ensuremath{\ensuremath{\mathit{a}}[\ensuremath{1,2,\ldots,\ensuremath{\mathrm... ...athit{a}}[\ensuremath{0,1,\ldots,\mathrm{length}(\ensuremath{\mathit{a}})-2}]}}$ do not run in constant time. They run in $O(\ensuremath{\ensuremath{\mathrm{length}(\ensuremath{\mathit{a}})}})$ time.

We take similar shortcuts with variable assignments, so that the code $\ensuremath{\ensuremath{\mathit{x}},\ensuremath{y}\gets \ensuremath{0,1}}$ sets $\ensuremath{\ensuremath{\mathit{x}}}$ to zero and $\ensuremath{\ensuremath{\mathit{y}}}$ to 1 and the code $\ensuremath{\ensuremath{\mathit{x}},\ensuremath{y} \gets \ensuremath{\ensuremath{\mathit{y}},x}}$ swaps the values of the variables $\ensuremath{\ensuremath{\mathit{x}}}$ and $\ensuremath{\ensuremath{\mathit{y}}}$.

Our pseudocode uses a few operators that may be unfamiliar. As is standard in mathematics, (normal) division is denoted by the $/$ operator. In many cases, we want to do integer division instead, in which case we use the $\ensuremath{\bdiv }$ operator, so that $\ensuremath{\ensuremath{\ensuremath{\mathit{a}}\bdiv \ensuremath{\mathit{b}}}} = \lfloor a/b\rfloor$ is the integer part of $a/b$. So, for example, $3/2=1.5$ but $\ensuremath{\ensuremath{3\bdiv 2}} = 1$. Occasionally, we also use the $\bmod$ operator to obtain the remainder from integer division, but this will be defined when it is used. Later in the book, we may use some bitwise operators including left-shift ( $\ensuremath{\ll}$), right shift ( $\ensuremath{\gg}$), bitwise and ($\wedge$), and bitwise exclusive-or ( $\ensuremath{\oplus}$).

The pseudocode samples in this book are machine translations of Python code that can be downloaded from the book's website.^1.2 If you ever encounter an ambiguity in the pseudocode that you can't resolve yourself, then you can always refer to the corresponding Python code. If you don't read Python, the code is also available in Java and C++. If you can't decipher the pseudocode, or read Python, C++, or Java, then you may not be ready for this book.

Footnotes

... website.^1.2

http://opendatastructures.org