### Unit 7:INTRODUCTION TO COMPUTER ALGORITHM

**Key Unit Competency**

By the end of the unit you should be able to:

• Identify appropriate steps to solve a problem.

• Identify an appropriate algorithm for a given problem.

• Represent graphically algorithm using flowchart.**Unit Outline**

• Algorithm concept.

• Design of algorithm.

• Variables.

• Constants.

• Operators and expressions.**Introduction**

Before developing a program, is it important that a programmer specifies the order in

which the set of instructions contained in the program are to be executed. This process

of defining the step-by-step procedure in which the instructions are to be executed is

known as algorithm design. In this unit, we begin by defining algorithm concepts

followed by discussion on tools used to design algorithms. Later, we demonstrate

how to express algorithm’s logic and concepts using pseudocode and flowcharts.**7.1 Algorithm Concept**

The term algorithm was derived from the name of the 9th century Persian

mathematician and astronomer Mohammed al-Khwarizmi. The concept has been

adapted in computer science to refer to a step-by-step procedure that specifies how

to perform a task or solve a problem. Therefore, a computer program is an algorithm

implemented using a programming language.

To ensure that an algorithm produces desired solution, a programmer is tasked with

the following roles:

1. Identify a problem that may be solved using a computer program.

2. Outline the social and technological factors that need to be considered before

converting the problem into a computer program.3. Provide possible solutions to a problem. This may be by means of using off-theshelf software or custom-made software.

**7.1.1 Characteristics of Algorithm**

A good algorithm is crucial to development of good computer programs. Some of

the characteristics of good algorithms include:

• Correctness: The goal during program design is to produce logical designs.

The design of a system is correct if the system satisfies user’s requirements. It

is the responsibility of a programmer to find the best possible design within the

limitations imposed by the requirements and environment in which the program

will be used.**• Verifiability**: Verifiability is concerned with how easily the correctness of the

design can be checked. Design should be correct and it should be verified for

correctness.**• Completeness:**Completeness requires that designs of different system

components be verified. This requires dry-running of system’s data structures,

modules, user interfaces, and module integration.**• Traceability:**In order for a program to meet user’ needs and expectations, it is

important that the entire design be traceable from user requirements.**• Efficiency:**Good design results in an efficient program that consumes less

processor time and memory space.**• Simplicity:**Though a program may be complex, its simplicity is one of the most

important factors that influence its user-friendliness and ease of maintenance.**• Documentation**: It is good practice to provide documentation containing details of a program algorithms.**7.1.2 Role and Structure of algorithms**

The role of algorithms is to support programmers in designing and implementing computer programs that solve a problem of importance. For example, consider a problem of finding the shortest route to travel between Kigali and Musanze. To solve such a problem, algorithm design follows a structured approach outlined below:

1. The programmer first analyses the problem to come up with problem specification as shown in Fig. 7.1. A problem specification defines input, processing and output required to solve the problem

2. Map the problem specification into an algorithm that defines the logic or

procedure for solving the problem.

3. Once an algorithm has been designed and tested against problem specifications,

implement it as a program using suitable programming languages.

4. Finally the program is installed on computers or portable devices to solve the

problem.**7.2 Design of Algorithms**

Algorithms can be expressed in many ways such as using natural languages,

pseudocode, and flowcharts used for complex or technical algorithms. To avoid

ambiguities common in natural language statements, most programmers prefer using

structured design tools like pseudocode and flowcharts discussed in details later.**7.2.1 Natural language**

The term natural language refers to the ordinary language likes English or Kinyarwanda

used by human beings to communicate with each other in speech or writing. Because

an algorithm is a procedure for solving a problem, the natural languages can be used

to express the steps to be followed to solve a specific problem. For example, the

following is natural language algorithm for how to make a hot sauce:

1. Before you prepare a hot sauce, make sure you have garlic that is peeled and

chopped, fresh lime juice, distilled white, vinegar, olive oil, molasses, turmeric

and salt.

2. Now, combine the pepper, garlic, lime juice, vinegar, mustard, oil, molasses,

turmeric, and salt in a blender and puree until smooth. Correct the seasoning,

adding more salt or molasses to taste.

3. Transfer the sauce to a clean bottle. You can serve it right away, but the flavour

improves if you let it age for a few days.

The above ‘algorithm’ is a recipe, that is, a step-by-step instructions that takes raw

ingredients and produces a tasty product – hot sauce. However, one of the limitations

