csphtp1_04.

fm Page 95 Tuesday, November 13, 2001 10:55 AM

Algorithms
Any computing problem can be solved by executing a series of actions in a specific order.
A procedure for solving a problem in terms of

1. the actions to be executed and

2. the order in which these actions are to be executed
is called an algorithm. The example that follows demonstrates the importance of correctly
specifying the order in which the actions are to be executed.
Consider the “rise-and-shine algorithm” followed by one junior executive for getting
out of bed and going to work: (1) get out of bed, (2) take off pajamas, (3) take a shower, (4)
csphtp1_04.fm Page 96 Tuesday, November 13, 2001 10:55 AM

get dressed, (5) eat breakfast, (6) carpool to work. This routine gets the executive to work
well-prepared to make critical decisions.
Suppose that the same steps are performed in a slightly different order: (1) get out of
bed, (2) take off pajamas, (3) get dressed, (4) take a shower, (5) eat breakfast, (6) carpool
to work. In this case, our executive shows up for work soaking wet.
The importance of correctly specifying the order in which actions appear applies to
computer programs, as well. Program control refers to the task of ordering a program’s
statements correctly. In this chapter, we begin to investigate the program control capabili-
ties of C#.

4.3 Pseudocode
Pseudocode is an artificial and informal language that helps programmers develop algo-
rithms. The pseudocode we present is particularly useful for developing algorithms that
will be converted to structured portions of C# programs. Pseudocode is similar to everyday
English; it is convenient and user-friendly, and it is not an actual computer programming
language.
Pseudocode is not executed on computers. Rather, pseudocode helps the programmer
“think out” a program before attempting to write it in a programming language, such as C#.
In this chapter, we provide several examples of pseudocode algorithms.
Software Engineering Observation 4.1
Pseudocode helps the programmer conceptualize a program during the program design pro-
cess. The pseudocode may then be converted to C#. 4.1

The style of pseudocode that we present consists solely of characters, thus program-
mers may type pseudocode conveniently using an editor program. Programmers can con-
vert carefully prepared pseudocode programs to corresponding C# programs easily. In
many cases, this conversion takes place simply by replacing pseudocode statements with
their C# equivalents.
Pseudocode normally describes only executable statements—the actions that are per-
formed when the pseudocode is converted to C# and executed. Declarations are not execut-
able statements. For example, the declaration

int i;

informs the compiler of the type of variable i and instructs the compiler to reserve space
in memory for this variable. This declaration does not cause any action, such as input, out-
put or a calculation, to occur when the program executes. Some programmers choose to list
variables and their purposes at the beginning of a pseudocode program.
csphtp1_05.fm Page 166 Tuesday, November 13, 2001 3:50 PM

Structured-Programming Summary
Just as architects design buildings by employing the collective wisdom of their profession,
so should programmers design programs. Our field is younger than architecture is, and our
collective wisdom is considerably sparser. We have learned that structured programming
produces programs that are easier to understand, test, debug, modify and prove correct in a
mathematical sense than unstructured programs.
Figure 5.22 summarizes C#’s control structures. Small circles in the figure indicate the
single entry point and the single exit point of each structure. Connecting individual flowchart
symbols arbitrarily can lead to unstructured programs. Therefore, the programming profes-
sion has chosen to combine flowchart symbols to form only a limited set of control structures
and to build structured programs by combining control structures in only two simple ways.
For simplicity, only single-entry/single-exit control structures are used—there is only
one way to enter and only one way to exit each control structure. To connect control struc-
tures in sequence to form structured programs, the exit point of one control structure is con-
nected to the entry point of the next control structure (i.e., the control structures are simply
placed one after another in a program). We call this process “control-structure stacking.”
The rules for forming structured programs also allow control structures to be nested.
Figure 5.23 contains the rules for forming properly structured programs. The rules assume
that the rectangle flowchart symbol can indicate any action, including input/output.

Operators Associativity Type

() left to right parentheses

++ -- right to left unary postfix
++ -- + - ! (type) right to left unary prefix
* / % left to right multiplicative
+ - left to right additive
< <= > >= left to right relational
== != left to right equality
& left to right logical AND
^ left to right logical exclusive OR
| left to right logical inclusive OR
&& left to right conditional AND
|| left to right conditional OR
?: right to left conditional
= += -= *= /= %= right to left assignment

Fig. 5.21 Precedence and associativity of the operators discussed so far.

 Fig. 5.22
Sequence Selection Repetition

if structure if/else structure while structure

(single selection) (double selection)
T F T T

structures.
F F

do/while structure
. switch structure
.
.
csphtp1_05.fm Page 167 Tuesday, November 13, 2001 3:50 PM

