Chapter 2

INTRODUCTION TO CONSTRUCTION OF
ALGORITHMS

2.1 Definition of Algorithm

The first step to solving a problem through a program

computer is the precise definition of the problem. After this step, the solution is planned.
of the problem through writing an algorithm. An algorithm consists of a
a sequence of well-defined steps (instructions) that receive some values like
inputs produce some values as output. When executed, the instructions of
an algorithm solves a given problem. Furthermore, these instructions do not
they must be ambiguous and every algorithm must terminate.

A very common analogy that helps in understanding the concept of an algorithm is

that between algorithm and culinary recipe. In a culinary recipe, the ingredients and
utensils used (for example, eggs, wheat flour, baking dish) make up the input
and the final product (for example, a cake) is the output. The preparation method specifies a
sequence of steps that inform how to process the input in order to produce the output
desired. Although the analogy between algorithm and recipe is valid,
hardly a recipe can be considered an actual algorithm, as it typically
cooking recipes are imprecise in specifying ingredients (input) and in
description of the preparation method (processing). In addition, culinary recipes, in
most of the time, they require inferences and decision-making by those who
we implement an algorithm that should not require any type of inference or decision making
of decision by a computer that, ultimately, will execute it.
Computers simply do not have such capabilities.

Rarely is an algorithm written to accept a limited set of values. More

commonly, it is written to handle various input cases. For example, a
algorithm to solve quadratic equations can receive the equation as input
x2- 5x + 6and produce as output the roots2e3This same algorithm would serve
to solve the equationx2-4x + 4producing2as output. In this example, the
Equations are input cases of the exemplified algorithm. In everyday life, a case of
entry is simply referred to as entry.
Chapter 2 Introduction to Algorithm Construction 2

An algorithm is correct when, for every input case, it stops with the output.
correct. An incorrect algorithm may not stop when it receives a given input case
entry or can stop presenting a result that is not correct.

There can be several functionally equivalent algorithms that solve the same
problem. Equivalent algorithms can use more or fewer resources, have a number
greater or fewer instructions and so on. Again, the analogy between
algorithm and culinary recipe is valid here: some recipes require less effort and
ingredients of what others that result in the same dish.

It is important to emphasize that not every problem has an algorithm. For example, not
There is an algorithm for the financial enrichment problem (legal or illegal). This
the problem does not have an algorithm because it is not even well defined, but there are problems
which are well defined but do not have complete algorithms, such as, for example,
play chess. It is interesting to note that problems that are solved trivially
by human beings, such as speaking a natural language or recognizing a face, neither do
they have algorithmic solutions. On the other hand, problems that are relatively difficult for
humans, like multiplying two numbers with ten digits each, have
relatively trivial algorithms.

2.2 Divide and Conquer Approach

The most common approach used in algorithm construction is called divide

and conquer. In this approach, a problem is successively divided into subproblems.
increasingly smaller until they can be solved trivially. The solutions to the
subproblems are then combined to result in the solution to the original problem.
This problem-solving strategy is also known as the approach to
successive refinements.

The divide and conquer approach is not used specifically in the field of programming.
or computing. In other words, this problem-solving approach is generic and
frequently used even for everyday problems. Therefore, its use will be
exemplified below through the resolution of a non-computational problem.

Suppose you are having friends over for lunch and want to serve them a
delicious bedribs in coconut sauce. So, thealgorithm to be followed to solve this
the problem can be described as follows1:

Shrimp in Coconut Sauce Algorithm

1
The author thanks nutritionist and chef Suzana Brindeiro for the recipe and the secrets of
executions that are not revealed here.
Chapter 2 Introduction to Algorithm Construction 3

Ingredients and equipment (Input):

• 1kg of shelled shrimp
• 1 liter of coconut milk
• 1 medium onion
• 2 peeled and seeded tomatoes, chopped
• ½ medium green bell pepper
• 1 bunch of tied cilantro
• 4 tablespoons of olive oil
• 2 tablespoons of annatto
• Frying pan
• Panela
• Wooden spoon or polypropylene
• etc. (to shorten the example)

Output:
• Shrimp in coconut sauce

Preparation (Steps or Instructions):

Chop the onion into small pieces.
2. Remove the skin from the tomato and chop it.
3. Cut the bell pepper into large pieces that allow
the removal after cooking.
4. Obtain the coconut milk.
5. Make the colored olive oil.
Sauté the shrimp and set aside.
7. Sauté the onion, bell pepper, and tomato.
8. Add the coconut milk and the red olive oil
to the sauté.
9. When the mixture boils, add the shrimp.
10. Let it cook on low heat for about 10 minutes.
minutes.
11. (Optional) Remove the cilantro and the pieces of
bell pepper

Since kitchen receptions are in fashion and your friends are close, you invite them.
to help you in the preparation of the dish. Now, suppose you assign task 1 to a
from his friends and that he does not know how to execute it (i.e., the task is not trivial for this)
friend). So, you will have to specify this task in more detail for him.
be able to execute it. In other words, you will have to refine task 1 into
subtasks in such a way that your friend knows how to execute each one of them. In
Chapter 2 Introduction to Algorithm Construction 4

programming, the corresponding analogy to this refinement of tasks is that the

the programmer must refine (i.e., divide) the steps of an algorithm until each step
resulting fromsuccessive divisionsit can be represented by a single instruction in a
high-level language2.

Step 1 of the algorithm presented above can be refined to result in the following
sequence of substeps:

1.1 Cut the onion in half lengthwise.

1.2 Remove the onion skin, leaving the stem.
1.3 For each band of cebolafação that follows:
1.4.1 Place the flat side of the onion band down on the
cutting board.
2.4.1 Cut the onion into high strips, then with the knife in
horizontal, apply two longitudinal cuts
from the opposite end to the stalk to close to the
cut in such a way as to divide the onion into three parts,
otherwise apply a cut in such a way as to divide the
band in two parts.
3.4.1 With the knife vertically, make cuts
longitudinally along the onion band in order to divide
I love thin strips.
4.4.1 Hold the onion strip with four fingers, without
include the thumbs, turned inward in a way
that the onion stem is facing the
inside of the hand.
5.4.1 With the knife close to the fingers and in position
vertical, while the onion band is not
cut close to the stem apply cuts
verticals.

Note that step 1.3.2 presents two actions conditioned by the format of the onion (i.e., to
problem input) and only one of these actions should be executed. The
The conditions of step 1.3.2 are the facts that follow the two words and the actions come.
after the words then and not. Conditional actions are very common in programming.
High-level languages provide facilities for coding them.

Steps 1.3 and 1.3.5 presented above involve repetitive actions that have
analogous instructions in programming. For example, step 1.3.5 represents a
loop structure of the type: while a given condition is not met execute
repeatedly a certain action. In the given example, the stopping condition of the

2
A programmer with some experience does not need as much refinement.
Chapter 2 Introduction to Algorithm Construction 5

repetition is the fact that the onion is cut close to the stem and the action to be
repeated is the cutting of the onion.

All the other steps of the prep modethey canto be refined according to the
culinary intimacy of the one who will execute them3In the best case, the friend who will
executing one of the steps is an experienced chef and does not need further
details to execute the task. On the other hand, another friend who has never boiled water
requires that the task to be performed is well detailed. These facts correspond.
in programming: just like a chef, to create a program, a
an experienced programmer needs few details in the description of an algorithm,
while a beginner programmer needs to have a much more refined algorithm in
details.

Before concluding this culinary adventure, a very important analogy arises.

necessary. Suppose that one of your guests is allergic to shrimp. Then,
you decide to serve fish in coconut sauce to this friend. The fact is that the recipe
this dish is similar to the shrimp recipe presented above, except for the following
facts:

• Ingredients: replace the shrimp with a firm-textured fish in

posts (e.g., golden or mackerel).
• Result: fish in coconut sauce, instead of shrimp in sauce
of coconut.
• Preparation - replace steps 5 and 8 with:
Fry the fish and set aside.
8. When the mixture boils, add the fish.

