Computer Science

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² + bx + c = 0

2. 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² + 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² + 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.