Recents in Beach

Express an Algorithm


We can express an algorithm many ways, including natural language, flow charts, pseudocode, and of course, actual programming languages.
Natural language is a popular choice, since it comes so naturally to us and can convey the steps of an algorithm to a wide audience. When we're developing algorithms, we are often working both with people who know programming and those who don't—but they all know natural language.
However, natural language has its drawbacks. It has a tendency to be ambiguous and too vaguely defined, since it has no imposed structure. That makes it difficult for others to follow the algorithm and feel confident in its correctness. Flow charts and pseudocode are more structured formats that can more precisely express an algorithm, and are popular with computer scientists and programmers.
Let's try out the more structured formats by expressing the Pig Latin algorithm from the previous article.

Flow charts

A more formal way to express an algorithm is with a flow chart, a diagram with boxes connected by arrows.
To start simple, here's a flow chart for the basic version of the Pig Latin algorithm:

Flow chart for basic Pig Latin algorithm, with 6 nodes flowing from one to the next:
  • "Start"
  • "Append "-""
  • "Append first letter"
  • "Append "ay""
  • "Remove first letter"
  • "End"
Each rectangle represents a step in the sequence, and the arrows flow from one step to the next.
This next flow chart is for the improved algorithm and uses a diamond to represent the selection phase:

Flow chart for improved Pig Latin algorithm. It starts with 3 nodes flowing from one to the next:
  • "Start"
  • "Append "-""
  • "Store first letter"
Then a diamond node has condition "first letter = vowel?".
An arrow labeled "true" leads to:
  • "Append "yay""
  • "End"
An arrow labeled "false" leads to:
  • "Append first letter"
  • "Append "ay""
  • "Remove first letter"
  • "End"
Finally, this flow chart visualizes the complete algorithm with iteration:


Flow chart for final Pig Latin algorithm. It starts with 3 nodes flowing from one to the next:
  • "Start"
  • "Store words"
  • "For word in words"
An arrow labeled "word" flows from there to a nested flow chart that starts with:
  • "Start"
  • "Append "-""
  • "Store first letter"
Then a diamond node has condition "first letter = vowel?".
An arrow labeled "true" leads to:
  • "Append "yay""
  • "End"
An arrow labeled "false" leads to:
  • "Append first letter"
  • "Append "ay""
  • "Remove first letter"
  • "End"
An arrow flows from "End" of the nested flow chart back to "For word in words".
An arrow labeled "end of words" flows from "For word in words" leading to an "End" node.
Expressing an algorithm in a flow chart allows us to visualize the algorithm at a high level, plus it forces us to think very carefully about sequencing and selection. Which arrow goes to what node? Are there missing arrows? Those are the kinds of valuable questions that can come up while translating an algorithm into a flow chart.

Pseudocode

Ultimately, most algorithms become code that actually runs on a computer. Before that happens, programmers often like to express an algorithm in pseudocode: code that uses all the constructs of a programming language, but doesn't actually run anywhere.
Here's the Pig Latin algorithm written in the style of AP CSP pseudocode:
FOR EACH word IN words
{
  APPEND(word, "-")
  letter ← FIRST_LETTER(word)
  IF (IS_VOWEL(letter)) {
    APPEND(word, "yay")
  } ELSE {
    APPEND(word, letter)
    APPEND(word, "ay")
    REMOVE_FIRST(word)
  }
}
Every programmer writes pseudocode differently, since there is no official standard, so you may run into pseudo-code that looks very different.
Expressing an algorithm in pseudocode helps a programmer think in familiar terms without worrying about syntax and specifics. It also gives computer scientists a language-independent way to express an algorithm, so that programmers from any language can come along, read the pseudo-code, and translate it into their language of choice.

Programming languages

Once we've planned our algorithm, whether in natural language, flow charts, pseudocode, or a combination, it's time to turn it into running code.


Post a Comment

0 Comments