Nick Bennett and Todd Nordquist" />

DDC Style Guide: Pseudocode

Coding conventions for the Deep Dive Coding Java + Android Bootcamp

Overview

A number of tasks in this bootcamp focus on reading or writing pseudocode. Pseudocode is a set of practices and notational conventions used to express computational processes in a non-programming-language-specific form, but usually with the aim of facilitating or documentating implementation in one or more programming languages.

Pseudocode shares its primary aim with flowcharting: expression of a procedure in a clear, unambigous form, built on a relatively small vocabulary of symbols that a reader may be assumed to know. Pseudocode differs from flowcharting primarily in the emphasis on a textual, rather than graphical, representation of the process or algorithm. Another difference is that while flowchart symbols are mostly standardized, there isn’t a formal or de facto standard syntax for pseudocode; instead, pseudocode typically employs a combination of natural language and mathematical notation.

The guidelines and rules below have been formulated with the following aims in mind:

Note that there are recognized experts in the fields of computer science and software engineering who advocate the use of programming language code over pseudocode. For example, Robert Sedgewick, the author or co-author of several influentual texts on algorithms, has recommended the Java language for expressing algorithms, even when the intended implementation is in other languages. Nonetheless, we find significant value in the practice of writing pseudocode, and the inclusion of pseudocode in technical documentation.

Symbols & types

Keywords & operators

Grammar & syntax

Formatting

Annotations

Depending on the intended audience, additional explanatory text annotations may help the reader to understand the pseudocode. When considering the inclusion of such annotations, please follow these guidelines:

The following example includes inline explanatory annotations with some of the statements. Each such annotation is written in parentheses immediately below the statement it explains, and follows the indentation structure of the pseudocode.

Example

What follows is annotated pseudocode for a binary search over a sorted array of real numbers. Note that this—like virtually all pseudocode (or programming language code) expressions of a non-trivial procedure—is just one of many ways to express the binary search algorithm.

Binary search over a sorted array

Mathematical symbols

Beyond the basic arithmetic and logical operations, this pseudocode uses the following mathematical symbol(s):

Symbol Meaning
$\lfloor x \rfloor$ The floor of a real number $x$—i.e. the largest integer that is less than or equal to $x$.

Given

  • $D\text{: real array}$, of length $n$, to be searched: $D = (d_0, d_1, \ldots, d_{n - 1})$.

  • The elements of $D$ are in ascending order.

  • $v\text{: real}$ is the value to search for:

    • If $v$ is in $D$, its position must be returned.
    • If $v$ is not in $D$, $-(p + 1)$ must be returned, where insertion of $v$ at position $p$ would preserve the sort order.

To search for $v$ in $D$

  1. $a\text{: integer} \gets 0$.

    ($a$ is the lower inclusive bound of the search range.)

  2. $b\text{: integer} \gets n$.

    ($b$ is the upper exclusive bound of the search range.)

  3. While $a < b$:

    1. $m\text{: integer} \gets \left \lfloor \frac{a + b}{2} \right \rfloor$.

      ($m$ is the midpoint of the search range.)

    2. If $d_m = v$,

      • return $m$;

        (Done: $v$ is found at position $m$.)

      otherwise, if $d_m > v$,

      • $b \gets m$;

        ($d_m$ is too high, so $m$ is used as the new exclusive upper bound of the search range.)

      otherwise,

      • $a \gets m + 1$.

        ($d_m$ is too low, so $(m + 1)$ is used as the new inclusive lower bound of the search range.)

  4. Return $-(a + 1)$.

    ($v$ is not in $D$, but inserting $v$ at position $a$ would preserve the sorted order.)

The following Markdown, with embedded $\LaTeX$, was used to produce the rendered example above:

## Binary search over a sorted array

### Mathematical symbols

Beyond the basic arithmetic and logical operations, this pseudocode uses the following mathematical symbol(s):

| Symbol | Meaning |
|:------:|:--------|
| $\lfloor x \rfloor$ | The _floor_ of a real number $x$---i.e. the largest integer that is less than or equal to $x$. |

### Given

* $D\text{: real array}$, of length $n$, to be searched: $D = (d_0, d_1, \ldots, d_{n - 1})$.

* The elements of $D$ are in ascending order.
    
* $v\text{: real}$ is the value to search for: 

    * If $v$ is in $D$, its position must be returned. 
    * If $v$ is _not_ in $D$, $-(p + 1)$ must be returned, where insertion of $v$ at position $p$ would preserve the ascending sort order.

### To search for $v$ in $D$

1. $a\text{: integer} \gets 0$. 

    ($a$ is the lower _inclusive_ bound of the search range.)

2. $b\text{: integer} \gets n$. 
    
    ($b$ is the upper _exclusive_ bound of the search range.)

3. While $a < b$:

    1. $m\text{: integer} \gets \left \lfloor \frac{a + b}{2} \right \rfloor$. 
    
        ($m$ is the midpoint of the search range.)
    
    2. If $d_m = v$,
   
        * return $m$;
        
            (Done: $v$ is found at position $m$.)
        
        otherwise, if $d_m > v$,
        
        * $b \gets m$;
        
            ($d_m$ is too high, so $m$ is used as the new exclusive upper bound of the search range.)
        
        otherwise,
        
        * $a \gets m + 1$.
        
            ($d_m$ is too low, so $(m + 1)$ is used as the new inclusive lower bound of the search range.)
        
4. Return $-(a + 1)$.

    ($v$ is not in $D$, but inserting $v$ at position $a$ would preserve the sorted order.)