of such an algorithm is that it tends to be verbose or ambiguous. Furthermore, there

are different languages in the world which makes it difficult for an algorithm written

in a particular language to be universal. To avoid ambiguities inherent in natural

languages, there are language independent tools such as pseudocode and flowcharts discussed later in this section.**Activity 7.1: Natural Language Algorithm**

1. Consider a daily routine of waking up and going to class. Outline an algorithm

named “wakeup-to-class” starting with getting out of bed to attending the first

lesson of the day. If the routine is to be computerized, specify the order in which

statements are to be executed.

2. In groups, identify ingredients of preparing ibihaza or bugali. If the routine is to

be computerized, specifying the order in which statements are to be executed.

Discuss desirable qualities of recipe in terms of procedure for preparing the

product.

3. Consider a payroll program used to computer employee’s salary based on basic

salary, house allowance, commuter and overtime allowance. The basic salary is

based on eight hours per pay for five days a week. If monthly net salary is less

15% pay as you earn (PAYE) and 2.5% medical cover, perform the following

tasks:

• Using natural language such as English, develop an algorithm for a program

that calculates gross salary, net and total deductions.**7.2.2 Pseudocode**

Pseudocode is a standard method of describing an algorithm without use of any

specific programming language. The word pseudo means that although pseudocode

statements resemble real program code, it cannot be executed by a computer. The

purpose of pseudocode design is to help the programmers formulate their thoughts on

the organisation and sequence of a computer algorithm without the need of following

the actual coding syntax.

Although pseudocode is frequently used, there are no standard for its implementation.

In most cases, we borrow keywords such as PRINT, WRITE, INPUT, and READ

from programming languages like FORTRAN and Pascal to express an algorithm as

a pseudocode. For example, Fig. 7.2 depicts pseudocode that takes radius as input

to calculate and display area of a circle:To avoid ambiguity experienced with the use of natural languages, the following are

basic rules to be followed when writing pseudocode:

1. Pseudocode statements should be short, clear and readable.2. The statements must not have more than one meaning i.e. should be unambiguous.

3. The pseudocode lines should be clearly outlined and identified clearly.

4. A pseudocode should show clearly the start and stop of executable statements

5. Input, output and processing statements should be clearly stated, using keywords

such as PRINT, READ, INPUT etc.**Advantages of using pseudocode**

The following are some the advantages of using pseudocode to express an algorithm:

1. Pseudocode is easy to use and create because it uses English-like statements.

2. Pseudocode requires very little syntax to write.

3. Statements of a Pseudocode can easily be translated to any high-level language.

4. Pseudocode reduces time spent in coding, testing, and modifying a system.

5. Pseudocode implements structured concepts in a better way**Activity 7.2: Expressing Algorithm using pseudocode**

Neza deposited FRW 200 000 in a bank at interest rate of 8% per annum for a period

of five years. At the end of each year, the interest earned is added to the deposit and

the new amount becomes the deposit for that year. Formulate a pseudocode that

would be used to track growth of the investment.**7.2.3 Flowcharts**

A flowchart is a diagrammatic or symbolic representation of step-by-step solution to a given problem. Flowcharts use standard symbols that help programmers visualize input, processing and output operations to be performed by a computer program. Unlike natural languages and pseudocode, use of standardised symbols makes the flowcharts easier to interpret hence more universally acceptable. Table 7.1 below gives a brief description of six standard symbols used to create flowcharts.The example shown in Fig. 7.3 depicts a flowchart that takes radius as input

to calculate and display area of a circle.**Explanation**

1. The first symbol indicates start of the flowchart.

2. The parallelogram (second symbol) indicates the algorithm takes radius as input.

3. The rectangle indicates that:

(i) Pi is assigned constant 3.142

(ii) The area is calculated as Pi × radius2

4. The fourth box display Area as output

5. The last symbol is the exit.

The following are general rules that may be followed when expressing an algorithm

using flowchart:

1. Be sure to use the right symbol for the right purpose. For examples it is wrong

to use a terminal symbol for input.

2. All the symbols of a flowchart should be connected using arrows (flow lines)

and not plain lines.

3. The direction of flow should be from top to bottom, or sides depending on the

page layout.

4. The start and end of a flowchart must be indicated with (start/stop) terminal

symbol.

5. Flowchart should have only one entry point at the top and one exit point at the

bottom or side.

6. The decision symbol should have only two exit points for either true or false