Wisely, due to the proximity of the two recipes, you will not repeat the steps that are
common to them. That is, the best way to solve this new problem is to take advantage of
part of what was done in the previous problem. In this specific case, all the
ingredients and steps used in the preparation of shrimp sauce can be reused
in the creation of the new dish. Therefore, the two best alternatives for the cook are:
reduce the amount of shrimp or increase the amount of ingredients used in
coconut sauce, so that there is enough sauce for it to create the new recipe. In
In any case, the cook will be reusing part of the work that has already been done.
done and this has an analogous in programming that, unfortunately, is not properly
explored in teaching this subject: code reuse.

3
In fact, even obtaining the ingredients and equipment may require detailing. By
For example, the choices of shrimp and coconut type are critical in this recipe.
Chapter 2 Introduction to Algorithm Construction 6

An experienced programmer very rarely starts to write a program from

from scratch. That is to say, most of the time, he always finds a program that he already
he wrote that there may be reusable parts in the construction of a new program.

2.3 Algorithmic Language

An algorithm can be written in any language, just like in a natural language (e.g.,
Portuguese) or in a programming language (e.g., C). By the way, a program of
a computer consists exactly of an algorithm (or collection of algorithms) written
in a programming language. Pure natural language is rarely used in writing
of algorithms as it presents inherent problems, such as verbosity, imprecision,
ambiguity and context dependency. The use of a programming language of
high level is also not convenient for writing an algorithm, because the programmer
You need to divide your attention between this task and details about language constructions.
in which the algorithm will be written.

The objective here is the writing of algorithms that, ultimately, can become
programs. However, writing algorithms in a programming language imposes serious
difficulties for those who have not yet gained practice in algorithm construction
they do not know the programming language used well. Thus, when trying to write
an algorithm in a programming language, the learner would be involved in two
simultaneous tasks: the resolution of the issue at hand (i.e., the construction of
algorithm itself) and the use of a language that he still does not master. An idea that
facilitates the programmer's life consists of using in the construction of algorithms a
language close to the programmer's natural language, but that incorporates
similar constructions to those commonly found in languages
programming. A language withthese characteristicsis called language
algorithm or pseudolanguage4In order to serve the purpose for which it is intended, a
algorithmic language still needs to be much easier to use than any
programming language.

Pseudocode is a description of an algorithm written in an algorithmic language.

Pseudocode is directed towards people, not machines.
Pseudocode is used not only by beginner programmers but also by
experienced programmers, although they are capable of writing programs
relatively simple without the aid of pseudocode.

Using an algorithmic language, the development of a program is divided

in two major phases, each of which will be detailed later on:

4
An alternative resource for the use of pseudocode is flowcharts. This alternative already
It was widely used but is now out of use and will not be studied here.
Chapter 2 Introduction to Algorithm Construction 7

1. Construction of the algorithm using algorithmic language. In this phase, the

the programmer should essentially be involved with reasoning that
guides the writing of the algorithm, since ideally, the language used in the
writing of the algorithm should not impose any difficulty for the
programmer. For example, if a certain step of the algorithm requires
the reading of an integer value to be stored in a variable x, the
programmer must write:

write(x)

2. Translation of the algorithm into a programming language. Here, the

the programmer's concern should no longer be the reasoning involved
in building the algorithm. That is, at this stage, the programmer will use
just your knowledge about a programming language for
transform your algorithm into a program. For exampleplo, at this stage, the
the writing instruction presented above would be translated in C as5:

printf("%d", x);

The next sections of this chapter describe an algorithmic language that takes into
considering what was presented in this section. The learner should note that not
it is necessary to strictly follow the specifications of this language, as it was
As exposed above, it is an artificial language that aims to assist you in
writing algorithms and the subsequent translation of the algorithm using a language of
programming. For example, you can, if you wish, replace the output statement:

write(x)

by

print(x)

without any problems. But be careful with your language customizations

algorithmic so that they do not hinder the purposes of the language.

There is no standard or rigid syntax for pseudocode or pseudocode, but

there are recommendations, such as:

• Written instructions in pseudocode can include descriptions in

natural language or mathematical notation.

5
Note how it would be much more complicated for the programmer if he had to write the
algorithm in C from the beginning of the development process. In this example, the instruction
write(x)it's much simpler thanprintf("%d", x).
Chapter 2 Introduction to Algorithm Construction 8

• The resulting algorithm should be easier to understand than a program.

written in any programming language.
• The pseudolanguage must be independent of programming language and
of the environment in which a program based on pseudocode will be
built, but should facilitate translation in a programming language.
• Details that are not essential for understanding the algorithm must
they need to be declared only when
your types are not obvious.
• Blocks and function calls that make up the body of a structure of
controls can be replaced by sentences in Portuguese.
• The divide and conquer approach can be applied successively until
each subproblem can be considered trivial. The amount of detail
Instructions depend on how much the programmer understands the problem.
Typically, novice programmers need much more detail about
that experienced programmers. The detailing of an algorithm must be
enough to allow the writing of the corresponding program. If the
pseudocode is hard to read or translate into a programming language,
There must be something wrong with the level of detail adopted.

2.4 Variables and Assignments

The programming language represents the content of a through a name.

continuous space in memory (i.e., a set of neighboring cells). Thus, a
variable is characterized by three attributes: address, content (or value) and name (or
identifier), as illustrated in Figure 1.

Figure 1: A Variable with Four Cells

Note that, as illustrated in Figure 1, when a variable occupies more than one cell
In memory, its address corresponds to the address of the first cell.

In programming, the name of a variable represents its content. Thus, for

example, when a variable appears in an expression like in:

y+5
Chapter 2 Introduction to Algorithm Construction 9

it is understood that it is your current value that is being added to5.

Informally, a simple expression is a combination of an operator, which

represents an operation to be performed, and the operands on which the operation acts.
An operand can be represented by a constant value or a variable.
Considering the last example, the operator is represented by the symbol '+' and the
operands are y (a variable) and 5 (a constant).

In a more complex expression, the operands of an operator can also be

expressions. For example, in the expression:

x+y*2

the operands of the operator '+' are the variablexand the expressiony * 2In Section 2.5,
Expressions and operators will be explored in greater detail.

An assignment instruction represents the act of a variable receiving the value of a

constant, the value of another variable or the result of evaluating an expression. A
assignment in algorithmic language will be represented by the symbol←, with the variable
that suffers the assignment to the left of the arrow and the value assigned to it (represented by a
constant, variable or expression) on the right. For example, if it is desired to express the
idea of a variablexreceives the resulting value of the sumy + 2, whereyit's another
variable, it is written in algorithmic language:

x← y + 2

This assignment instruction reads as: x receives the value of y plus two.

Now, consider the following assignment example:

x←x+2

In this case, the variablexreceives the value that she had before6of the assignment to occur
added to2.

Most high-level programming languages require that any variable be

declared before its first use. Declaring a variable simply means
inform what your type is. This is done by preceding the variable name with its
respective type.

6
This occurs because, in an assignment in which a variable receives the resulting value from the
evaluation of an expression, the expression must be evaluated before the assignment happens.
Chapter 2 Introduction to Algorithm Construction 10

In the algorithmic language presented here, three types are used:

• whole ([Link] 2.5.2)

• real(Section 2.5.2)
• boolean ([Link] 2.5.4)

When the type of a variable is not easily inferred from the context, it is advisable
include your declaration at the beginning of the algorithm where the variable is used. Declare
variables in an algorithm are also advantageous for translating the algorithm into a program
because it prevents the programmer from forgetting to do it.

Examples:

boolean b
whole x
real y, z

Note that when two or more variables are of the same type, like the variablesy
ez from the previous example, they can be declared in a summarized way by separating them by
commas and preceding them with the name of the common type.

2.5 Operators and Expressions

There are three basic types of expressions in programming:

• Arithmetic expressions. The operators represent operations.

