Lecture Notes :

Algorithms and Data Structures I

Introduction to Algorithms and Programming

Academic year : 2023-2024.

1st Year Mathematics License,

Faculty of Mathematics,
University of Science and Technology Houari Boumediene.

Content :
• Overview of the lecture’s goals and syllabus.
• Understanding the concept of Algorithms and Programs.
• Pseudocode sketching and Input/Output Operations

1/38
Making a Cup of Tea

• Let’s make a cup of tea :

1. Boil Water.
2. Prepare the Teacup.
3. Pour Hot Water.
4. Steep the Tea.
5. Remove the Tea Bag.

• An algorithm can be compared to a cooking recipe.

• Roughly, an algorithm is a complete, detailed description of the actions to be

performed and their order to achieve a given result.

2/38
Historical Milestones

3/38
Algorithms are useful!

Algorithm = Solving Method

• An algorithm is used to transmit know-how, skill, etc.

• It describes the steps to follow to complete a job.

• The user of an algorithm simply has to follow the instructions, in the right
order, to get a solution to a given problem.

Algorithmics = Study and Analysis of Algorithms

4/38
What is an Algorithm?

→ The word Algorithm comes from the Latinized name of the Persian
mathematician Al-Khawarizmi.
→ Algorithms are the basis of all computer programming.

Definition of an Algorithm
An algorithm is
• a finite sequence of well-defined,
• unambiguous,
• and executable steps or instructions,
that solve a particular problem.

→ It provides a systematic approach to problem-solving by breaking down complex

tasks into simpler, discrete operations that can be carried out methodically. 5/38
What is an Algorithm?

→ Informally, an algorithm is any well-defined computational procedure that takes

some value, or set of values, as input and produces some value, or set of values, as
output in a finite amount of time.

An algorithm is thus a sequence of computational steps that transform the

input into the output.

Example

suppose that you need to sort a sequence of numbers into monotonically

increasing order.
Input: A sequence of n numbers a1 , a2 , . . . , an .
Output: A permutation (reordering) a′1 , a′2 , . . . , a′n of the input sequence such
that a′1 ≤ a′2 ≤ · · · ≤ a′n . 6/38
Properties of Algorithms

An algorithm must:

• have a finite number of steps,

• terminate after a finite number of operations,
• provide a result.
• sequences (steps) follow one another in a certain order.
• Each step must be rigorously and unambiguously defined.
• An algorithm has a beginning and an end.

7/38
Manifestation of Algorithms

• Human-Human communication :
• Natural language description : Set of instruction written in human language.

• Flowcharts : Graphical representation using forms and symbols.

• Pseudocode: uses a combination of natural language and simplified

programming-like constructs that can be extremely detailed.

• Human-Machine communication :
• Computer programs, also called codes.

8/38
From Algorithms to Programs

Code/Program = Algorithm translated to a "computer

language"

→ Coding/programming : writing algorithms that are "understandable" by

computers using a Programming Language.

A program is an implementation of an algorithm using a specific

programming language. It is a set of instructions written in code that can
be executed by a computer to carry out a task or solve a problem.

9/38
From Algorithms to Programs

Programming is the process of writing code to instruct a computer to perform

a task.

It involves:

• Writing code in a predefined syntax rules, called a programming language.

• Debugging and testing code.
• Running/executing programs.

Syntax are rules and symbols used to express instructions.

10/38
General Structure of an Algorithm

An algorithm consists of two parts:

• Declarative part: also called the algorithm header, it generally contains
declarations related to the needed memory space.
• Body part of the algorithm: consisting of a sequence of instructions
calling for operations to be executed.

Syntax
Algorithm Name_of_algorithm ;
< List of variables and/or constantes > ;
Begin
< Sequence of instructions > ;
End
11/38
Units of Measurement : A Memory Cell

Memory Cells: Computer memory consists of numerous memory cells, each

capable of storing a single basic information.
→ These cells are typically grouped into storage units:

• A bit (binary digit) is a binary element. Its value is either 0 or 1.

• A byte is a set of 8 bits. Commonly used lengths are sets of 16, 32 or 64 bits.
• A kilobyte (abbreviation: KB) corresponds to 1024 bits, or 210 bits.
• One megabyte (MB) corresponds to 1024 KB, or 210 KB.
• A gigabyte (GB) is 1024 MB, or 210 MB.
• These units of measurement are frequently used to indicate memory sizes (or
capacities).

12/38
Binary representation: Overview

The value of a binary number is calculated as the sum of each digit (0 or 1)

multiplied by 2 raised to the power of its position from right to left.

Example

In the binary number 1101:

