Datastructures and algorithms, Part 1

Explore datastructures, algorithms, flowcharts, pseudocode, and arrays

By Jeff Friesen, JavaWorld.com, 05/02/03

Page 2 of 7

What is an algorithm?

Algorithms often associate with datastructures. An algorithm is a sequence of instructions that accomplishes a task in a finite time period. The algorithm receives zero or more inputs, produces at least one output, consists of clear and unambiguous instructions, terminates after a finite number of steps, and is basic enough that a person can carry out the algorithm using a pencil and paper. In contrast, a program is not necessarily finite: the program, such as a Web server, may never terminate without external intervention. Examples of algorithms associated with datastructures: linear-search, bubble-sort, binary-search, matrix-multiplication, linked-list-concatenation, stack-push-and-pop, and queue-insert-and-delete. (I will explore the linked-list-concatenation, stack-push-and-pop, and queue-insert-and-delete algorithms next month.)

Algorithm representation

How do you represent an algorithm? The most obvious representation: Java source code. However, writing source code before you fully understand an algorithm often leads to difficult-to-find bugs. One technique for overcoming those bugs involves flowcharts.

A flowchart is a visual representation of an algorithm's control flow. That representation illustrates statements that need to execute, decisions that need to be made, logic flow (for iteration and other purposes), and terminals that indicate start and end points. To present that visual representation, a flowchart uses various symbols, which Figure 2 shows.

What does a flowchart look like? Suppose you have a simple algorithm that initializes a counter to 0, reads characters until a new-line (\n) character is seen, increments the counter for each read digit character, and prints the counter's value after the new-line character has been read. Figure 3's flowchart illustrates this algorithm's control flow.

A flowchart's advantages include its simplicity and its ability to present an algorithm's control flow visually. Flowcharts also have disadvantages:

• Highly-detailed flowcharts can introduce errors or inaccuracies.
• Extra time is required to position, label, and connect a flowchart's symbols, even though tools speed up this process. This delay might slow your understanding of an algorithm.
• Because flowcharts are tools of the structured programming era, they aren't as useful in an object-oriented context. The Unified Modeling Language (UML) is more appropriate for providing object-oriented visual representations.

An alternative to flowcharts is pseudocode: a textual representation of an algorithm that approximates the final source code. Pseudocode is useful for quickly writing down an algorithm's representation. Because syntax is not a concern, no rules define how to write pseudocode. Consider the following example:

DECLARE CHARACTER ch
DECLARE INTEGER count = 0
DO
  READ ch
  IF ch IS '0' THROUGH '9' THEN
     count++
  END IF
UNTIL ch IS '\n'
PRINT count
END

The example above presents the pseudocode equivalent of Figure 3's flowchart. Although locating control flow in pseudocode can prove harder than finding it in a flowchart, typically, writing pseudocode takes less time than drawing a flowchart.