usual arithmetic, and the operands and results of their evaluations are
numeric values.
• Relational expressions. The operators represent operations of
comparison between numerical values that result in a value
true or false. These values are called constants or
logical values.
• Logical expressions. The operators represent logical connectives. The
operands are constants, variables, or logical expressions. The result
of a logical expression is a logical constant.

2.5.1 Operator Properties

Chapter 2 Introduction to Algorithm Construction 11

Before exploring in detail the three types of expression mentioned above, there will be
described properties that are common to all operators.

Aridity

The arity of an operator is the number of operands that the operator accepts.
In algorithmic language, operators are divided into two categories of arity:

• Unary operators are operators of arity one (i.e., they require

only one operand.
• Binary operators are operators of arity two (i.e., that require
two operands)

For example, the addition operator is a binary operator (i.e., it has arity two).

Result

Any operator, when applied to its operands, results in a value. This value is the
result of the operator. For example, the result of the addition operator is the value obtained
when its two operands are added.

Precedence

The precedence of an operator determines the relative order in which it is applied.

in an expression containing operators considered distinct with respect to this
property. That is, when in an expression, an operator has higher precedence than
Moreover, the operator with the highest precedence is applied before the operator with the lowest.
precedence.

Operators are grouped into precedence groups, so that, within each group
of precedence, the operators have the same precedence. On the other hand, operators that
belong to different precedence groups have different precedences. For
For example, the addition and subtraction operators are part of the same group of
precedence and the same occurs with the multiplication and division operators. But, the
the precedence group that includes multiplication and division has higher precedence than
that the precedence group of addition and subtraction. Thus, in the expression:

2*5 + 4

the multiplication operator (“*”) is applied before the addition operator (“+”).
Chapter 2 Introduction to Algorithm Construction 12

Associativity

Just like the property of precedence, associativity is used to decide the

order of application of operators in an expression. But, while precedence is used
with operators of different precedences, associativity is used with
operators of the same precedence or with occurrences of the same operator. There are
two types of associativity:

• Left associativity - the left operator is applied before the right one.
right operator.
• Right associativity - the right operator is applied before the operator
from the left.

For example, in the expression8/2/2the first division operator is applied before the
second, because the division operator is left associative. In this case, the
the result of the expression is2(If the division operator had right associativity, the
result would be8.)

2.5.2 Operators and Arithmetic Expressions

The arithmetic operators used in programming correspond to the usual operations.

in mathematics (for example, addition, subtraction, multiplication, etc.). However, not
they always use the same notation seen in mathematics. For example, in
In mathematics, the multiplication operator can be represented by a dot (by
example,a.b) or by the simple juxtaposition of operands (for example,ab) while
In programming, this operator is usually represented by "*" (asterisk).

The most common arithmetic operators in programming are presented in Table 1.

together with their respective meanings.

OPERATOR meaning
- unary minus (i.e., sign inversion)
+ soma
- subtraction
* multiplication
/ integer division
Chapter 2 Introduction to Algorithm Construction 13

% remainder of integer division

Table 1: Arithmetic Operators

The operands of any arithmetic operator must be numeric. There are two types.
basics of numbers in programming: integers and floating point. The latter
correspond approximately to real numbers in mathematics. Except for the
operator "%", whose operands must always be integers, the operands of any
Other arithmetic operators can be integers or floating point. When the
If the operands of an arithmetic operator are of the same type, the result will be of this type.
same type. If one of the operands is floating point, the result will also be of this type.
type. For example:

Expression Result
2.5 + 4 6.5
6.5 6.5
2+4 6
5%2 1
5/2 2
2.5 2.5

There are arithmetic functions that can be used to compose expressions.

arithmetic. For example, the functionsquare rootresulting in the square root of a number that it
receives as input (for example,2results in2Languages of
programming usually provides the user with a vast collection of such functions that
include, for example, trigonometric functions, exponential functions, etc. When they appear
In an expression, these functions are evaluated before the application of any operator.

Table 2 below presents the properties of precedence and associativity of

arithmetic operators:

OPERATOR PRECEDENCE Associativity

(unary) High (first applied) To the right
*, /,% ↓ On the left
+, – (binary) Downgrade (applied last) To the left

Table 2: Precedences and Associativities of Arithmetic Operators

Chapter 2 Introduction to Algorithm Construction 14

In the above table, operators on the same line have the same precedence. Therefore,
when such operators are found together in the same arithmetic expression, the
the leftmost operator is applied first, except in the case of the inversion operator
of signal that has right associativity.

Note that the use of parentheses changes the properties of precedence and associativity
two operators. For example, in the expression(2 + 3)*4the parentheses make it so that the
the addition operation should be applied before multiplication (i.e., the precedence of addition
becomes greater than the precedence of multiplication). Another example:8/(2/2)
results in8because parentheses increase the precedence of the second operator
division.

2.5.3 Operators and Relational Expressions

Relational expressions formed by relational operators and operands

numerical, resulting in a value, called logical value, which can betrue
orfalseAn operand of a relational operator can be a numeric constant,
a variable with numeric content or an arithmetic expression.

The commonly used relational operators inprogramming and the respective

results obtained from their applications are presented in Table 3 below7.

EXPRESSION TRUE WHEN

A=B A is equal to B
A?B A is different from B
A>B A is greater than B
A?B A is greater than or equal to B
A<B A is smaller than B
A?B A is less than or equal to B

Table 3: Relational Operators

Note that a relational expression corresponds to a question whose answer is yes or no.
no. When the answer to this question is yes, the result of the expression istrue;
when the answer to this question is no, the result of the expression isfalse. For

7
Evidently, the result of a relational operator is false when it is not true.
Chapter 2 Introduction to Algorithm Construction 15

example2 is greater than 3corresponds to the question: Is two greater than three? whose answer is
obviously not, therefore, the expression2 > 3results infalse.

As mentioned before, an operand of a relational expression can be

an arithmetic expression. This means that one can have expressions containing
arithmetic and relational operators. For example,2 + 3 > 4 * 6it's an expression
containing two arithmetic operators (+ and*) and a relational operator (>), and it is
interpreted as: two plus three is greater than four times six? Note that, for this
expression to have this interpretation, it is implied that the operations of addition and multiplication
must be carried out before the relational operation greater than. That is, the operators of
Addition and multiplication should have higher precedence than the greater than operator.

In general, all relational operators are part of the same group of

precedence and their precedence is lower than the precedence of any operator
arithmetic. This means that in an expression containing arithmetic operators and
In relational expressions, arithmetic operators are applied before relational operators.

It is important to note that, due to the approximations used by computers in

floating point number representations, it is not convenient to compare these
numbers using relational operators. For example, if you write the expression
relational

2.5 = 5.0/2.0

it may be that you obtainfalseas a result. This occurs because the division5.0/2.0
can result in something like2.499999999999999or maybe,2.500000000000001,
and not exactly in2.5, as would be intuitively expected.

2.5.4 Logical Operators and Expressions

Expressions containing relational operators are examples of expressions

logical. A logical expression (also known as a boolean expression) is
simply an expression that results in a logical value ([Link]).

A logical variable (or boolean variable) is a variable that can assume only
a logical value. A boolean variable can be directly assigned a constant
logic or the resulting value from the evaluation of a Boolean expression, as shown by the
examples to follow.

boolean bol1, bol2

bol1← false
bol2← 2 > 3
Chapter 2 Introduction to Algorithm Construction 16

Constants, variables, and boolean expressions can be combined with each other through
logical operators. There are three most commonly used logical operators in
programming

• Negation - unary operator represented bynoin pseudolanguage

• Conjunction – binary operator represented bye in pseudolanguage
• Disjunction - binary operator represented byyouin pseudolanguage

The possible results of the applications of these operators are typically presented
in tables calledtruth tablesThe truth tables for the operators not,
the presentations are shown below8.

Operator1 noOperating1
true false
false true

Operand1 Operand2 Operating1e Operating2

true true true
true false
false true false
false false false

Operand1 Operand2 Operating1youOperando2

true true true
true false true
false true true
false false false

The following conclusions can be derived from the observations of the truth tables above:

8
In these tables,operando1eoperating2they can correspond to any constant, variable
the boolean expression.
Chapter 2 Introduction to Algorithm Construction 17

• The result of the negation of an operand istruewhen the

operand isfalseand vice versa.
• Instead of memorizing the entire truth table of the operatore, it is necessary
just to remember that the result ofoperand1 and operand2é
trueonly when each of the operands istrue; em
any other situation the application of this operator results infalse.
• Instead of memorizing the entire operator tableyou, it is only necessary
remember that your application results infalseonly when your two
operands result infalse.

Example:

booleanobol1, bol2, bol3, bol4, bol5, bol6

bol1← 2 = 5
bol2← false
bol3← 10≤ 10
bol4← nãobol1
bol5← bol2ebol3
bol6← bol2oubol3

Exercise: What are the values assumed by logical variablesbol1, bol2, bol3,
bol4, bol5ebol6from the last example?

As mentioned above, an operand of a logical expression can be a

relational expression. On the other hand, a relational expression can have an expression
arithmetic as an operand. Therefore, it is possible to have, in the same expression,
arithmetic, relational, and logical operators. For example:

(2 + 4 < 7) and not (x = 10)

it is a perfectly legal expression. Thus, it is necessary to define a table of

precedentthat considers everyonethese operators. This general precedence of
operators are presented in Table 4.

OPERATOR PRECEDENCE
(unary)no High (applied first)
*, /,% ↓
+, - (binary) ↓
relational operators (=,≠, ≥, etc.) ↓
Chapter 2 Introduction to Algorithm Construction 18

e ↓
or Low (last applied)

Table 4: General Precedence of Operators

Exercise: If the value of the variablex for5at the moment of evaluating the expression
(2 + 4 < 7) and not (x = 10), the result of this expression will be true.
Show, step by step, how this result is obtained.

2.5.5 Functions

In addition to the elementary operations presented above, high-level languages

they typically offer numerous functions that perform more elaborate evaluations. The
The operands on which these functions operate are typically referred to as parameters.

Some functions with their most commonly used names in programming

they are:

• sqrtcalculate the square root of the operand (parameter)

• powcalculate the exponential of the first parameter raised to the second
• randresults in a randomly chosen number (random number)

When a function appears in an expression, its execution has a higher priority than that of
that the application of any operator presented above. When there is an occurrence of more
from a function in an expression, functions are evaluated from left to right.

2.5.6 Use of Parentheses

As seen earlier, one can modify precedence and associativity of

operators through the use of parentheses. Sometimes the use of parentheses is mandatory
to give the expression the meaning that one intends for it to have. For example, if you
pretends that the expression:

bol1oubol2ebol3oubol4

it should be interpreted as a conjunction of two disjunctions; i.e., it has the meaning:

(bol1orbol2)e(bol3orbol4)
Chapter 2 Introduction to Algorithm Construction 19

you have to write it exactly as in the previous line (i.e., with the parentheses);
otherwise, the original expression would be interpreted as:

bol1ou(bol2ebol3)oubol4

given that the operator has higher precedence than the precedence of the operatoryou9.

The use of parentheses is also recommended in the following cases:

• When there is a doubt related to the precedence between two or more

operators.
• To facilitate the reading of complex expressions.

Expressions involving relational and logical operators are particularly vulnerable

and susceptible to errors in programming. The judicious use of parentheses to improve the
the legibility of these expressions is a preventive weapon against errors.

As final advice, remember that redundant (but not excessive) use of

Parentheses do not hinder the understanding of an expression, but the lack of parentheses does.
can result in an interpretation that is not intended. In other words, it is better
it is better to be redundant and have a functioning program than to try to be succinct and have one
defective program.

2.6 Input and Output

Frequently, a computer program needs to obtain data using some means.

as input (for example, keyboard, disk). In algorithmic language, it is used to
instructionLeiafor obtaining data for an algorithm. This instruction always comes
accompanied by a list of variables that represent the memory locations where the
read data will be stored. Thus, an instruction like:

read(x1, x2, ..., xn)

indicates how many data will be read and then stored as the contents of the variablesx1,
x,2 ..., x n.

An instruction for outputting data from an algorithm to some output medium (by
example, screen, printer) has the following format in algorithmic language:

9
Be careful with logical expressions, as they represent a very common source of error.
in programming (even for experienced programmers!).
Chapter 2 Introduction to Algorithm Construction 20

write1, and2, ..., andtranslatedText)

In this instruction,e1, e2, ..., en they represent the information that will be written in the middle of
output and eacheiit can be:

• A constant value that will be written exactly as it is.

• A variable whose content will be written.
• An expression that will be evaluated and whose resulting value will be written.
• A string (see below).

A character string consists of a sequence of characters between

quotes. For example,Good Luckit is a string. When a string
characters appear in an instruction write all of its characters except the quotes
that delimit the chain are written in the order they appear.

2.7 Control Structures

The execution flow of an algorithm consists of the sequence and the frequency (i.e.,
number of times) that the algorithm instructions are executed. In the natural flow
execution of an algorithm, each instruction is executed exactly once and in the
order in which it appears in the algorithm.

Control structures are instructions that allow the programmer to change the flow.
natural execution of an algorithm. They are divided into three categories:

• Conditional deviations change the execution sequence of an algorithm

causing the diversion of the execution flow of the algorithm to a
determined instruction. This deviation is conditioned on the resulting value of
evaluation of a logical expression.
• Unconditional deviations are similar to conditional deviations, but the
deviations caused by them are independent of the evaluation of any expression.
• Repetitions (loops of repetition) change the frequency with which one or
more instructions are executed.

Some control structures have been informally presented in the example of

section 2.2 algorithm. The following will present a branching instruction
Chapter 2 Introduction to Algorithm Construction 21

conditional and two repetition instructions used by the algorithmic language. Deviations
Unconditional ones will be presented later.

2.7.1 Conditional Deviation if-then-else

The instructionit-so-otherwisehas the following format:

if (condition) then instructions1 else instructions2

Where:

• condition represents a logical expression that determines where the

diversion will be made.
• instructions represent a set of one or more instructions for where the
diversion will be carried out if the resulting value of the expression evaluation
conditionfortrue.
• instructions represent a set of one or more instructions for where the
diversion will be made if the resulting value from the evaluation of the expression
condition forfalse.

It is important to point out that the partotherwisethe conditional instruction is optional.

Obviously, when this part of the instruction is absent, a deviation will occur only if the
result of the conditional expression fortrue.

Example:

read(x)

if (x < 0) then
The number is negative
otherwise
The number is not negative.

In this example, if the value read forx for-5the instruction:

The number is negative

it will be executed, but it will not be the case of the instruction:

The number is not negative

Chapter 2 Introduction to Algorithm Construction 22

2.7.2 Conditional Deviation select-case

The instructionselect-caseitis a multiple conditional branching instruction (or

deselection instruction) useful when there are several possible branches to be followed
in a section of the program. In this case, the use of instructionsit-so-otherwisenested
make the program difficult to read. The syntax of this instruction is:

select (whole-expression)
constant case1
instructions1
constant case2
instructions2
...
constant caseN
instructionsN
standard
instructionsp

The expression in parentheses that immediately follows the selected word must result in
in an integer value. When the resulting value from evaluating this expression coincides with
the value of one of the constants that accompany the words case, the instructions
corresponding to the respective constant are executed.

The part of the instructionselect-casethat

starts with the keyword is optional and
your instructions are executed when the resulting value of evaluating the expression is not
match with the value of no constant preceded by case.

Example:

Choose one of the five options:

Leia(op)

select (op)
case 1
You chose option 1
case 2
You chose option 2
case 3
You chose option 3
case 4
You chose option 4
case 5
You chose option 5
pattern
You did not choose a valid option
Chapter 2 Introduction to Algorithm Construction 23

2.7.3 Repeat Structure while-do

The instructionwhile-do itit has the following format:

while (condition) do instructions

Where:

• condition represents a logical expression that controls repetition.

• instructions represent a set of one or more instructions, called
body of the loop, which can be executed several times.

The loopwhile-do itit works like this: the expression condition is

evaluated; if the result of this evaluation istrue, the body of the loop is executed;
otherwise, the loop is terminated. This procedure is repeated until the result of
expression condition befalse.

It is important to note the following:

• If the first evaluation expressioncondition results infalse, the body of

the loop does not execute at all.
• If the condition expression never results infalsethe bond will never end
and the structure is called infinite bond.

Example 1:

read(x)

while (x < 10) do

x← x + 1

Exercise: What would happen if the body of the loop in this example werex← x - 1and the
if the read value was less than 10?

Example 2:

whole sum, count

soma← 0
cont← 1

while (cont < 10) do

Chapter 2 Introduction to Algorithm Construction 24

soma← soma + cont

cont← cont + 1

write("Result: ", sum)

Exercise: What does the algorithm from the last example write?

2.7.4 Do-while Loop Structure

The lace has the following format:

do instructions while (condition)

The only difference between the tiesmake-whileewhile-do itrelates to

when the conditional expression is evaluated. In the instructionwhile-do it, the expression
condition is evaluated before the body of the loop; in the instructiondo-while, a
conditional expression is evaluated after the loop body. As a consequence, the body
of a bowdo it-whileit may not be executed at all, but the body of a
loopwhile-doit is always executed at least once.

Example:

read(x)

do it
x← x + 1
while (x < 10)

Compare this last example with the first example in Section 2.7.2. Note that the
the only difference between them is that that example uses the loopwhile-makeand this
example uses the loopmake-whileNow, assuming that the value read and stored
in the variablexmine12in both cases, the body of the loopdo-whilewould not be
executed none time and the body of the noosewhile-do itwould be executed exactly
once.

2.7.5 Unconditional deviation stop

The instructionstopis
used to terminate loops, causing the flow of
execution should be diverted to the next instruction following the respective loop
repetition. For example, the following algorithm calculates the sum of numerical values
introduced by a user until he enters the value zero:
Chapter 2 Introduction to Algorithm Construction 25

soma← 0

while (true) do
read(x)

if (x = 0) then
stop

soma← soma + x

Write("Sum of the values: ", sum)

Note that the expression that accompanies the instructionwhile-dois represented

for the constant valuetrueTherefore, the only way to end the loop is by
middle of an instructionstop.

2.7.6 Blocks and Indentations

In programming, indentation is a small horizontal space that indicates

subordination of one instruction in relation to another. All examples of structures of
the controls presented above use indentation to indicate subordination of instructions
to the control structures to which they belong.

In an algorithm, a block is a sequence of instructions with no dependencies between them.

Thus, instructions that belong to the same block do not have indentations between
Yes. For example, in the following algorithm section:

x←1

while (x < 10) do

x← x + 1
write(x)

Bye, bye

the instructionsx ← x + 1ewrite(x)are at the same level of indentation and

therefore they are part of the same block. This block is subordinate to the instruction
while (x < 10) doand therefore, he is indebted in relation to this instruction.
The instructionBye, bye, which is not indented, does not belong to the block
what constitutes the body of the control structure.

Exercise: How many blocks are there in the last example and what are the instructions that
What is part of each block?
Chapter 2 Introduction to Algorithm Construction 26

Modern programming languages completely ignore additional spaces in

white, like those used in indentations. Therefore, in these languages, others
mechanisms are used to indicate the boundaries of a block. In C, for example, a
block is delimited by the characters {e}. However, in the algorithmic language used
Here, which will only be read by people, the indentation is sufficient to delineate blocks.

2.8 Comments and Readability of Algorithms

Readability is a highly desirable property of an algorithm. An algorithm

Readable code is easier to understand, test, and refine than an algorithm with
poor legibility.

The following procedures are recommended for constructing readable algorithms:

• Incorporate clear Portuguese comments in the algorithm.

Comments are inserted in an algorithm between /* (opening) and */
(closure). The goal of commenting an algorithm is to make it more
legible and the best time for this is during the conception of the algorithm
(and not after a week, for example). Comments should
add something beyond what can be easily
apprehended. For example, in the instruction:

x← 2 /* x receives the value 2 */

the comment is completely redundant and irrelevant, as a

programmer with a minimum of basic knowledge about
algorithms know the meaning of this instruction without the need for
any comment.

• Use variable names that are meaningful. In other

words, the name of a variable should suggest the type of information
stored in it. For example, in an algorithm to calculate averages of
students in a subject, the names of variablesname, note1, note2e
averagethey will certainly be much more significant than just
x , y , w ez .

• Highlight all the keywords(for example,read, be, so)

used in the algorithm10.

10
Keywords are often written in bold in textbooks and other materials.
printed, but this resource is not available, or at least is not very practical, in
handwritten algorithms.
Chapter 2 Introduction to Algorithm Construction 27

• Use indentation consistently. There is no format.

considered more correct for indentation, although some formats of
indentation is more recommended than others. For example,
some programmers prefer to align the parts of an instructionbe...
so... otherwiselike:

secondition then
instructions
otherwise
instructions

while others may prefer:

second sight
so
instructions
otherwise
instructions

Neither of the two forms of indentation above is more correct or more

more legible than the other. That is, using one format or another is a matter
of personal taste. But, once a format of indentation has
once chosen, it must be consistently maintained in the writing of the
algorithms.

• In addition to indentation, the judicious use of vertical whitespace

it can also improve the readability of algorithms in the same way
that the division into paragraphs improves the readability of common texts.
In particular, use vertical blank spaces to separate statements
of variables and the body of the algorithm. Also separate groups of
instructions that have different functions. Like with indentation, the use of
spaces to improve the readability of an algorithm not
it has fixed rules: simply use common sense and don't overdo it or
for more or less.

• It is recommended to use horizontal spaces to emphasize.

operator precedence. For example:

5*3+4

is better than:

5*3+4
Chapter 2 Introduction to Algorithm Construction 28

you:

5*3+4

• Use parentheses in expressions to clarify questions and make them more

legible (see Section 2.5.5). Don't worry about being redundant. Remember
I know that for every opening parenthesis there must be a closing parenthesis.
This means that the number of opening parentheses "(" must be equal
to the number of closing parentheses “)”. One way to check the
correspondences in parentheses in an expression containing many
parentheses is drawing lines cconnecting each pair of parentheses,
as shown in the following example11.