on the sides, or bottom and one side.

7. If a flowchart does not fit one page or column, use connectors to indicate breaks

in the flowchart**Advantages of using flowcharts**

The following are some the advantages of using flowcharts to express an algorithm:

1. Flowcharts are better way of communicating the system logic.

2. With a flowchart, problem can be analysed in a more effective way.

3. Graphical representation of design serves as good program documentation.

4. Flowchart makes it easier to debug and maintain a program.**Activity 7.3: Expressing algorithm using flowcharts**

1. Given that more emphases in algorithm design is on use of flowcharts and pseudocodes, differentiate the two algorithm design tools giving advantages of each.

2. Consider Neza’s case of FRW 200 000 deposit in a bank at interest rate of 8% per annum for a period of five years. Revisit the problem in Activity 7.2 and design a flowchart that would be used to keep track of interest earned each year.**Assessment Exercise 7.1**

1. Distinguish between pseudocode and flowchart. In each case, give advantages and disadvantages.

2. Jane wanted to design an examination system to be used in her school. Advise her on three algorithm design tools she may use.

3. Using illustrations, explain at least four standard symbols used in flowchart design.

4. In reference to decision flowcharts, differentiate between decision symbol and connector.

5. Explain three circumstances that may prompt a programmer to use a pseudocode instead of a flowchart.

6. State three advantages of using flowcharts over pseudocode in formulating an algorithm.

7. Hakizimana intends to automate library services starting with members registration. Draw a hierarchical diagram for the overall library system.**7.3 Variables**

A variable can be defined as a name also known as identifier that represents data values which can change. For example, in a mathematical problem of calculating area of a circle, radius can take any value as shown in table 7.2. Therefore, radius is an input variable while area is an output variable.If this problem is solved using as a computer program, radius and area variables represents memory locations reserved to hold values that change during program execution as shown in the table.

**7.3.1 Rules of Naming Variables and Keywords**

The name given to variable is matter of choice by a programmer subject to the following rules:

1. Choose meaningful variable names that tell the reader of the program what the variable represents. For example, use sum instead of just s.

2. Each variable in the same algorithm should be identified using a unique name. For example you cannot use balls represent input, and balls to represent output

3. By convention, variable names should begin with a letter of the alphabet but may be followed by numbers. For example, use balls3 instead of 3balls.

4. Avoid using variable names that may conflict with reserved or keywords used in most programming languages.

5. Variable names made up of two or more words should not have space in between

the words, instead combine the two words or use an underscore. For example,

instead of using Basic Salary as variable name, use BasicSalary or Basic_salary.**7.3.2 Declaration of Variables**

Declaration of variable refers to identify and explicitly state input and output variables required to solve a problem. For example, suppose you are required to solve a problem of finding sum and average of three numbers. To identify and state input and output variable from the problem, proceed as follows:

1. Express the problem using natural language in order to identify input, processing and output requirements as shown below:2. Identify a statement or statements that indicate input is required. In the above

algorithm, input is implied in the statement “Accept user input for 3 numbers.”

The statement implies that the user is expected to input numbers on the keyboard.3. Represent the input values as variables using symbolic names such as Num1,

Num2, and Num3.

Identify a statement or statements that indicate the algorithm provides output.

The algorithm indicates output using a statement “Display the reults.” Deeper

look at the algorithm points the result to calculated sum as average

4. Represent the output values as variables using symbolic names such as Sum,

Average

5. Rewrite the algorithm to indicate the input and output variables as shown below:**NB:**Variable names should not have spaces between words. Instead use an underscore

to combine two words or start the next work with uppercase.**7.3.3 Data types**

In programming, data type determines the type of values that can be stored in a

variable. Most programming languages supports the following primary data types:**• Integers:**Integers are whole numbers, which can either positive or negative

including zero. For example, 0, 5, -20, and 68 are integers.**• Real Numbers:**These are numbers with a fractional part. Normally, the fractional

part follows a decimal point. For example, 68.67 is a real number.**• Character:**Character data, sometimes referred to as “string” data, may consist

of any digits, letters of the alphabet or symbols which**• Boolean:**Bolean data type is a type that can only take two values - true or fale.

In logic, the true value is represented by one (1) while false is represented by zero(0).

In addition to primary data types, most programming languages support composite

data types. A composite data type such as array, record and linked list is obtained by

combining several primary data types.**7.3.4 Initialisation of Variables**