(multiple selection)
T break
F T
T break F
F
.
. for structure/foreach structure
.

T
break
F
T

F
break

C#’s single-entry/single-exit sequence, selection and repetition

csphtp1_05.fm Page 168 Tuesday, November 13, 2001 3:50 PM

Rules for Forming Structured Programs

1) Begin with the “simplest flowchart” (Fig. 5.24).

2) Any rectangle (action) can be replaced by two rectangles (actions) in sequence.
3) Any rectangle (action) can be replaced by any control structure (sequence, if, if/else,
switch, while, do/while, for or foreach, as we will see in Chapter 7, Arrays).
4) Rules 2 and 3 may be applied as often as you like and in any order.

Fig. 5.23 Rules for forming structured programs.

Fig. 5.24 Simplest flowchart.

Applying the rules of Fig. 5.23 always results in a structured flowchart with a neat,
building-block appearance. For example, repeatedly applying rule 2 to the simplest flow-
chart results in a structured flowchart that contains many rectangles in sequence (Fig. 5.25).
Notice that rule 2 generates a stack of control structures; therefore, we call rule 2 the
stacking rule.
Rule 3 is the nesting rule. Repeatedly applying rule 3 to the simplest flowchart results in
a flowchart with neatly nested control structures. For example, in Fig. 5.26, the rectangle in
the simplest flowchart first is replaced with a double-selection (if/else) structure. Then
rule 3 is applied again to both rectangles in the double-selection structure, replacing each of
the rectangles with a double-selection structure. The dashed boxes around each of the double-
selection structures represent the rectangles that were replaced with these structures.
Good Programming Practice 5.11
Too many levels of nesting can make a program difficult to understand. As a general rule, try
to avoid using more than three levels of nesting. 5.11

Rule 4 generates larger, more involved and deeply-nested structures. The flowcharts
that emerge from applying the rules in Fig. 5.23 constitute the set of all possible structured
flowcharts and the set of all possible structured programs.The structured approach has the
advantage of using only eight simple single-entry/single-exit pieces and allowing us to
assemble them in only two simple ways. Figure 5.27 shows the kinds of correctly stacked
building blocks that emerge from applying rule 2 and the kinds of correctly nested building
blocks that emerge from applying rule 3. The figure also shows the kind of overlapped
building blocks that cannot occur in structured flowcharts (as a result of avoiding goto
statements).
csphtp1_05.fm Page 169 Tuesday, November 13, 2001 3:50 PM

Rule 2 Rule 2 Rule 2

.
.
.

Fig. 5.25 Repeatedly applying rule 2 of Fig. 5.23 to the simplest flowchart.

Rule 3

Rule 3 Rule 3

Fig. 5.26 Applying rule 3 of Fig. 5.23 to the simplest flowchart.

csphtp1_05.fm Page 170 Tuesday, November 13, 2001 3:50 PM

Stacked building blocks Nested building blocks

Overlapping building blocks

(Illegal in structured programs)

Fig. 5.27 Stacked, nested and overlapped building blocks.

If the rules in Fig. 5.23 are followed, an unstructured flowchart (such as that in
Fig. 5.28) cannot be created. If you are uncertain about whether a particular flowchart is
structured, apply the rules in Fig. 5.23 in reverse to try to reduce the flowchart to the sim-
plest flowchart. If the flowchart can be reduced to the simplest flowchart, the original flow-
chart is structured; otherwise, it is not.
In summary, structured programming promotes simplicity. Bohm and Jacopini have
found that only three forms of control are necessary:
• Sequence
• Selection
• Repetition
Sequence is trivial. Selection is implemented in one of three ways:
• if structure (single selection)
• if/else structure (double selection)
• switch structure (multiple selection)

Fig. 5.28 Unstructured flowchart.

csphtp1_05.fm Page 171 Tuesday, November 13, 2001 3:50 PM

In fact, it is straightforward to prove that the if structure is sufficient to provide any form
of selection. Everything that can be done with the if/else and switch structures can be
implemented by combining if structures (although perhaps not as elegantly).
Repetition is implemented in one of four ways:
• while structure
• do/while structure
• for structure
• foreach structure (discussed in Chapter 7)
It is straightforward to prove that the while structure is sufficient to provide any form of
repetition. Everything that can be done with the do/while, for and foreach structures
can be done with the while structure (although perhaps not as elegantly).
Combining these results illustrates that any form of control ever needed in a C# pro-
gram can be expressed in terms of:
• sequence
• if structure (selection)
• while structure (repetition)
These control structures can be combined in only two ways—stacking and nesting. Indeed,
structured programming promotes simplicity.

for ( expression1; expression2; expression3 )

statement