This way of checking parenthetical expressions is much more efficient than

just count the number of open parentheses and compare
to see if it matches the number of closing parentheses.

• Never write more than one instruction per line. That is, even if
you have a sufficiently small set of instructions for
fitting on one line, don't do it because it will harm readability of the
algorithm.

• Break long instruction lines. When an instruction is

too extensive to fit in a single line, break the line and use
indentation on the following line forindicate the continuation of the instruction.
For example, it is better to write the instruction12:

write("This é a instruction very

loooooooooooooooooooooonga

like this:

This is a very instruction

long

11
This is just a verification trick. Obviously, these lines should not be part of it.
of the algorithm.
12
Suppose that the instruction from the example is actually much longer.
Chapter 2 Introduction to Algorithm Construction 29

2.9 How to Build a Program I: Algorithm Design

The construction of a small-scale program in any algorithmic language

The conventional process usually follows the sequence of steps mentioned below:

1. Problem analysis (see Section 2.9.1)

2. Refinement of the algorithm (see Section 2.9.2)
3. Algorithm test (see Section 2.9.3)
4. Algorithm coding (see Section 3.16.1)
5. Construction of the executable program (see Section 3.16.2)
6. Program test (see Section 3.16.3)

The first three steps will be explored in depth below, while the
the others will be studied in Chapter 3.

Before proceeding, it is important to emphasize that the machine only does what you are.
capable of teaching her. Thus, the main premise of programming can be stated
like:

The computer only does what it is instructed to do (which is not always

corresponds to what you want him to do.

Therefore, when writing an algorithm, try to think about how the computer will execute it.
that is, without making any inference, conjecture or assumption, as the computer does not
has this ability.

2.9.1 Stage 1: Problem Analysis

The first step to be followed in the construction of an algorithm consists of analysis.

understand the problem. This step is fundamental and should not be overlooked.

At this stage, the problem statement must be analyzed word by word until the
input and output data can be properly identified. Once this is done, an attempt is made
describe a procedure in Portuguese that shows how to obtain the result
desired (output) using the available data (input). The table below summarizes this
stage.

1. Read and reflect carefully on the problem, and answer the following questions:
Chapter 2 Introduction to Algorithm Construction 30

1.1 What initial problem data will be available (input)? Write the
response to this question preceded by the word Entry.
What is the expected result (output)? Write the answer preceded by
Exit.
1.3 What type of processing (algorithm) is necessary to obtain the result
expected from the input data? Write an algorithm that does this.
Don't worry for now about whether the algorithm is well detailed.
You can even write it in Portuguese, instead of using the language
algorithmic.

The answers to questions 1.1 and 1.2 are necessary to identify the input data and
program output. When answering these questions, use meaningful names (not
necessarily in Portuguese) to represent input and output data (e.g.,
studentRegistration). Make sure these answers are very accurate before
proceed to step 1.3.

In stage 1.3, you must find a connection between the input data and the result.
desired that allows determining which are the steps of the algorithm that lead to the
result. The following are presented somethe recommendations for being successful in
writing of this algorithm outline13:

• Build a predicted example of the program execution result and use it.
until the end of the development process. An example of execution is
useful not only in the phase of building the algorithm but also serves
as a test case of the algorithm itself and the program that will result from it
end of the process.
• Draw diagrams that assist your reasoning. In particular, use
rectangles to represent variables and track the changes of their
contents represented by the interiors of the rectangles, as shown
several examples presented in the book.
• Try to recognize something that is familiar. That is, try to find a
problem that presents similar output and involves principles
similar. Use analogy and try to find a simpler problem that
be similar to the one in question. That is, if you cannot solve the
proposed problem, try to solve a similar problem first that is
considered easier. Solving a simpler analogous problem may
provide clues for solving a more complex problem.

13
Some of the suggestions presented below were adapted from the book How to Solve It
mathematician George Pólya (see Bibliography).
Chapter 2 Introduction to Algorithm Construction 31

Suppose, for example, that your algorithm aims to solve second degree equations.
gray (i.e.,ax2bx + c = 0So, at this stage of building the algorithm you
you should obtain the following:

a, b, c (real values that represent the coefficients of the equation)

Output:
• The coefficients do not constitute a second degree equation.
• There are no real roots
• x1, x2 (as real roots of the equation, if they exist)

Algorithm:
1. Read the values of the coefficients and store them in the variables a, b, c.
If the coefficients do not constitute a quadratic equation, report.
the fact is closed.
3. Calculate the discriminant (∆) of the equation.
If the value of the discriminant is less than zero, inform that there are none
real roots and conclude.
5. Calculate the values of the roots and present the result.

Predicted examples of execution:

Example 1:

Quadratic coefficient (a): 0

Result: The value of a cannot be zero

Example 2:

Coeficiente quadrático (a): 1

Coeficiente linear (b): -2
Coeficiente constante (c): 4

Result: There are no real roots

Example 3:

Quadratic coefficient (a): 1

Linear coefficient (b): -5
Coeficiente constante (c): 6

Result: The roots are: 3 and 2

Chapter 2 Introduction to Algorithm Construction 32

Example 4:

Coeficiente quadrático (a): 1

Coeficiente linear (b): -2
Constant coefficient (c): 1

The roots are: 1 and 1

Despite the relative simplicity of the problem exemplified above, it is unlikely that a
beginner programmer can succeed in this stage on the first attempt. In
algorithm in question, the most common mistake among beginners is to assume that the only output of
algorithm is the roots of the equation. In other words, beginners often forget
what may be is that there are no roots or that the coefficients read do not even constitute
a second-degree equation. Therefore, it is important that there is a deep reflection
about the problem in order to accurately determine what the input data is and
output of an algorithm before proceeding with its writing. It is impossible for a
The algorithm is correctly written when its inputs and outputs are not well defined.
specified.

2.9.2 Stage 2: Algorithm Refinement

The second stage of building a program involves refining the algorithm.

preliminary obtained in the first stage:

2. Break down each step of the algorithm outlined in Step 1.3 that does not have
trivial solution.

At this stage, the initial algorithm for solving second-degree equations would be
refined as:

real a, b, c, x1, x2, delta

read

if (a = 0) then
The value of a cannot be zero
if not
read(b, c)

delta = b*b - 4*a*c

if (delta < 0)
There are no real roots
otherwise
(-b + sqrt(delta)) / (2 * a)
x2 = (-b - sqrt(delta))/(2*a)
Chapter 2 Introduction to Algorithm Construction 33

The roots are:

Notes:
• Note that the variabledeltathe algorithm above does not represent either
neither input nor output of the algorithm; i.e., it is used as an auxiliary variable
in processing.
• The algorithm presented above is not the only solution to the problem.
Normally, there are many functionally equivalent algorithms
that solve a certain problem. Perhaps not all of these
algorithms may be equivalent in terms of efficiency, but,
meanwhile, don't worry about this aspect.
• Do not expect to quickly achieve a refinement like the one presented.
above. That is, you may need to make several refinements
intermediaries before obtaining a satisfactory algorithm. As an exercise,
refine the algorithm outline presented in Section 2.9.1 and try to obtain
an equivalent algorithm to the one presented above. The result that you
it does not have to be the same as the last algorithm presented, but it should
be functionally equivalent to it.

2.9.3 Step 3: Algorithm Testing

After obtaining a refined algorithm, you must test it:

3. Check if the algorithm actually works as expected. In other

words, check if the algorithm does what it should do and does not do what it should not
should do. Test the algorithm with some input cases that are
qualitatively different and verify if it produces the desired output for
each of these cases. If the algorithm produces undesirable responses, go back to
Stage 1.

Considering the example of quadratic equations presented above, if you

test your algorithm only with input cases that always result in∆ 0
regardless of the number of tests, they will not be qualitatively different, and
therefore, they will not be sufficient to test your algorithm. Qualitative tests
different ones must check all possible outputs of an algorithm.

Note also that if you need to return to Step 1, as recommended above, do not
you need to undo everything you have done so far. Maybe you just forgot to take
considering some input data (Step 1.1), or one of the steps of the algorithm
preliminary (Stage 1.3) or its refinement (Stage 2) may be inadequate.
Chapter 2 Introduction to Algorithm Construction 34

To test an algorithm, you must act as both the computer and the user.
That is, you should perform the algorithm manually as if you were the computer and
You should also provide input data for the algorithm, as if you were a user.
For example, consider the algorithm for solving quadratic equations.
presented above. The first step of this algorithm is the instruction:

Leia

During the tests, you will need to input a value for the variable.a, exercising, thus,
the role of the user, and read the respective value, acting as a computer. Suppose
that you introduce (as a user) and read (as a computer) the value zero. Then, after the
manual execution of this instruction the value of the variablea becomes zero.

The beginning of the next instruction of the algorithm is:

if (a = 0) then
The value of a cannot be zero.

Like the value of the variableaat this moment of the execution of the algorithm is zero, according to
with the interpretation of the if-then-else instruction, the instruction:

The value of a cannot be zero

will be executed. Thus, the result is the writing of:

The value of a cannot be zero

After writing this sentence, the algorithm ends because the mentioned part is not.
instructions-then-not-executed and there are no more instructions that
can be executed in the algorithm. Now, observing the first expected example of
execution, this was really the expected result of the algorithm. Therefore, the algorithm is
approved in the input case test when the coefficienta is equal to zero.

The four anticipated execution examples presented in Section 2.9.1 represent

qualitatively different input cases. Therefore, all of them must be tested.
Above, it was shown how to test the algorithm with the first input case (i.e.,
whenais equal to zero). It is left as an exercise to test the other cases using the
the same reasoning applied above.

2.9.4 Implementation

Typically, the final stages of building a program are collectively

referred to as implementation and consist of editing the source program, building the
Chapter 2 Introduction to Algorithm Construction 35

executable program and subsequent tests. In reality, these steps can only be
considered as last if the resulting program is absolutely correct, what
it rarely occurs. The most common is that it contains flaws and, consequently, is
it is necessary to repeat the construction process from one of the previous stages.

What happens from Stage 4 (inclusive) of program construction is the subject of

study of the next chapter. But, only as an illustration and not to leave
incomplete or the example of quadratic equations started above, the coding in C
The algorithm that solves this problem is presented below:

/* Allows the use of library functions */

#include "leitura.h" /* Function LeReal() */
#include <stdio.h> /* printf() function */
#include <math.h> /* Function sqrt() */

int main(void)
{
/* >>> The translation of the algorithm begins below <<< */

/* double is the equivalent in C to the type */

/* real of the algorithmic language */
double a, b, c, /* Coefficients of the equation */
x1, x2, /* The roots */
delta; /* Discriminant of the equation */

/* Requests the user and reads the coefficient 'a' */

Enter the quadratic coefficient (a):
a = LeReal();

If the value of 'a' is equal to zero, do not

It will have a quadratic equation */
if (a == 0) {
/* Informs the result of the program */
The value of a cannot be zero
else
/* Asks the user and reads the coefficient 'b' */
printf("\nEnter the linear coefficient (b): ");
b = LeReal();

/* Requests the user and reads the coefficient 'c' */

Enter the constant coefficient (c):
c = LeReal();

delta = b*b - 4*a*c; /* Calculates the discriminant */

/* Check if there are real roots */

if (delta < 0) { /* There are no real roots */ }
/* Indicates the result of the program */
There are no real roots
} else {
/* Calculates the roots of the equation */
x1 = (-b + sqrt(delta))/(2*a);
x2 = (-b - sqrt(delta))/(2*a);

/* Informs the result of the program */

The roots of the equation are: %f and %f
Chapter 2 Introduction to Algorithm Construction 36

x1, x2 );
}
}

Ends the program informing the system

operational that there was no error */
return 0;
}

Examples of program execution:

Example 1:

Enter the quadratic coefficient (a): 0

The value of a cannot be zero

Example 2:

Enter the quadratic coefficient (a): 1

Digite o coeficiente linear (b): -2

Enter the constant coefficient (c): 4

There are no real roots

Example 3:

Enter the quadratic coefficient (a): 1

Enter the linear coefficient (b): -5

Enter the constant coefficient (c): 6

The roots of the equation are: 3.000000 and 2.000000

Example 4:

Enter the quadratic coefficient (a): 1

Digite o coeficiente linear (b): -2

Enter the constant coefficient (c): 1

The roots of the equation are: 1.000000 and 1.000000

Even if you have not yet been formally introduced to the C language, read the
program and try to find some correspondence between it and the presented algorithm
in Section 2.9.2.
Chapter 2 Introduction to Algorithm Construction 37

2.10 Programming Examples

2.10.1 Exchange of Values between Variables

Problem: Write an algorithm that reads values for two variables and swaps their values.
It shows them before and after the exchange. In other words, if the variables arex e y, at the end
x will have the initial value ofy, andy will have the initial value ofx.

Solution:

Input: x, y
Output: x, y

Preliminary Algorithm:
1. Read the values of x and y
2. Write the values of x and y
3. Store the value of x in a temporary variable
4. Assign the value of y to x
5. Assign the value of the auxiliary variable to y
6. Write the values of x and y

Refined Algorithm:
read(x, y)
write("Values of x and y before the swap", x, y)

/* If the value of x is not saved, */

he will be lost */
auxiliary← x
x← y
y← auxiliary

Write("Values of x and y after the swap", x, y)

Power Table

Problem: Write an algorithm that calculates and presents a table presenting the
first 100 powers of 2 (i.e., 2 ). (Yourn algorithm should not contain 100 instructions)
write!)