Once a variable is declared it does not have a defined value, hence it cannot be used

until it is initialised by assigning it a value. Initialising a variable goes beyond

declaration to assign an initial value to a variable. For example, in our previous

algorithm, we can initialise variables Num1, Num2, Num3 with initial values as

shown below:**Input: Num1= 3, Num2 =5, Num3 =7**,

The statement assigns the values to the variables such that if the algorithm is

implemented, the initial sum and average before any user input is calculated as:**Sum = 3+ 5 + 7; this returns 15**

Average = 15/3; returns 5

Note that in a real program, if a variable has been declared but not initialised, the

memory location contains nothing, hence we say it holds a null until the user enters

values to be assigned to the variable. Fig. 7.4 shows how to initialise variables_A,

Temporary and Variable_B.**Activity 7.4: Declaring variables**

1. In mathematics a variable is a symbolic number whose value is unknown yet.

Identify variables in the following algebraic expressions:

• y = mx + c

• ax^{2}+ bx + c = 02. Study the pseudocode below and identify input and output variables. In each

case, indicate data type for each variable.**7.4 Constants**

Unlike a variable which is an identifier for values that can change, a constant is a fixed value which cannot be changed. In mathematics and physics, examples of constants include pi (π), speed of light, and gravity. For example, referring back to the problem of calculating area of a circle discussed earlier, π is a constant whose value is 3.142. If implemented as a program, the value of π can never be changed during the program execution.**Activity 7.5: Definition of constants**

In mathematics and physics, a constant is a value that does not change. Study the algebraic expressions restated below and identify constants:

• y = mx + c

• ax^{2}+ bx + c = 0**Declaration of Constants**

Declaring a constant refers to specifying a symbolic name for a value that cannot be changed during program execution.

In algorithm design constants may be declared as string or numeric constants.

A string constant is a sequence of characters such as “FRW 7200” that cannot

be manipulated mathematically while numeric constants such as 7200 can be

manipulated in a mathematical expressions. For example, to calculate area of a circle,

we can declare π (pi) as a numeric (constant) as follows:**• const double PI= 3.142**

The pseudocode of Fig. 7.6 illustrates an algorithm in which TAXRATE and

DAILY_RATE are declared as numeric constants.**Activity 7.6: Declaring constants**

Using internet, download introduction to C++ tutorials and familialise yourself with basic concepts. Using knowledge acquired from the tutorials explain the full meaning

of constant declaration const double PI= 3.142.**7.5 Operators and Expressions**

To write correct mathematical expressions, you need to understand operators used

in programming languages namely: assignment, arithmetic, relational, and logical operators.**7.5.1 Assignment operators**

The assignment operators such as (=) or (:=) causes the operand on the left side of the

operator to be replaced by the value on the right side. For example, in the following

expression, the value of x is replaced by the sum of a and b.

• x = a + b**Activity 7.7: Operators and expressions**

The order of evaluation of an arithmetic expression follows the rule known as

BODMAS. In a class discussion, brainstorm on how BODMAS relate to precedence

rule in evaluating the expressions.

x + y–10 × 13/y**7.5.2 Arithmetic operators**

Arithmetic operators are used to evaluate the four basic arithmetic operations: addition

(+), subtraction (-), division (/) and multiplication (*). In an expression such as 3+2,

addition operator adds the two operands to return a value, hence it is referred to as a

binary operator.**7.5.3 Relational operators**

Relational operators are used in boolean expressions that compares numeric or string

constants and returns a true or false. Such operators include: greater than (>), less

than (<), equal to ( =), less than or equal to (<=), greater than or equal to (>=), and

not equal to (< >). Relational operators are binary operators because they act on two

operands e.g. 5>3 that returns true.**7.5.4 Logical operators**

Logical operators derived from Boolean algebra are used on compound expressions

or conditions to return true or false. The three logical operators used in most

programming languages are AND, OR and NOT. Unlike AND and OR which are

binary operators, NOT is a unary like tild (~) in mathematics. This means that it

negates the operand on its right side; e.g. NOT true returns false.**Activity 7.8: Logical operators**

Consider a task of designing an automated alarm system that has the logic: “If the

door alarm sounds AND it is after six p.m. AND it is NOT a holiday, OR if it

is a weekend, then call the police.” Write a statement that would implement the

alarm logic**7.5.5 Bitwise operators**

Bitwise operators are similar to logical operators only that they are specifically used

