Example

The algorithm Trie below is an example of how algorithms are written. It produces the trie of a dictionary $X$, finite set of words $X$. It successively considers each word of $X$ during the for loop of lines 2-10 and inserts them into the structure letter by letter during execution of the for loop of lines 4-9. When the latter loop is over, the last considered state $t$, ending the path from the initial state and labelled by the current word, is set as terminal at line 10.

Trie$(X \textrm{ finite set of words})$

    \begin{algorithmic}
    \STATE $M\leftarrow $New-automaton()
    \FOR{each string $x\in X$}
        \STATE $t\leftarrow initial(M)$
        \FOR{each letter $a$ of $x$, sequentially}
            \STATE $p\leftarrow $Target$(t,a)$
            \IF{$p=NIL$}
                \STATE $p\leftarrow $New-state()
                \STATE $Succ[t]\leftarrow Succ[t] \cup (a,p)$
            \ENDIF
            \STATE $t\leftarrow p$
        \ENDFOR
        \STATE $terminal[t]\leftarrow TRUE$
    \ENDFOR
    \RETURN{$M$}
    \end{algorithmic}

Writing Conventions of Algorithms

The style of the algorithmic language used here is relatively close to real programming languages but at a higher abstraction level. We adopt the following conventions:

Indentation means the structure of blocks inherent to compound instructions.
Lines of code are numbered in order to be referred to in the text.
The symbols // introduce a comment.
The access to a specific attribute of an object is signified by the name of the attribute followed by the identifier associated with the object between brackets.
A variable that represents a given object (table, queue, tree, word, automaton) is a pointer to this object.
The arguments given to procedures or to functions are managed by the ``call by value'' rule.
Variables of procedures and functions are local to them unless otherwise mentioned.
The evaluation of boolean expressions is performed from left to right in a lazy way.
Instructions of the form $(m_1,m_2,\dots) \leftarrow (exp_1, exp_2, \dots)$ abbreviate the sequence of assignments $m_1 \leftarrow exp_1$, $m_2 \leftarrow exp_2$, $\dots$.

125 Problems in Text Algorithms

Example

Writing Conventions of Algorithms