Solution:

entry: none
Chapter 2 Introduction to Algorithm Construction 38

Output:
01
12
24
...
100 299

Preliminary Algorithm:
1. Start the exponent with 1
2. Start the power with 1
3. Write 0 and 1
4. While the exponent is less than 100 do
4.1 Assign to the power its current value multiplied by 2
4.2 Write the value of the exponent followed by the power
4.3 Assign to the exponent its current value plus 1

Refined Algorithm:
exponent← 1
power← 1

/* Displays the first row of the table */

01

/* Display the remaining rows of the table */

while exponent < 100 do
power← power * 2
write(exponent, power)
exponent← exponent + 1

2.10.3 Sum of an Indeterminate Number of Values

Problem: Write an algorithm that calculates and writes the sum of a set of
values. The algorithm must terminate when a zero value is read.

Solution:

Input: set of values

Output: the sum of the values

Preliminary Algorithm:
Read the first value
2. Assign the first value to the variable that will accumulate the sum
3. While the read value is different from zero do the following
3.1 Read a value
Chapter 2 Introduction to Algorithm Construction 39

3.2 Assign to the variable sum its current value added to the value
pool
4. Write the sum of the values read

Refined Algorithm:
read(value)
soma← value

While the read value is different

From scratch do the following */
while value ≠ 0 do
read(value)
soma← sum + value