to manipulate binary digits. The main Bitwise operators are AND, inclusive OR,

exclusive OR (XOR), NOT (~), binary left shift (<<), and binary right shift (>>).

Activity 7.9: Bitwise operators

1. Using sample expressions, distinguish between logical operators and bitwise

operators.

2. Study the truth table shown on Table 7.3 below and indicate values returned by

evaluating the expressions. Note that 1 is a binary value representing true and

0 represents false.3. Design an algorithm for a program that would evaluate the following compound

statements:

• If (x = 30) AND (gender = “male”).

• IF (x = 20) OR (y <10).

• If (NOT false) OR (size > 5.4).**7.5.6 Precedence of operators**

Precedence of operators refers to established rule that assigns priority of each

operator used in an expression. For example, when writing complex expressions in

mathematics, we use precedence rule known as BODMAS that stands for Brackets,

Off, Division, Multiplication, Addition, and Subtraction. BODMAS rule means

that the highest priority is assigned to Bracket, with the lowest priority being assigned

to Subtraction. For example, in the expression below, unless we apply BODMAS

rule, the answer could be 6.5!

x = 5 + 8 ÷ 2

x = (5 + 8) ÷ 2 (if evaluated from left to right, we get 6.5)

x = 5 + (8 ÷ 2) (with BODMAS rule the result is 9)

Like BODMAS in mathematics, we use precedence rule in algorithms to assign

priority to each of the arithmetic, relational and logical operators. Table 7.4 shows

the order of precedence in each of the four categories from the highest to the lowest.**NB:**In case an expression has multiplication and division such as 8*3/4, evaluation

is carries out from left to right.**7.6 Read and Write functions**

Functions are “self-contained” group of statements that accomplish a specific task.

In algorithms, the read function gets data from input devices like keyboard while

write functions prints output on devices such as screen.**7.6.1 Read functions**

To represent read functions in an algorithm, we use keywords like READ, INPUT, and

GET. For example, the following statements demonstrate how to use read functions

to get radius as input from keyword:Good practice in algorithm design requires the READ functions to be in uppercase

while values to be read also known as parameters to be in lowercase. For clarity,

if a function is to read several paramenters, parenthesis may be used to enclose the

parameters as shown below:**7.6.2 Write Functions**

Like in read operations, we use keywords like WRITE, DISPLAY, and SHOW to

represent functions that display information on the screen. For example, the following

statements demonstrate how to display area on the screen:For clarity, if a write function is to display several values, parenthesis may be used

to enclose the parameters as shown below:**Activity 7.10: Read and write functions**

1. Using read and write functions, formulate an algorithm that computes roots of

x from the following quadratic expressions = ax2 + bx + c.

2. Sebahive took a loan of FRW 400,000 from a local bank at interest rate of 12%

annually. Assuming the loan should be paid back in 4 years time, use read and

write functions in a pseudocode that computes monthly loan repayment.**Assessment Exercise 7.2**

1. Design an algorithm for a program that would be used to solve a quadratic equation:

y = ax^{2}+ bx + c.

2. Design an algorithm for a program that would be used to compare three numbers

x, y and z, and then display the least among the three.

3. Differentiate between read function and write functions as used in algorithms.

4. Jere deposited FRW 200,000 in his savings account. The amount deposited earns

a 3% annual interest. Design an algorithm that would be used to calculate interest

after n years.**Unit Test 7**

1. Explain the following algorithm concepts:

(a) Precedence rule

(b) Variables

2. To get estimate the rate of fuel consumption, Lemba needs to calculate kilometres

per litre consumed by his car. Design an algorithm for a program that lets Lemba:

(a) Enter current fuel reading and after refilling.

(b) Enter kilometres and fuel reading after driving for at least 30 km on a highway.

The computer should then calculate and prints estimated consumption in km/

litre.

3. Draw a flowchart that prompts for five numbers, and then calculates sum and

average. The computer should display total sum and average of the five numbers.

4. Draw a flowchart that reads temperature for each day in a week, in celsius, converts

the celsius into fahrenheit and then calculate the average weekly temperatures.

The algorithm should display weekly average temperature in degrees fahrenheit.

5. Nyframahoro deposited FRW 2000 in a Micro-finance company at an interest rate

of 20% per annum. At the end of each year, the interest earned is added to the

deposit and the new amount becomes the deposit for that year. Draw a flowchart

that would track the growth of deposits over a period of seven years.