Decimal 23 22 21 20
13 1 1 0 1
Binary

That is,

1 · 23 + 1 · 22 + 0 · 21 + 1 · 20 = 8 + 4 + 0 + 1 = 13 in decimal.

13/38
Binary representation: Overview

Let bn , bn−1 , . . . , b2 , b1 , b0 be a binary number with n + 1 digits (from left to right),

where each bi can be either 0 or 1. The decimal equivalent of this binary number is
calculated as: n
X
D= bi · 2n−i .
i=0

• D represents the decimal equivalent. n is the highest power of 2 in the binary

number (i.e., the number of digits minus one).
You can use this formula to convert any binary number into its decimal
representation.

n bit can represent integers up to 2n − 1.

Example: with 8 bits (a byte), one can represent values from 0 to 255 (28 − 1).
14/38
Data Storage in programming

In programming, memory addresses are represented by names. The programmer

doesn’t know the address of a cell, but rather its name. So there are two ways of
looking at the computer’s main memory: from the programmer’s side and from the
computer’s side.

Computer side Programmer side

Address Word Name
11010010 8 a
11010011 2 f
11010100 5 average
.. .. ..
. . .

15/38
Variables and Constants

• A variable is a memory cell designed to hold values (numbers, characters, etc.).

It has a name, a type and a content that can be modified during
algorithm execution. The keyword is: Var
• The definition of a constant is the same as that of a variable, with the difference
that its value remains unchanged throughout the execution of the algorithm.
The keyword is: Const

Syntax
Var <variable_ID> : <type> ;
Const <constant_ID> = <value> ;

16/38
ID choice

Remark:
The choice of variable names is subject to a few rules:
• A name must begin with an alphabetical letter.
! • Must be different from reserved words (e.g.: integer, float, else,
switch, case, for, return, etc.)

Examples

→ Valid exampled: A1, pi, alpha, x, y.

→ invalid examples: 1A, for, end, 11.

For readability, choose meaningful names that describe the data being manipulated.

17/38
Variables and Constants

• An identifier <variable_ID> and <constant_ID>: is a name assigned to

the variable or constant, which can be made up of letters and numbers
but without spaces.
• A type: defines the nature and size of the variable.

Example
Var a, b : Integer;
Const pi = 3.14;

In this example, we have declared :

• Two variables a and b of integer type, described in the next subsection.
• A constant pi equal to the value 3.14 as an example

18/38
Integer Type

• This is a numeric type representing the set of relative integers, such as:
−9, 0, 31, . . . etc.
• The operations allowed on this type are: +, - , *, div (integer division) and
mod (modulo or remainder remainder of integer division).
• The keyword is: integer.

Example
Var x : integer;

19/38
float Type

• This is a numeric type representing the set of float numbers, such as

0.25, −1.33, 2.5e + 10, . . . etc.
• The keyword is: float.

Example
Var y : float;

20/38
Character Type

• This type represents all alphanumeric characters, such as ’a’, ’A’, ’3’, ’%’, space,
etc.
• Operations supported by this type: =, , <, <=, >, >=.
• The keyword is: character.

Example
Var a : character;

21/38
Boolean Type

• This type is used in logic to represent two values: true and false.
• The operations supported are: NOT, AND, OR.
• The keyword is: boolean.

Example
Var b : boolean;

22/38
Declarations Examples

Var x, y : integer;
z, w : float;
letter : character;
name : string;
Status: boolean;
Const n = 100;
arobase = ’@’;
word = "hello";

23/38
Assignment

• Assignment is the most basic instruction used in an algorithm.

• Assignment consists in setting a value to a variable.
• In other words, filling or modifying the contents of a memory cell.
• In pseudocode, the assignment is noted with the sign ←.

Syntax
<variable_ID> ← <value>;

Example
x ← 8;

24/38
Assignment : Example 1

Example
Algorithm Assignment_Example ;
Var x, y : integer ;
Begin
x ← 2 ;
y ← 5 ;
End ;

This algorithm stores the values 2 and 5 in the variables x and y:

x 2 y 5

25/38
Assignment : Example 2

Example
Algorithm Assignment_Example ;
Var x, y : integer ;
Begin
x ← 2 ;
x ← 1 + 2 ;
y ← x ;
y ← x + 2 ;
y ← x + y ;
End ;

26/38
Exercise : permutation of two variables

Write an algorithm that permutes the values of two variables.

Algorithm Permutation ;
Var x, y, i : integer ;
Begin x y i
x ← 2 ; - - - - - 2
x ← 8 ; - - - - - 2 8
i ← y ; - - - - - 2 8 8
y ← x ; - - - - - 2 2 8
x ← i ; - - - - - 8 2 8
End ;