write(sum)

Fibonacci Sequence

Problem: A Fibonacci sequence is a sequence of natural numbers, whose

the first two terms are equal to 1, and such that each number (except the first two)
in the sequence is equal to the sum of its two closest preceding numbers. That is, the
the Fibonacci sequence is made up as follows:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Write an algorithm that generates the Fibonacci sequence up to the n-th term.

Solution:

Input: number of terms in the sequence.

Output:
• The terms of the sequence, if the number of terms is greater than or equal to 2.
• Report of irregularity if the number of terms is less than 2.

Preliminary Algorithm:
1. Read the number of terms in the sequence
2. If the number of terms entered is less than two,
report that the sequence does not exist and close.
3. Write the first two terms of the sequence
4. Generate and present the terms of the sequence starting from the third
term up to the n-th.
4.1 While the n-th term is not generated and written do:
4.1.1 Calculate the current term as the sum of the two.
previous terms
Chapter 2 Introduction to Algorithm Construction 40

4.1.2 Write the current term

4.1.3 Update the preceding terms
[Link] The first antecedent becomes the second
[Link] The second antecedent becomes the current one

Refined Algorithm:
integer nTerms, antecedent1, antecedent2, current, i

read (terms)

if (nTerms < 2) then

The number of terms cannot be less than 2
otherwise
antecedent1← 1
antecedent2← 1

/* Displays the first two terms of the series */

write(antecedent1, antecedent2)

Generate and display the terms of the sequence from

from the third term to the n-th term */

I← 3

while (i <= nTerms) do

current← antecedent1 + antecedent2
write(current)

/* Updates the previous terms */

antecedent1← antecedent2
antecedent2← current

i← i + 1 /* Increments the term counter */

In C, this algorithm could be coded like this:

/* Allows the use of library functions */

#include <stdio.h> Input and output
#include "leitura.h" /* EasyRead */

int main(void) /* Here begins the execution of the program */

{
/* Variable declarations */
int antecedent1, antecedent2,
current, nTerms, i;

Read the number of terms of the sequence

Enter the number of terms of the sequence
(at least 2):
nTerms = ReadInteger();

/* Checks if the number of terms */

is less than 2 */
if(nTerms < 2) {
The number of terms cannot be less
Chapter 2 Introduction to Algorithm Construction 41

of what 2
} else {
/* Initializes the first two terms of the series */
antecedente1 = 1;
antecedent2 = 1;

/* Displays the first two terms of the series */

%d, %d

/* Generates and displays the terms of the sequence a */

/* starting from the third to the nth term */

/* Starts the term counter of the sequence */

i = 3;

while (i <= nTerms) {

/* Updates the current term with the */
sum of its two predecessors
current = antecedent1 + antecedent2;

/* Displays the current term */

, %d

Update the preceding terms

antecedent1 = antecedent2;
antecedent2 = current;

i = i + 1; /* Increments the term counter */

}
}

Close the program informing the system

Operational that had no error */
return 0;
}