27/38
Exercise : permutation of two variables

Write an algorithm that permutes the values of two variables without an

intermediate variable.

Algorithm Permutation ;
Var x, y: integer ;
Begin x y
x ← 2; - - - - - 2
x ← 8; - - - - - 2 8
x ← x + y ; - - - - - 10 8
y ← x - y ; - - - - - 10 2
x ← x - y ; - - - - - 8 2
End ;

28/38
Arithmetic Operations

• Arithmetic operations are fundamental mathematical calculations used in

everyday life and programming.
• Let’s explore various operations: Addition, Subtraction, Multiplication,
Division, Modulo, Integer Division, and Exponentiation.

Operation Symbol
Addition +
Subtraction −
Multiplication ∗
Division /
Modulo % or mod
Integer Division div
Exponentiation ˆ or ∗∗
29/38
Arithmetic Operations

Using the assignment and the arithmetic operations, we can calculate:

Syntax
Addition: Result ← A + B A+B
Subtraction: Result ← X − Y X −Y
Multiplication: Result ← M ∗ N M ×N
P
Division: Result ← P/Q
Q
Modulo: Result ← D mod E result ≡ D[E]
Integer Division: Result ← Z div W
Exponentiation: Result ← R ∗ ∗S RS

30/38
Relational Operations

Common Relational Operations and Symbols

• Greater Than (>): It’s true if the left value is greater than the right
value.
• Less Than (<): It’s true if the left value is less than the right value.
• Greater Than or Equal To (>=): It’s true if the left value is greater
than or equal to the right value.
• Less Than or Equal To (<=): It’s true if the left value is less than or
equal to the right value.
• Equal To (=): It’s true if the left value is equal to the right value.
• Not Equal To (! =): It’s true if the left value is not equal to the right
value.
31/38
Logical Operations

• Logical operations are used to manipulate Boolean values (true or false) in

programming.
• Let’s explore some basic logical operations:

Common Relational Operations and Symbols

AND (&) : Result ← A&B (true if both A and B are true)

OR (|) : Result ← X|Y (true if either X or Y is true)
NOR : Result ← NOR(P, Q) (true if neither P nor Q is true)
NAND : Result ← NAND(D, E) (true unless both D and E are true)
NOT (!) : Result ←!Z (inverts the value of Z)

32/38
Operator Precedence Order

For Arithmetic and Concatenation Operators:

1. Parentheses
2. Exponentiation
3. Multiplication (x) and Division (/)
4. Modulus (mod)
5. Addition (+) and Subtraction (-)
For Logical Operators:
1. NOT (non)
2. AND (et)
3. OR (ou)
33/38
Input/Output Operations

• Input and output operations are essential in algorithms for processing data.

• They allow an algorithm to communicate with the external world.

• Input operations involve receiving data from external sources, such as the user.
• Output operations involve sending results or information to external destinations,
like displays or files.

Input Algorithm Output

34/38
Input Instruction

• It allows you to read input values and assign them to variables stored in
memory.
• The values assigned are often data entered from an input device such as the
keyboard. Syntax:

Syntax
Read(<var1_ID>, <var2_ID>, ...);

• Read(x): reads and stores a given value in the memory location

associated with x.
• Read(x, y): reads and stores two values, the first in x and the second
in y.
35/38
Output Instruction in Algorithms

It allows the algorithm to write the output data resulting from a processing
(value, text, etc.) by displaying them, for example, on an output device such as
the screen.
Syntax:
Write(<var1_ID>, <var2_ID>, <expr1>, <expr2>, ...);

Remark:
In the case of writing an expression, it is the result of the evaluation of that
! expression that is displayed, not the expression itself.
Example

Let’s consider two variables, x and y, such that x = 5 and y = 7. The

instruction: Write(x+y); Displays the result of adding x and y (which is 12). 36/38
Example IO Operations

Algorithm Average_of_two_floats;
Var x, y, z: float;
Begin
Write ("Enter the first value: ");
Read (x);
Write ("Enter the second value: ");
Read (y);
z <- (x + y) / 2;
Write ("The average is: ", z);
// Alternatively, you can use a single line:
Write ("The average is: ", (x + y) / 2);
// In this case, you don’t need z
End; 37/38
Example IO Operations

Write an algorithm that calculates the area of a circle using the formula: Area =
Radius * Radius * Pi.

Algorithm Circle_Area;
Const Pi = 3.14;
Var Radius: integer;
Area: float;
Begin
Write("Enter the radius value: ");
Read(Radius);
Area <- Radius * Radius * Pi;
Write("The area of the circle is: ", Area);
End;
38/38