Example of program execution:

Enter the number of terms in the sequence (at least 2): 5

1, 1, 2, 3, 5

Again, even if you don't know the C language yet, read the program and try.
find some correspondence between the algorithm presented earlier and this program.

2.11 Review Exercises

Definition of Algorithm (Section 2.1)

What is an algorithm?
Chapter 2 Introduction to Algorithm Construction 42

2. (a) In what aspects is the concept of algorithm analogous to the concept of a recipe?
cuisine? (b) When does this analogy cease to be valid?

What is an input case?

What is a correct algorithm?

5. What are functionally equivalent algorithms?

6. Cite três exemplos de problemas que não possuem algoritmos.

Divide and Conquer Approach (Section 2.2)

7. Describe the divide and conquer approach used in the construction of algorithms.

8. What does the level of detail of instructions obtained through depend on

successive refinements?

9. What is code reuse?

Algorithmic Language (Section 2.3)

10. (a) O que é linguagem algorítmica? (b) Por que linguagem algorítmica também é
called pseudolanguage?

11. What is the advantage of using pseudocode in the construction of algorithms?

detriment to the use of natural language (e.g., Portuguese)?

12. Why a high-level programming language is not convenient for the

writing algorithms?

What is pseudocode?
for algorithms written in pseudocode?

Variables and Assignments (Section 2.4)

14. What are the attributes that characterize a variable?

15. What is an assignment statement?

Chapter 2 Introduction to Algorithm Construction 43

16. What is the meaning of the following instruction:

x← x + 2

Operators and Expressions (Section 2.5)

17. Describe the following properties of operators:

Aridity
(b) Result
(c) Precedence
(c) Associativity

What is a unary operator?

19. What is a precedence group?

What is left associativity?

21. How are arithmetic operators grouped according to their precedences?

22. (a) Para que servem os operadores relacionais? (b) Quais são os operadores
relational?

23. What are the possible values resulting from the evaluation of a relational expression?

24. Descreva os operadores lógicos de negação, conjunção e disjunção.

25. What is a truth table?

26. What are parentheses used for in an expression?

27. Write the truth table corresponding to the boolean expression:A or B and C, where
A, BandCare logical variables. (Remember that the operatorandhas precedence
greater than the operatoryou.)

28. IfA = 150, B = 21, C = 6, falseeL2 = truewhat will be the

value produced by each of the following boolean expressions?
(a)not L1 and L2
(b) not L1 or L2
(c)no (L1 and L2)
Chapter 2 Introduction to Algorithm Construction 44

(d)L1 or not L2
(e)(A > B) and L1
(f)(L1 or L2) and (A < B + C)

Input and Output (Section 2.6)

29. What is a data input instruction used for?

30. Describe how the instruction worksprincess.

31. What is a data output instruction used for?

32. Describe how the instruction workswrite.

33. What is a string?

Control Structures (Section 2.7)

34. (a) O que é fluxo de execução de um algoritmo? (b) Como é o fluxo natural de
execution of an algorithm?

What are control structures?

36. How are control structures classified?

37. Describe the functioning of the if-then-else instruction.

38. What is the difference between the while-do and do-while instructions in terms of
functioning?

39. (a) O que bloco? (b) O que é endentação? (c) Qual é a relação entre bloco e
indentation in pseudocode?

40. Consider the following algorithm, wherei1, i2, i3, i4ei5represent instructions:

boolean b1, b2, b3

if b1 then i1
otherwise
if b2 then
so b3 then
i2
Chapter 2 Introduction to Algorithm Construction 45

otherwise
i3
i4
i5

Now, suppose thatV representstrueeF representsfalseand answer the

following questions:

(a) What instructions will be executed whenb1 = V, b2 = Veb3 = F?

What instructions will be executed whenb1 = F, b2 = Vandb3 = F?
(c) What instructions will be executed whenb1 = F, b2 = Veb3 = V?
What values should they assume?b1, b2eb3for just the instructioni5be
executed?

41. What will be the value of the variableresultafter the execution of the following algorithm?

boolean b1, b2, b3

real x, y
whole result

b1← false
b2← true
b3← false

x← 1.5
y← 3.5
x← x + 1

b3 or ((x + y > 5) or (not b1 and b2))

so result← 0
otherwise result← 1

Two instructions are functionally equivalent if they produce the same effect.
under any circumstances. Check if instructions 1 and 2 below are
functionally equivalent:

Instruction 1:L← X = Y

Instruction 2:if X = Y
so L← true
otherwise L← false;
Chapter 2 Introduction to Algorithm Construction 46

Comments and Readability of Algorithms (Section 2.8)

43. Cite five recommended practices in building algorithms that favor the
readability.

What is a meaningful variable name?

What is a comment in algorithm construction?

incorporation of comments in an algorithm?

46. (a) O que é endentação coerente? (b) Por que é aconselhável usar endentação
coherently in the construction of algorithms?

How to Build a Program (Section 2.9)

47. What are the steps involved in writing an algorithm?

48. How should a problem for which an algorithmic solution is desired be analyzed?

49. (a) Como um algoritmo deve ser testado? (b) Como um programa deve ser testado?

50. Why, even if an algorithm has been tested and deemed correct, is it
Is it necessary to test a program derived from it?

Is it always necessary to declare the variables of an algorithm?

52. Why is the final stage of building a program not always the last?

2.12 Programming Exercises

2.12.1 Easy

EP2.1) Write an algorithm that takes the radius of a circle as input and calculates its
2
area and displays the result. Given: area of a circle =πr , where r is the radius of the circle.
2
Tip: to obtain r , simply calculate r*r.

EP2.2) Write an algorithm that reads a value supposedly representing a measure

in inches and convert it to centimeters. [Tip: 1 inch corresponds to 2.54cm.]
Chapter 2 Introduction to Algorithm Construction 47

EP2.3) Write an algorithm that reads three integer values that will be stored in the
variables x, y, and z. Then, the algorithm calculates and displays the sum and the product of these values.

EP2.4) Write an algorithm that takes two numbers as input and displays the smaller one.
themselves. If the numbers are equal, there will be no difference as to which one will be
presented.

EP2.5) Write a slightly different algorithm from that of the previous exercise that
The numbers are equal.
equal forms.

EP2.6) Write an algorithm that reads three integers and informs which one is the largest.

2.12.2 Moderate

EP2.7) Write an algorithm that repeatedly reads real values that represent radii.
of circles. For each read value, the algorithm calculates the area of the respective circle and displays it.
the result. The algorithm should terminate when a value of zero is read.

EP2.8) Write an algorithm that reads an indefinite number of values and displays the
the least of them. The entry of values ends when zero is read. [Suggestion: Use a
variable to store the smallest value read. Initially, assign this variable the
first value. Then, for each value read, compare it with the value of the variable that should be
count the smallest. If a new value read is less than the one currently
stored in this variable, assign this value to the variable.

EP2.9) Write an algorithm that calculates and presents the factorial of a given number
non-negative integer. The factorial of an integer n≥ 0 is given by:

1, if n = 0
n * (n - 1) * (n - 2) * ... * 2 * 1, if n > 0
Chapter 2 Introduction to Algorithm Construction 48