Algorithms & Data Structures

Modules ASD 1, ASD 2 & ASD 3

License in Computer Science – Semesters 1, 2 & 3

ASD 1: UEF12 – Credits 7, Coefficient 5

ASD 2: UEF22 – Credits 7, Coefficient 5

ASD 3: UEF31 – Credits 6, Coefficient 5

Language: C (recommended for implementation)

Evaluation: Exam (60%) + Continuous (40%)

A simple, visual course with flowcharts and diagrams

With real examples from Algerian businesses:

Yassir, Jumia, Djezzy, Sonatrach, Condor, Baridi Mob

Algorithms & Data Structures By Benabderrezak Youcef

Licence Informatique

2
Algorithms & Data Structures By Benabderrezak Youcef

Contents

1 Introduction to Algorithms 9

1.1 What Is an Algorithm? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 The Problem-Solving Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3 Structure of a Computer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2 Simple Sequential Algorithm 15

2.1 Writing an Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2 Variables, Constants and Basic Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3 The Three Basic Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.4 The Flowchart (Organigramme) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.5 Translating to C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.6 Five Worked Examples (Algorithm + C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3 Conditional Structures 28

3.1 Why Make Decisions? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.2 Simple and Double Condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.3 Nested and Multiple Choice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3
Algorithms & Data Structures By Benabderrezak Youcef

3.4 Five Worked Examples (Algorithm + C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4 Repetitive Structures (Loops) 38

4.1 Why Loops? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.2 The Four Parts of Every Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.3 The Three Loops – Which One to Use? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.4 Example: Sum of Transfers (For loop) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.5 Nested Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4.6 Five Worked Examples (Algorithm + C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5 Arrays and Strings 47

5.1 One-Dimensional Array (1D) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.2 Two-Dimensional Array (2D / Matrix) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.3 Strings (Character Arrays) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.4 Five Worked Examples (Algorithm + C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

6 Custom Types 57

6.1 Structure (Record) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

6.2 Enumerations and typedef . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

6.3 Five Worked Examples (Algorithm + C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4
Algorithms & Data Structures By Benabderrezak Youcef

7 ASD 1 – Solved Exercises 64

8 Subprograms: Functions and Procedures 70

8.1 Why Subprograms? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

8.2 Local vs Global Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

8.3 Passing Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

8.4 Five Worked Examples (Algorithm + C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

8.5 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

8.6 Five Worked Examples (Algorithm + C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

9 Files 83

9.1 Why Files? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

9.2 Types of Files and Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

9.3 Five Worked Examples (Algorithm + C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

10 Pointers and Dynamic Memory 90

10.1 What Is a Pointer? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

10.2 Dynamic Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

10.3 Five Worked Examples (Algorithm + C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

11 Linked Lists 97

5
Algorithms & Data Structures By Benabderrezak Youcef

11.1 Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

11.2 Array vs Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

11.3 Operations on a Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

11.4 Doubly Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

11.5 Stacks and Queues (Special Lists) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

11.6 Five Worked Examples (Algorithm + C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

12 ASD 2 – Solved Exercises 106

13 Algorithmic Complexity 112

13.1 Why Measure Complexity? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

13.2 Common Complexity Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

13.3 Computing Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

13.4 Five Worked Examples (Algorithm + C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

14 Sorting Algorithms 116

14.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

14.2 Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

14.3 Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

14.4 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

6
Algorithms & Data Structures By Benabderrezak Youcef

14.5 Merge Sort (Divide and Conquer) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

14.6 Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

14.7 Five Worked Examples (Algorithm + C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

15 Trees 121

15.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

15.2 Binary Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

15.3 Tree Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

15.4 Binary Search Tree (BST) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

15.5 Five Worked Examples (Algorithm + C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

16 Graphs 126

16.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

16.2 Representing a Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

16.3 Graph Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

16.4 Five Worked Examples (Algorithm + C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

17 ASD 3 – Solved Exercises 130

Summary 133

7
Algorithms & Data Structures By Benabderrezak Youcef

MODULE ASD 1
Sequential Algorithms, Conditions, Loops, Arrays

8
Algorithms & Data Structures By Benabderrezak Youcef

1 Introduction to Algorithms

1.1 What Is an Algorithm?

The intuition first. Before any definition, picture something you already do perfectly: giving a friend directions to

your house. “Leave the metro at Tafourah, walk straight for 200 m, turn left at the pharmacy, my door is the blue one.”

You just gave an algorithm – a list of exact steps that, if followed in order, always leads to the same place. You did not

need a computer; you needed clear thinking. That is the real subject of this course: not C, not machines, but the skill

of describing a solution so precisely that even a mindless follower reaches the correct result.

Why does this concept exist? A computer is astonishingly fast but astonishingly literal: it does exactly what it

is told, in the exact order, and never guesses what you “meant”. So before we can make a machine solve a problem,

a human must first break that problem into steps so unambiguous that no guessing is possible. The word for such a

step-list is algorithm. It exists to bridge the gap between a fuzzy human wish (“sort these prices”) and the rigid literal

machine.

What problem does it solve? It lets us separate thinking from coding. First we design the steps (the algorithm),

calmly, on paper, in plain language. Only afterwards do we translate those steps into a programming language. This

separation means one good algorithm can be reused in C, Python, or Java – the idea does not change, only the spelling.

▶ In plain words: Think of an algorithm as a recipe. A recipe has ingredients (input), steps in a fixed order

(work), and a finished dish (output). Follow the same recipe and you always get the same dish. A computer is

just a very fast, very obedient cook that never improvises – so your steps must be exact and in the right order, or

the dish comes out wrong.

An algorithm is a finite list of clear steps that solves a problem. It takes an input, does some work, and gives an

output.

9
Algorithms & Data Structures By Benabderrezak Youcef

It is independent of any programming language – the same algorithm can be written in C, Python, or Java.

Every keyword in that definition, explained:

• finite – the steps must end. A list that runs forever is not an algorithm. (A washing machine that never stops is

broken, not clever.)

• clear steps (also called definite) – each step has exactly one meaning; “add a bit of salt” is not clear, “add 2 g of

salt” is.

• input – the data you start with (the amount to transfer, the list to sort). An algorithm may have zero or many

inputs.

• work – the ordered steps that transform input into output.

• output – the answer produced (the receipt, the sorted list). At least one output is expected – otherwise, why run

it?

• independent of language – the algorithm is the idea; C/Python/Java are just different alphabets for writing the

same idea.

The 5 classic properties (a good algorithm has all of them): finiteness (it stops), definiteness (no ambiguous step),

input, output, and effectiveness (each step is simple enough to actually be carried out).

Everyday Algerian examples:

• Making mint tea: boil water → add tea → add sugar → pour. A fixed order of steps.

• Yassir app: take your GPS position (input) → find nearest driver (work) → show price and time (output).

• Baridi Mob transfer: enter amount → check balance → move money → print receipt.

Where algorithms are used: literally everywhere a decision or computation happens – GPS routing (Yassir),

ranking products (Jumia), matching a fingerprint to unlock your phone, compressing a photo, recommending a song.

Learning to design algorithms is learning the native language of every digital device.

Advantages of thinking in algorithms: (1) you can check a solution is correct before writing a single line of code;

10
Algorithms & Data Structures By Benabderrezak Youcef

(2) the same design works in any language; (3) you can compare two solutions and pick the faster one (Module ASD

3); (4) you can explain your idea to another human.

Limitations: an algorithm is only as good as the thinking behind it. It cannot solve a problem you have not

understood, it cannot fix wrong or missing input (“garbage in, garbage out”), and some problems have no fast algorithm

at all – a theme you will meet again in complexity.

Common beginner mistakes. (1) Vague steps – “sort the list” is a wish, not a step; you must say how. (2) Wrong

order – pouring the tea before boiling the water; order is part of the meaning. (3) No stopping point – forgetting

when to end, so the recipe never finishes. (4) Assuming the computer will “understand” – it will not; it only

obeys.

▶ In plain words: Think about it: could a person who has never seen your problem follow your steps and still

get the right answer, without asking you a single question? If yes, you have an algorithm. If they would need to

ask “what do you mean here?”, that step is not clear enough yet.

1.2 The Problem-Solving Cycle

Why a “cycle” and not just “write code”? The single biggest mistake a beginner makes is to open the editor and start

typing C immediately. That is like building a house by laying bricks before drawing a plan – you get a wall, but not a

house. Experienced programmers spend most of their time thinking, and very little typing. The four stages below force

that discipline: understand before you design, design before you code, and code before you trust the result.

Real-life analogy. Building anything real follows the same path: an architect first studies what the client needs

(Analysis), then draws plans (Algorithm), then workers build from the plans (Program), and finally an inspector checks

the finished building (Execution). Skip the plans and the workers guess; skip the inspection and the roof may leak.

To make a computer solve a problem, we go through 4 stages. This is the heart of ASD 1.

1. Analysis 2. Algorithm 3. Program 4. Execution

understand problem write the steps translate to C run & test

11
Algorithms & Data Structures By Benabderrezak Youcef

The four stages, one by one – what you do, why it matters, and what breaks if you skip it:

1. Analysis – understand the problem. Ask: what is the input? what is the wanted output? what are the rules and

special cases (empty list? negative amount?). Why: you cannot solve what you have not understood. If skipped:

you build the wrong thing perfectly.

2. Algorithm – design the steps. Write the solution in plain, ordered steps (pseudocode or a flowchart), still

language-free. Why: this is where the real problem-solving happens, cheaply, on paper. If skipped: you code by

trial-and-error and get lost.

3. Program – translate to C. Now, and only now, rewrite each step as C code. This stage is mostly mechanical if

the algorithm is good. Why: the machine needs a language it can run. If skipped: you have an idea but nothing

executes.

4. Execution – run and test. Feed real inputs, compare the output to what you expected, fix mistakes (debugging).

Why: an untested program is only a hope. If skipped: bugs reach the user.

▶ In plain words: The arrows point forward, but in practice the cycle loops back: testing (stage 4) often reveals

a misunderstanding (stage 1), so you refine and go round again. This is normal and healthy – good software is

grown, not typed once.

Common beginner mistake: jumping straight to stage 3 (coding). Symptoms: you stare at a blank screen, or you

write code that “almost” works but you cannot say why. The cure is always to step back to stage 1 or 2 – write

down, on paper, what the input and the steps really are.

1.3 Structure of a Computer

Why learn the hardware in an algorithms course? Because every line you will write moves data between just a few

places. When you understand where a variable lives and who does the arithmetic, ideas like “read into a variable”, “the

program runs one step at a time”, or “the disk keeps data after shutdown” stop being magic and become obvious. You

do not need electronics – just a mental map of three parts.

Real-life analogy: a cook at a small kitchen counter. The CPU is the cook (does the work, one action at a time).

12
Algorithms & Data Structures By Benabderrezak Youcef

The Memory (RAM) is the counter in front of the cook – small, fast to reach, but wiped clean when the kitchen closes.

The disk is the pantry – huge and permanent, but slow: you must walk to it. I/O is the serving hatch where orders

come in and dishes go out. A cook keeps only what they are using right now on the counter, and stores the rest in the

pantry – exactly how a program uses RAM vs disk.

A computer has three main parts:

• Memory – stores data and programs (RAM = fast/temporary, disk = slow/permanent).

• Processor (CPU) – does the calculations, one instruction at a time.

• Input/Output (I/O) – keyboard, screen, disk. Talks to the outside world.

Each part, explained:

• CPU (Central Processing Unit) – the “brain”. It fetches one instruction, does it, then the next: this fetch–execute

rhythm is why algorithms are a sequence of steps. It is extremely fast (billions of steps per second) but can only

follow orders, never invent them.

• RAM (Random Access Memory) – the working space. Every variable in your program lives here while it

runs. “Random access” means the CPU can reach any cell equally fast. It is volatile: switch off the power and

everything in RAM vanishes.

• disk (hard disk / SSD) – permanent storage. Files, photos, and saved data survive shutdown, but reading the

disk is far slower than RAM (walking to the pantry vs reaching the counter). This speed gap is why we will later

study files separately.

• I/O – keyboard and mouse (input), screen and printer (output). This is how the program talks to the outside

world, e.g. scanf (in) and printf (out).

• bus – the “road” that carries data between CPU, memory and I/O (the arrows below).

13
Algorithms & Data Structures By Benabderrezak Youcef

CPU bus Memory

(processor) (RAM)

Input/Output

Reading the diagram: the double arrows mean data flows both ways. The CPU pulls a value from RAM, computes,

and writes the result back to RAM (CPU ↔ Memory). It also reads from the keyboard and writes to the screen (CPU

↔ I/O). Almost every program is just this dance: get data in, move it between CPU and RAM, send results out.

▶ In plain words: What happens if I forget to save? Your work lived only in RAM (volatile). Cutting the power

wipes it – exactly why unsaved documents are lost after a crash. “Saving” means copying from fast, temporary

RAM to the slow, permanent disk.

Advantages of this design: keeping a small fast memory (RAM) next to the CPU and a big slow one (disk) far

away gives us both speed and permanence. Limitation & common confusion: beginners mix up RAM and disk –

remember, a running variable is in RAM and disappears; a saved file is on disk and stays. Confusing the two

explains most “where did my data go?” bugs.

14
Algorithms & Data Structures By Benabderrezak Youcef

2 Simple Sequential Algorithm

2.1 Writing an Algorithm

Intuition first. In Chapter 1 an algorithm was “a list of clear steps”. But if every programmer wrote those steps in

their own free style, no two people could read each other’s work. So we agree on a fixed skeleton – a standard shape

every algorithm follows. This is exactly like the standard layout of a formal letter (header, greeting, body, signature):

the shape is fixed so anyone can read it instantly.

Why does this structure exist? It answers three questions a reader always has, in order: What is this? (the Title),

What does it work with? (the Declarations – the data), and What does it do? (the Body – the steps). Separating “the

data it uses” from “the actions it performs” keeps even long algorithms readable.

An algorithm has three parts:

1. Title – the name.

2. Declarations – the variables and constants used.

3. Body – the instructions between Begin and End.

Keyword by keyword, in the example below:

• Algorithm TransferFee – the Title. It names the algorithm so we can refer to it (like a filename).

• Variables amount, fee : Real – the Declarations. We announce, before using them, which named boxes

we need and what type they hold. Declaring up front is like laying out your tools before starting work.

• Constant RATE = 0.01 – a fixed value that will never change while the algorithm runs. Naming it RATE makes

the body readable and lets us change the rate in one place.

• Begin ...End – the Body: the ordered instructions, run top to bottom.

15
Algorithms & Data Structures By Benabderrezak Youcef

Algorithm TransferFee
Variables amount, fee : Real
Constant RATE = 0.01 // BaridiMob: 1% fee
Begin
Read(amount)
fee ← amount * RATE
Write("Fee = ", fee, " DZD")
End

Advantages of this fixed structure: any reader finds the data (Declarations) and the logic (Body) in the same place

every time; and it maps almost one-to-one onto a C program (Declarations → variable declarations, Body → statements

in main). Limitation: the skeleton organises steps but does not, by itself, make them correct – that is still your job.

Common beginner mistakes: (1) using a variable you never declared; (2) putting instructions outside the Begin

/ End block; (3) trying to change a Constant in the body (a constant cannot change).

2.2 Variables, Constants and Basic Types

Intuition: a variable is a labelled box. Remember from ğ1.3 that data lives in RAM. RAM is millions of tiny cells;

finding data by cell number would be misery. So instead we give a cell a name – amount, fee – and let the computer

remember which cell that is. A variable is that name + box: you put a value in, read it out, or replace it later.

Real-life analogy. A variable is a labelled drawer. The label (name) never changes, but the contents (value) can

be swapped any time. A constant is a drawer you glue shut after filling it – the label and the contents are fixed forever.

Why do types exist? What problem do they solve? The same bits in a box could mean a whole number, a

decimal, or a letter. The type tells the computer how to read the box and how much space to reserve. It also catches

nonsense early: multiplying two prices makes sense, “multiplying” two names does not. Choosing the right type is the

first correctness decision you make.

A variable is a named box in memory whose value can change. A constant never changes. The basic types:

• Integer – whole numbers: number of drivers, stock quantity.

• Real – decimal numbers: price, distance.

16
Algorithms & Data Structures By Benabderrezak Youcef

• Character – one symbol: ’A’, ’5’.

• Boolean – True or False.

How the pseudocode types map to C (you will need this at every “Translate to C” step):

Pseudocode type C type Example value

Integer int 25, -3
Real float (or double) 3.14, 45999.99
Character char ’A’, ’5’
Boolean int (0 = false, 1 = true) 1, 0

▶ In plain words: Why is ’5’ (character) different from 5 (integer)? The integer 5 is a quantity you can add.

The character ’5’ is a symbol you can print – like the shape drawn on a keyboard key. You can do arithmetic with

5; ’5’ is just a drawing of it. Mixing them up is a classic first-week bug.

Where used / advantages: good variable names (totalPrice, not x) make an algorithm self-explaining; constants

(RATE, PI) put “magic numbers” in one clearly-named place. Limitations: every type has a range – an int cannot

hold arbitrarily huge numbers, and a float stores decimals only approximately (why 0.1+0.2 is not exactly 0.3).

Common beginner mistakes: (1) storing a price in an Integer and losing the centimes; (2) reading into a

variable you forgot to declare; (3) expecting a float to be perfectly exact; (4) reusing one variable for two

unrelated meanings – give each idea its own box.

2.3 The Three Basic Instructions

Why only three? It is a beautiful fact that every sequential algorithm – however long – is built from just three basic

actions: get data in (Read), send data out (Write), and store/compute a value (Assignment). Master these three and

you can already write any straight-line program. Everything later (decisions, loops) only chooses or repeats these same

three.

Analogy. Think of a clerk at a counter: they Read the form you hand in (input), compute your fee on scratch paper

(assignment), and Write the result on a receipt (output). In, work, out.

17
Algorithms & Data Structures By Benabderrezak Youcef

Instruction Meaning Example

Read (input) take value from user Read(amount)
Write (output) show value on screen Write(fee)
Assignment ← put a value in a variable fee ← amount*0.01

Each one, explained:

• Read(x) – pause and copy a value from the keyboard into box x. Whatever was in x before is overwritten. In C:

scanf.

• Write(. . . ) – copy a value out to the screen. It does not change any variable, it only shows it. In C: printf.

• Assignment x ← expr – compute the right side expr, then store the result in box x. The arrow points into the

box on the left.

How assignment really works (read the arrow as “becomes”): the machine first evaluates the whole right-hand

side using the old values, then drops the result into the left box.

Instruction old x right side computes new x

x ← 5 (any) 5 5
x ← x + 1 5 5+1 = 6 6
x ← x * 2 6 6 × 2 = 12 12

Assignment is not equality! x ← x + 1 means “take the old x, add 1, store back”. It is a valid instruction,

not a math equation. As maths, “x = x + 1” is impossible; as an instruction it simply grows x by 1. Also: a ← b

copies b into a (they are not linked afterwards), and it is not the same as b ← a. Direction matters.

2.4 The Flowchart (Organigramme)

Why draw a picture of an algorithm? Text is read line by line, but the human eye grasps shape and flow instantly. A

flowchart (French: organigramme) turns the steps into a diagram so you can see the path the computer takes – especially

useful once decisions and loops make the path branch and circle back. It is the “plan” of stage 2 in the problem-solving

cycle.

18
Algorithms & Data Structures By Benabderrezak Youcef

Why different shapes? Each shape has a fixed meaning, so you recognise the kind of step without reading the

words – like road signs, where a shape alone tells you “stop” or “yield”. This is a worldwide convention.

A flowchart draws an algorithm using shapes:

• Rounded rectangle = Start / End

• Parallelogram = Read / Write (I/O)

• Rectangle = Process (calculation, assignment)

• Diamond = Decision (test yes/no)

The meaning of every symbol:

• Rounded rectangle (terminal) – where execution starts and ends. Every flowchart has exactly one Start and at

least one End.

• Parallelogram (I/O) – talking to the outside world: Read (in) or Write (out).

• Rectangle (process) – internal work: a calculation or an assignment. Nothing leaves or enters the program.

• Diamond (decision) – a yes/no question; the flow splits into two labelled arrows (Yes / No). (You will use this

heavily from Chapter 3 on.)

• arrows – the order of execution: always follow the arrow.

Flowchart – BaridiMob transfer fee:

19
Algorithms & Data Structures By Benabderrezak Youcef

Start

Read amount

fee ← amount × 0.01

Write fee

End

2.5 Translating to C

The idea: once the algorithm is written, translating to C is mostly mechanical – you rewrite each part in C’s spelling.

The table below shows the near one-to-one correspondence; keep it in mind and C stops feeling foreign.

Pseudocode C
Variables x : Real float x;
Read(x) scanf("%f", &x);
x ← expr x = expr;
Write(x) printf("%f", x);
Begin ...End int main() { ...return 0; }

#include <stdio.h>
int main() {
float amount, fee;
printf("Amount in DZD: ");
scanf("%f", &amount);

20
Algorithms & Data Structures By Benabderrezak Youcef

fee = amount * 0.01; // BaridiMob 1% fee

printf("Fee = %.2f DZD\n", fee);
return 0;
}

Every line, explained:

• #include <stdio.h> – brings in the standard input/output toolbox so we may use scanf and printf. Remove

it and the program does not know those names.

• int main() { – execution always begins in main. The { opens the body (the Begin).

• float amount, fee; – declares two Real boxes. Remove it and C complains the names are undefined.

• printf("Amount in DZD: "); – a prompt, so the user knows what to type. Purely for the human.

• scanf("%f", &amount); – read one float from the keyboard into amount. %f = “a float”; the & means “the

address of amount” – i.e. where to store what was typed. Forgetting the & is the #1 beginner scanf bug.

• fee = amount * 0.01; – the assignment: compute 1% and store it in fee.

• printf("Fee = %.2f DZD\n", fee); – print fee; %.2f = “a float with 2 decimals”, \n = newline.

• return 0; – tell the operating system “finished successfully”. } closes main (the End).

Time & memory: this program runs in constant time O(1) (a fixed number of steps, whatever the amount) and uses

two float boxes – trivial memory. Possible errors: missing & in scanf; using %d (int) for a float; forgetting

#include.

2.6 Five Worked Examples (Algorithm + C)

Each example gives the algorithm, the full C program (with libraries and main), an organigramme (flowchart), and a

déroulement – a table showing every variable step by step, exactly as the computer runs it.

Example 1. Read an amount, print the 1% BaridiMob fee.

21
Algorithms & Data Structures By Benabderrezak Youcef

→ Algorithm: →C:

Read(amount) #include <stdio.h>

fee ← amount * 0.01 int main() {
Write(fee) float amount, fee;
scanf("%f", &amount);
fee = amount * 0.01;
printf("%.2f\n", fee);
return 0;
}

→ Organigramme:

Start

Read amount

fee ← amount × 0.01

Write fee

End

→ Déroulement (step-by-step run) for amount = 5000:

Step Instruction Value

1 amount read 5000
2 fee = 5000*0.01 50
3 print 50.00

Example 2. Read two amounts, print sum and average.

22
Algorithms & Data Structures By Benabderrezak Youcef

→ Algorithm: →C:

Read(firstAmount) #include <stdio.h>

Read(secondAmount) int main() {
sum ← firstAmount float a, b, sum;
+ secondAmount scanf("%f %f", &a, &b);
Write(sum, sum/2) sum = a + b;
printf("%.2f %.2f\n",
sum, sum/2);
return 0;
}

→ Organigramme:

Start

Read firstAmount,
secondAmount

sum ← firstAmount
+ secondAmount

Write sum, sum/2

End

→ Déroulement (step-by-step run) for firstAmount = 1000, secondAmount = 3000:

Step Instruction Value

1 read both 1000, 3000
2 sum = 1000+3000 4000
3 print sum, sum/2 4000, 2000

Example 3. Swap two balances using a temporary variable.

23
Algorithms & Data Structures By Benabderrezak Youcef

→ Algorithm: →C:

temp ← balanceA #include <stdio.h>

balanceA ← balanceB int main() {
balanceB ← temp int A = 200, B = 500;
int temp;
temp = A;
A = B;
B = temp;
printf("%d %d\n", A, B);
return 0;
}

→ Organigramme:

Start

temp ← balanceA

balanceA ← balanceB

balanceB ← temp

End

→ Déroulement (step-by-step run) for balanceA = 200, balanceB = 500:

Step temp balanceA balanceB

start - 200 500
temp=balanceA 200 200 500
balanceA=balanceB 200 500 500
balanceB=temp 200 500 200

24
Algorithms & Data Structures By Benabderrezak Youcef

▶ In plain words: Why the temp box? Think about it. What if we just wrote balanceA ← balanceB then

balanceB ← balanceA? The first line overwrites A with 500 – the old 200 is gone forever – so the second line

copies 500 back and both end up 500. It is like pouring tea into a full glass of coffee: to swap two full glasses you

need a third empty glass. temp is that third glass, holding A’s old value while B moves in.

Example 4. Convert an amount in DZD to centimes (integer).

→ Algorithm: →C:

Read(dinars) #include <stdio.h>

centimes ← dinars * 100 int main() {
Write(centimes) float dinars;
long centimes;
scanf("%f", &dinars);
centimes = (long)(dinars*100);
printf("%ld\n", centimes);
return 0;
}

→ Organigramme:

Start

Read dinars

centimes ← dinars × 100

Write centimes

End

25
Algorithms & Data Structures By Benabderrezak Youcef

→ Déroulement (step-by-step run) for dinars = 150.50:

Step Instruction Value

1 read dinars 150.50
2 150.50*100 15050.0
3 cast to long 15050

Example 5. Last digit of an account number.

→ Algorithm: →C:

Read(number) #include <stdio.h>

lastDigit ← number mod 10 int main() {
Write(lastDigit) int number, lastDigit;
scanf("%d", &number);
lastDigit = number % 10;
printf("%d\n", lastDigit);
return 0;
}

→ Organigramme:

Start

Read number

lastDigit ← number mod 10

Write lastDigit

End

26
Algorithms & Data Structures By Benabderrezak Youcef

→ Déroulement (step-by-step run) for number = 12345:

Step Instruction Value

1 read number 12345
2 12345 % 10 5
3 print lastDigit 5

▶ In plain words: What is mod (% in C)? It is the remainder of a division. 12345 ÷ 10 = 1234 remainder 5 – and

that remainder is the last digit. This trick generalises: n mod 10 always gives the last digit, and n div 10 chops

it off (used in the “count digits” loop later). Why it works: our numbers are base 10, so dividing by 10 separates

the last digit from the rest.

27
Algorithms & Data Structures By Benabderrezak Youcef

3 Conditional Structures

3.1 Why Make Decisions?

Intuition first. Every sequential program in Chapter 2 ran straight through: line 1, line 2, line 3, always the same path.

But real life is full of “if. . . then. . . ”. If it rains, take an umbrella. If the balance is enough, do the transfer; otherwise,

refuse. A program that cannot ask a question can only ever do one fixed thing. Conditions give a program the power

to choose a different path depending on the data.

Why does this concept exist? What problem does it solve? A straight-line algorithm treats every input the same,

which is often wrong and sometimes dangerous – imagine BaridiMob transferring money it does not have. Conditions

solve this by letting the program inspect the data and react: check first, act accordingly. This is the birth of intelligent

behaviour.

Real-life analogy. A condition is a fork in the road with a signpost. You read the sign (the test), and it sends you

left or right. You cannot walk both roads – you take exactly one, based on the answer.

Programs must choose. Jumia checks if stock > 0 before selling. Baridi Mob checks if balance is enough before

a transfer. This is done with conditions.

The building block: a Boolean test. A condition is any expression that is either True or False. It is built with

comparison operators:

Pseudocode C Meaning Example (True)

= == equal to stock == 0
̸= != not equal state != 1
< > < > less / greater age > 18
≤ ≥ <= >= at most / at least bal >= amt

28
Algorithms & Data Structures By Benabderrezak Youcef

Several tests can be joined with And (&&), Or (||), Not (!): e.g. age >= 18 And hasID.

The #1 condition bug: writing = (assignment) where you mean == (comparison) in C. if (x = 5) stores 5 into

x and is always true; if (x == 5) asks whether x is 5. One = versus two is the difference between a command

and a question.

3.2 Simple and Double Condition

Two shapes of decision. Sometimes you act only if something is true and do nothing otherwise (simple). Sometimes

you must pick one of two actions (double: this or that). Choose the shape that matches your problem.

Simple: If (condition) Then ...EndIf

Double: If (condition) Then ...Else ...EndIf

Reading it: the condition is tested once. Simple – if True, run the Then block; if False, skip it and continue.

Double – if True, run Then; if False, run Else. Exactly one of the two blocks runs, never both, never neither. EndIf

marks where the choice rejoins the main path.

Baridi Mob transfer – double condition:

If (balance >= amount) Then
balance ← balance - amount
Write("Transfer done")
Else
Write("Not enough money")
EndIf

Flowchart:

29
Algorithms & Data Structures By Benabderrezak Youcef

Start

Yes balance ≥ No
amount?

balance ← Write "Not

balance − amount enough"

End

Following the path: the diamond asks balance ≥ amount?. On Yes the flow goes left – subtract the amount

and confirm. On No it goes right – refuse. The two branches meet again at End: whichever road you took, the

program continues as one afterwards. Why the test comes first: it guards the money – we never subtract before

checking there is enough. Remove the guard and the balance could go negative.

3.3 Nested and Multiple Choice

Why go beyond two branches? A double If chooses between two outcomes. But some questions have three or more

answers: a demand level is high, medium, or low; an exam grade is A, B, C, D, or F. To handle these we nest decisions

– put an If inside the Else of another, forming an “Else If ladder” that tries each case in turn until one matches.

Analogy. It is a series of sieves stacked on top of each other: the data falls through the first test; if it does not

match, it drops to the next test, and so on, until it lands in exactly one bucket. The final Else is the catch-all bucket at

the bottom for “none of the above”.

30
Algorithms & Data Structures By Benabderrezak Youcef

Yassir surge pricing – nested / multiple choice:

If (demand = "high") Then
factor ← 1.5
Else If (demand = "medium") Then
factor ← 1.2
Else
factor ← 1.0
EndIf

How it runs: test demand = "high" first; if True, set factor to 1.5 and skip the rest. Only if it is False do we

try "medium", and only if that is False do we fall to the final Else (1.0). At most one branch runs – the first that

matches.

When the choices are a fixed list of values of one variable, C offers a cleaner form, switch:
switch (level) {
case 3: factor = 1.5; break; // high
case 2: factor = 1.2; break; // medium
default: factor = 1.0; // normal
}

Line by line: switch(level) jumps to the case matching level’s value. case 3: runs when level==3.

break; exits the switch. default: is the catch-all (the final Else).

Common beginner mistakes with decisions: (1) forgetting break; – without it, control “falls through” into

the next case and runs it too. (2) Using = instead of == in the test. (3) Writing overlapping conditions in the

wrong order, so a later case can never be reached. (4) Forgetting the final Else/default, leaving “none of

the above” unhandled.

3.4 Five Worked Examples (Algorithm + C)

Example 1. Print “OK” if balance is enough, else “Refused”.

31
Algorithms & Data Structures By Benabderrezak Youcef

→ Algorithm: →C:

If balance ≥ amount Then #include <stdio.h>

Write("OK") int main() {
Else float balance, amount;
Write("Refused") scanf("%f %f",
EndIf &balance, &amount);
if (balance >= amount)
printf("OK\n");
else
printf("Refused\n");
return 0;
}

→ Organigramme:

Start

Read balance, amount

Yes balance ≥ No
amount?

Write "OK" Write "Refused"

End

→ Déroulement (step-by-step run) for balance = 5000, amount = 8000:

Step Test Result

1 5000 >= 8000 false
2 take else "Refused"

Example 2. Biggest of two amounts.

32
Algorithms & Data Structures By Benabderrezak Youcef

→ Algorithm: →C:

If amountA > amountB Then #include <stdio.h>

Write(amountA) int main() {
Else int amountA, amountB;
Write(amountB) scanf("%d %d",
EndIf &amountA, &amountB);
if (amountA > amountB)
printf("%d\n", amountA);
else
printf("%d\n", amountB);
return 0;
}

→ Organigramme:

Start

Read amountA,
amountB

Yes amountA > No

amountB?

Write amountA Write amountB

End

→ Déroulement (step-by-step run) for amountA = 200, amountB = 500:

Step Test Result

1 200 > 500 false
2 take else 500

Example 3. Is an amount even or odd?

33
Algorithms & Data Structures By Benabderrezak Youcef

→ Algorithm: →C:

If (number mod 2 = 0) Then #include <stdio.h>

Write("even") int main() {
Else int number;
Write("odd") scanf("%d", &number);
EndIf if (number % 2 == 0)
printf("even\n");
else
printf("odd\n");
return 0;
}

→ Organigramme:

Start

Read number

Yes number No
mod 2 = 0?

Write "even" Write "odd"

End

→ Déroulement (step-by-step run) for number = 7:

Step Test Result

1 7 % 2 1
2 1 == 0 false "odd"

Example 4. Account state code 1/2/3 to a word (multiple choice).

34
Algorithms & Data Structures By Benabderrezak Youcef

→ Algorithm: →C:

If state = 1 Then #include <stdio.h>

Write("Active") int main() {
Else If state = 2 Then int state;
Write("Blocked") scanf("%d", &state);
Else switch (state) {
Write("Closed") case 1:
EndIf printf("Active\n"); break;
case 2:
printf("Blocked\n"); break;
default:
printf("Closed\n");
}
return 0;
}

→ Organigramme:

Start

Read state

Y
state = 1? Write "Active"

Y
state = 2? Write "Blocked"

Write "Closed"

End

→ Déroulement (step-by-step run) for state = 2:

Step Test Result

1 state == 1 false
2 state == 2 true → "Blocked"

35
Algorithms & Data Structures By Benabderrezak Youcef

Example 5. Fee with a minimum of 20 DZD.

→ Algorithm: →C:

fee ← amount * 0.01 #include <stdio.h>

If fee < 20 Then int main() {
fee ← 20 float amount, fee;
EndIf scanf("%f", &amount);
fee = amount * 0.01;
if (fee < 20)
fee = 20;
printf("%.2f\n", fee);
return 0;
}

→ Organigramme:

Start

Read amount

fee ← amount
× 0.01

Yes
fee < 20? fee ← 20

No

Write fee

End

→ Déroulement (step-by-step run) for amount = 1000:

Step Instruction fee

1 1000*0.01 10
2 10 < 20 true 20

36
Algorithms & Data Structures By Benabderrezak Youcef

▶ In plain words: Why a simple If (no Else) here? We only act in one case – when the fee is too small we raise

it to 20; when it is already ≥ 20 we do nothing and keep it. This “if too low, pull it up” pattern is called clamping,

and it needs no Else because “leave it alone” is not an action. Think about it: what if amount were 5000? Then

fee = 50, the test 50 < 20 is false, the Then is skipped, and 50 is printed unchanged.

37
Algorithms & Data Structures By Benabderrezak Youcef

4 Repetitive Structures (Loops)

4.1 Why Loops?

A loop repeats the same steps many times. Jumia adds the price of 50 items in a basket; Sonatrach reads 1000 sensor

values. Writing the line 1000 times is impossible – so we write it once and tell the computer how many times to repeat.

▶ In plain words: Think of climbing stairs. You do the same action – “lift foot, step up” – again and again. You

need three things: where you start (step 1), when you stop (top step), and the step up that moves you forward. A

loop is exactly this.

4.2 The Four Parts of Every Loop

Any loop is built from 4 parts. Miss one and it breaks:

1. Start – give the counter a first value: i ← 1

2. Test – the condition to keep going: i ≤ 10? (when false ⇒ stop)

3. Body – the work you repeat (read, add, print. . . )

4. Update – move the counter forward: i ← i+1

Forget the update and the test never becomes false ⇒ infinite loop (program hangs).

See the 4 parts in a For loop counting 1 to 3:

For ← 1 |{z}
| {z i} |{z} to 3 Do Write(i)
| {z } EndFor (i ← i+1)
| {z }
start test i≤3 body update, automatic

A For loop hides the start/test/update in one line. A While loop writes them by hand.

38
Algorithms & Data Structures By Benabderrezak Youcef

4.3 The Three Loops – Which One to Use?

Loop Test is Runs Use when. . .

For . . . EndFor counter (auto) known count you know how many times (“do 10 times”)
While . . . EndWhile before body 0 or more times you don’t know the count (“until user types 0”)
Repeat . . . Until after body at least 1 time you must run once first (“ask, then check”)

▶ In plain words: The difference between While and Repeat is where you check. While checks first – if the test

is already false, the body runs zero times (like checking your wallet before shopping: empty ⇒ you don’t shop).

Repeat checks last – the body always runs once before the first test (like tasting soup, then deciding if it needs

more salt).

Same job (count 1 to 3), all three loops:

For While Repeat

For i←1 to 3 Do i ← 1 i ← 1
Write(i) While i ≤ 3 Do Repeat
EndFor Write(i) Write(i)
i ← i+1 i ← i+1
EndWhile Until i > 3

All three print 1 2 3. The For is shortest – prefer it when the count is known.

Trace of the While version (follow the 4 parts round by round):

Round i (start/update) i ≤ 3? (test) Body: prints

1 1 true 1
2 2 true 2
3 3 true 3
4 4 false ⇒ stop – (loop ends)

Notice round 4: the test is false, so the body does not run and the loop ends. This is how a loop knows when to stop.

4.4 Example: Sum of Transfers (For loop)

39
Algorithms & Data Structures By Benabderrezak Youcef

BaridiMob – total of n transfers this month:

total ← 0
For i ← 1 to n Do
Read(transfer) // one amount each round
total ← total + transfer
EndFor
Write("Monthly total = ", total)

Flowchart of a While loop:

Start

i ← 1; total ← 0

Read transfer
Yes
i ≤ n? total ← total + transfer
i←i+1

No

Write total

End

4.5 Nested Loops

BaridiMob – print every (user, day) pair (3 users × 3 days, loop inside a loop). We only use the two counters i

and j – no arrays yet:

40
Algorithms & Data Structures By Benabderrezak Youcef

For i ← 1 to 3 Do // i = user number

For j ← 1 to 3 Do // j = day number
Write("user ", i, " day ", j)
EndFor
EndFor

The inner loop runs fully for each step of the outer loop ⇒ 3 × 3 = 9 prints.

4.6 Five Worked Examples (Algorithm + C)

Example 1. Sum of count transfers typed by the user.

→ Algorithm: →C:

total ← 0 #include <stdio.h>

For i ← 1 to count Do int main() {
Read(transfer) int count,i,transfer,total=0;
total ← total + transfer scanf("%d", &count);
EndFor for(i=1; i<=count; i++){
scanf("%d", &transfer);
total += transfer;
}
printf("%d\n", total);
return 0;
}

→ Organigramme:

41
Algorithms & Data Structures By Benabderrezak Youcef

Start

total ← 0; i ← 1

Read transfer
Yes
i ≤ count? total ← total+transfer
i ← i+1
No

Write total

End

→ Déroulement (step-by-step run) for transfers 10, 20, 30 (count = 3):

i transfer total
1 10 10
2 20 30
3 30 60

Example 2. Factorial number! with a loop.

→ Algorithm: →C:

result ← 1 #include <stdio.h>

For i ← 2 to number Do int main() {
result ← result * i int number, i;
EndFor long result = 1;
scanf("%d", &number);
for(i=2; i<=number; i++)
result = result * i;
printf("%ld\n", result);
return 0;
}

→ Organigramme:

42
Algorithms & Data Structures By Benabderrezak Youcef

Start

result ← 1; i ← 2

i≤ Yes result ← result×i

number? i ← i+1

No

Write result

End

→ Déroulement (step-by-step run) for number = 4:

i result×i result
- - 1
2 1×2 2
3 2×3 6
4 6×4 24

Example 3. Power baseexponent without the pow function.

→ Algorithm: →C:

result ← 1 #include <stdio.h>

For i ← 1 to exponent Do int main() {
result ← result * base int base, exponent, i;
EndFor long result = 1;
scanf("%d %d", &base, &exponent);
for(i=1; i<=exponent; i++)
result = result * base;
printf("%ld\n", result);
return 0;
}

→ Organigramme:

43
Algorithms & Data Structures By Benabderrezak Youcef

Start

result ← 1; i ← 1

i≤ Yes result ← result×base

exponent? i ← i+1

No

Write result

End

→ Déroulement (step-by-step run) for base = 2, exponent = 3:

i result×base result
- - 1
1 1×2 2
2 2×2 4
3 4×2 8

Example 4. Read transfers until 0 (sentinel), sum them.

→ Algorithm: →C:

total ← 0 #include <stdio.h>

Read(transfer) int main() {
While transfer ̸= 0 Do int transfer, total = 0;
total ← total + transfer scanf("%d", &transfer);
Read(transfer) while (transfer != 0) {
EndWhile total += transfer;
scanf("%d", &transfer);
}
printf("%d\n", total);
return 0;
}

→ Organigramme:

44
Algorithms & Data Structures By Benabderrezak Youcef

Start

total ← 0;
Read transfer

transfer Yes total ← total+transfer

̸= 0? Read transfer

No

Write total

End

→ Déroulement (step-by-step run) for input 100, 200, 0:

transfer test ̸=0 total

100 true 100
200 true 300
0 false (stop) 300

Example 5. Count the digits of a number (Repeat).

→ Algorithm: →C:

digits ← 0 #include <stdio.h>

Repeat int main() {
number ← number div 10 int number, digits = 0;
digits ← digits + 1 scanf("%d", &number);
Until number = 0 do {
number = number / 10;
digits = digits + 1;
} while (number != 0);
printf("%d\n", digits);
return 0;
}

→ Organigramme:

45
Algorithms & Data Structures By Benabderrezak Youcef

Start

Read number;
digits ← 0

number ← number
No
div 10; digits
← digits+1

number Yes
Write digits
= 0?

End

→ Déroulement (step-by-step run) for number = 12345:

step number digits

start 12345 0
1 1234 1
2 123 2
3 12 3
4 1 4
5 0 5

46
Algorithms & Data Structures By Benabderrezak Youcef

5 Arrays and Strings

5.1 One-Dimensional Array (1D)

The problem that arrays solve. Suppose you must store the 30 daily transfers of a month. With what you know so

far you would declare t1, t2, t3, ..., t30 – thirty separate variables. To add them you would write thirty lines.

For 1000 values this is hopeless, and worse: you cannot use a loop, because a loop’s counter i cannot reach a variable

named t_i. We are stuck. The array is the escape: one name for many values, reached by a number that a loop can

compute.

Intuition & analogy. An array is a row of numbered lockers sharing one wall-label. The label (transfer) names

the whole row; the locker number (the index) picks one box. Because the box is chosen by a number, a loop can walk

locker 0, 1, 2, . . . and touch every value with a single line of code. That is the whole point.

An array stores many values of the same type under one name. Each value has an index (position). In C, indices

start at 0.

Every keyword: same type – all boxes hold the same kind (all int, or all float); you cannot mix. one name –

the array’s name (transfer). index – the position number in [ ]; transfer[2] means “the value in box 2”. starts

at 0 – the first box is [0], so an array of size 5 has valid indices [0]. . . [4] – there is no [5].

▶ In plain words: An array is like a row of numbered lockers. One name (transfer), many boxes. To open

box number 2 you write transfer[2]. Careful: the first locker is number 0, not 1.

Why start counting at 0? The index is really a distance from the start: box 0 is “0 steps from the beginning”,

box 3 is “3 steps along”. The computer stores the array as one continuous block in memory and finds box i by “start

address + i × box-size”. Box 0 sits exactly at the start, so its distance is 0. This is why almost every language counts

array positions from 0.

47
Algorithms & Data Structures By Benabderrezak Youcef

How it looks in memory (the array below is one contiguous block; the [i] are positions, not stored values):

+------+------+------+------+------+

transfer| 450 | 999 | 1200 | 300 | 875 |

+------+------+------+------+------+

index [0] [1] [2] [3] [4]

In C you declare and use it like this:

Action C
declare 5 ints int transfer[5];
declare + fill int transfer[5] = {450,999,1200,300,875};
read box 2 x = transfer[2]; // gives 1200
write box 0 transfer[0] = 500;

transfer: 450 999 1200 300 875

[0] [1] [2] [3] [4]

Advantages: one name for thousands of values; instant access to any box by its index (“random access”, O(1));

and – the big one – you can loop over all elements. Limitations: the size is fixed when you declare it (a [5] array can

never hold 6); all elements must share one type; and C does not check whether your index is valid.

Common beginner mistakes with arrays: (1) off-by-one – looping 1 to n instead of 0 to n-1, missing the

first box or running past the last. (2) index out of bounds – writing transfer[5] in a size-5 array; C will not stop

you, it silently corrupts nearby memory (a dangerous bug). (3) Forgetting that box [0] exists. Always remember:

valid indices are 0 to size-1.

BaridiMob – find the biggest transfer of the month:

48
Algorithms & Data Structures By Benabderrezak Youcef

max ← transfer[0]
For i ← 1 to n-1 Do
If (transfer[i] > max) Then
max ← transfer[i]
EndIf
EndFor
Write("Biggest transfer = ", max)

The idea (before the code): to find the biggest value you cannot see all boxes at once, so you keep a “champion

so far” and challenge it against each new box. Line by line:

• max ← transfer[0] – start by assuming the first box is the biggest. Why box 0 and not 0? Because a real

transfer might be smaller than 0-as-a-guess would allow negative comparisons to misbehave; starting from

an actual element is always safe.

• For i ← 1 to n-1 – visit every other box (we already used box 0). n is the number of elements, so the

last index is n-1.

• If transfer[i] > max Then max ← transfer[i] – if this box beats the champion, it becomes the

new champion.

• After the loop, max holds the biggest value. Remove the If and max would just end up as the last element,

not the biggest.

5.2 Two-Dimensional Array (2D / Matrix)

A 2D array is a table with rows and columns: sales[i][j]. Good for grids: months × wilayas, students ×

subjects.

col 0

row 0 1 2 3

4 5 6

7 8 9

49
Algorithms & Data Structures By Benabderrezak Youcef

5.3 Strings (Character Arrays)

A string is a 1D array of characters ending with the special marker ’\0’ (null). Example: "Yassir" = Y a s s

i r \0.

BaridiMob – length of the account holder’s name (count until ’\0’):

len ← 0
While (name[len] ̸= ’\0’) Do
len ← len + 1
EndWhile

5.4 Five Worked Examples (Algorithm + C)

Example 1. Biggest transfer in an array of 5 transfers.

→ Algorithm:
biggest ← transfers[0] // assume first is biggest
For i ← 1 to 4 Do // check the rest
If transfers[i] > biggest Then
biggest ← transfers[i]
EndIf
EndFor

→C:
#include <stdio.h>
int main() {
int transfers[5], i, biggest; // array of 5 amounts
for (i = 0; i < 5; i++) // read the 5 values
scanf("%d", &transfers[i]);
biggest = transfers[0]; // start with first
for (i = 1; i < 5; i++) // scan the others
if (transfers[i] > biggest)// bigger?
biggest = transfers[i];// remember it
printf("%d\n", biggest); // print the biggest
return 0;
}

→ Organigramme:

50
Algorithms & Data Structures By Benabderrezak Youcef

Start

biggest ←
biggest ←
transfers[i]
transfers[0]; i ← 1
Y

Yes transfers[i]
i < 5?
> biggest?

No

Write biggest

End

→ Déroulement (step-by-step run) for transfers = [30, 90, 50, 20, 40]:

i transfers[i] biggest
- - 30
1 90 90
2..4 50,20,40 90

Example 2. Count transfers above 10 000 DZD.

→ Algorithm:
count ← 0 // counter of big ones
For i ← 0 to 4 Do // every transfer
If transfers[i] > 10000 Then
count ← count + 1
EndIf
EndFor

→C:
#include <stdio.h>
int main() {
int transfers[5], i, count = 0; // count starts 0
for (i = 0; i < 5; i++) // read 5 values
scanf("%d", &transfers[i]);

51
Algorithms & Data Structures By Benabderrezak Youcef

for (i = 0; i < 5; i++) // check each

if (transfers[i] > 10000) // above threshold?
count++; // count it
printf("%d\n", count); // print how many
return 0;
}

→ Organigramme:

Start

count ← count ←
0; i ← 0 count+1
Y

Yes transfers[i]
i < 5?
> 10000?

No

Write count

End

→ Déroulement (step-by-step run) for transfers = [5000, 12000, 30000, 800, 9000]:

i >10000? count
0 no 0
1,2 yes,yes 2
3,4 no,no 2

Example 3. Length of a name string (without strlen).

→ Algorithm:

52
Algorithms & Data Structures By Benabderrezak Youcef

length ← 0 // count of characters

While name[length] ̸= ’\0’ Do // until the end marker
length ← length + 1 // one more character
EndWhile

→C:
#include <stdio.h>
int main() {
char name[30]; // a string (char array)
int length = 0; // character counter
scanf("%s", name); // read a word
while (name[length] != ’\0’) // ’\0’ ends a string
length++; // move to next char
printf("%d\n", length); // print the length
return 0;
}

→ Organigramme:

Start

Read name;
length ← 0

name[length] Yes length ←

̸= ’\0’? length+1

No

Write length

End

53
Algorithms & Data Structures By Benabderrezak Youcef

→ Déroulement (step-by-step run) for name = "Ali":

length name[length] continue?

0 ’A’ yes
1 ’l’ yes
2 ’i’ yes
3 ’\0’ stop, length=3

Example 4. Copy a name into another string (without strcpy).

→ Algorithm:
i ← 0
While source[i] ̸= ’\0’ Do // until source ends
copy[i] ← source[i] // copy one character
i ← i + 1
EndWhile
copy[i] ← ’\0’ // add the end marker

→C:
#include <stdio.h>
int main() {
char source[30], copy[30]; // two strings
int i = 0; // index
scanf("%s", source); // read a word
while (source[i] != ’\0’) { // until end
copy[i] = source[i]; // copy character i
i++; // advance
}
copy[i] = ’\0’; // terminate the copy
printf("%s\n", copy); // print the copy
return 0;
}

→ Organigramme:

54
Algorithms & Data Structures By Benabderrezak Youcef

Start

Read source;
i←0

copy[i] ←
source[i] Yes
source[i];
̸= ’\0’?
i ← i+1

No

copy[i] ← ’\0’

End

→ Déroulement (step-by-step run) for source = "Hi":

i source[i] copy
0 ’H’ H
1 ’i’ Hi
2 ’\0’ "Hi"

Example 5. Sum of one row of a 3 × 3 transfers grid.

→ Algorithm:
rowTotal ← 0 // total for the row
For col ← 0 to 2 Do // the 3 columns
rowTotal ← rowTotal + grid[row][col]
EndFor

→C:
#include <stdio.h>
int main() {
int grid[3][3], row, col, rowTotal = 0; // 3x3 table
for (row = 0; row < 3; row++) // read all 9 cells
for (col = 0; col < 3; col++)

55
Algorithms & Data Structures By Benabderrezak Youcef

scanf("%d", &grid[row][col]);
row = 1; // choose row 1
for (col = 0; col < 3; col++) // add its 3 cells
rowTotal += grid[row][col];
printf("%d\n", rowTotal); // print the row total
return 0;
}

→ Organigramme:

Start

rowTotal ←
0; col ← 0

rowTotal ←
Yes rowTotal +
col < 3?
grid[row][col];
col ← col+1
No

Write rowTotal

End

→ Déroulement (step-by-step run) for row 1 = [100, 200, 300]:

col grid[1][col] rowTotal

0 100 100
1 200 300
2 300 600

56
Algorithms & Data Structures By Benabderrezak Youcef

6 Custom Types

6.1 Structure (Record)

A structure groups several fields of different types into one object. Perfect to describe a real thing (a client, a

product).

A BaridiMob account:
struct Account {
char name[30];
char rip[20]; // account number
float balance; // DZD
char phone[10]; // "0555..."
};
struct Account a1;
[Link] = 15000;

6.2 Enumerations and typedef

enum State { ACTIVE, BLOCKED, CLOSED }; // named values 0,1,2

typedef struct Account Account; // shorter name
enum State s = ACTIVE;

6.3 Five Worked Examples (Algorithm + C)

Here each example uses only one or two account variables (no arrays of structures – that comes later once arrays and

structures are both mastered).

Example 1. Declare an account, set its balance, print it.

→ Algorithm:

57
Algorithms & Data Structures By Benabderrezak Youcef

[Link] ← 15000 // set the balance field

Write([Link]) // show it

→C:
#include <stdio.h>
struct Account { // a record type
char name[30]; // holder name
float balance; // money in DZD
};
int main() {
struct Account account; // one account variable
[Link] = 15000; // dot accesses a field
printf("%.2f\n", [Link]); // print balance
return 0;
}

→ Organigramme:

Start

[Link]
← 15000

Write
[Link]

End

→ Déroulement (step-by-step run) after the assignment:

field value
[Link] 15000.00

Example 2. Transfer 2000 DZD from sender to receiver.

→ Algorithm:

58
Algorithms & Data Structures By Benabderrezak Youcef

[Link] ← [Link] - 2000 // debit

[Link] ← [Link] + 2000 // credit

→C:
#include <stdio.h>
struct Account { float balance; }; // simple record
int main() {
struct Account sender, receiver; // two accounts
[Link] = 15000; // set balances
[Link] = 1000;
[Link] = [Link] - 2000; // debit
[Link] = [Link] + 2000; // credit
printf("%.2f %.2f\n", [Link], [Link]);
return 0;
}

→ Organigramme:

Start

[Link] ←
[Link] − 2000

[Link] ←
[Link] + 2000

Write both balances

End

→ Déroulement (step-by-step run) for sender = 15000, receiver = 1000:

step sender receiver

start 15000 1000
debit 13000 1000
credit 13000 3000

59
Algorithms & Data Structures By Benabderrezak Youcef

Example 3. Allow a transfer only if the account is ACTIVE (enum).

→ Algorithm:
If [Link] = ACTIVE Then // is it active?
Write("allowed")
Else
Write("denied") // blocked or closed
EndIf

→C:
#include <stdio.h>
enum State { ACTIVE, BLOCKED, CLOSED }; // 0, 1, 2
struct Account { enum State state; }; // record
int main() {
struct Account account; // one account
[Link] = BLOCKED; // set the state
if ([Link] == ACTIVE) // active?
printf("allowed\n"); // yes
else
printf("denied\n"); // no
return 0;
}

→ Organigramme:

60
Algorithms & Data Structures By Benabderrezak Youcef

Start

[Link]
← BLOCKED

Yes state = No
ACTIVE?

Write "allowed" Write "denied"

End

→ Déroulement (step-by-step run) for [Link] = BLOCKED:

step test result

1 state == ACTIVE false
2 take else "denied"

Example 4. Compute the 1% fee and store it in the account.

→ Algorithm:
[Link] ← [Link] * 0.01 // 1% of balance
Write([Link])

→C:
#include <stdio.h>
struct Account { float balance; float fee; }; // record
int main() {
struct Account account; // one account
[Link] = 5000; // set balance
[Link] = [Link] * 0.01; // 1% fee

61
Algorithms & Data Structures By Benabderrezak Youcef

printf("%.2f\n", [Link]); // print the fee

return 0;
}

→ Organigramme:

Start

[Link] ←
[Link] × 0.01

Write [Link]

End

→ Déroulement (step-by-step run) for [Link] = 5000:

step balance fee

1 5000 -
2 5000 50.00

Example 5. Compare two accounts, print the richer holder.

→ Algorithm:
If [Link] > [Link] Then
Write([Link]) // first is richer
Else
Write([Link]) // second is richer
EndIf

→C:
#include <stdio.h>
struct Account { char name[30]; float balance; };
int main() {
struct Account first, second; // two accounts
[Link] = 8000; // set balances

62
Algorithms & Data Structures By Benabderrezak Youcef

[Link] = 3000;
if ([Link] > [Link]) // first richer?
printf("first is richer\n");
else
printf("second is richer\n");
return 0;
}

→ Organigramme:

Start

fi[Link] ← 8000
[Link] ← 3000

Yes fi[Link] > No

[Link]?

Write first Write second

End

→ Déroulement (step-by-step run) for first = 8000, second = 3000:

step test result

1 8000 > 3000 true
2 take then first

ASD 1 summary: sequence → conditions → loops → arrays → custom types. These are the building blocks of

every program. In ASD 2 we make them reusable (functions) and dynamic (pointers, lists).

63
Algorithms & Data Structures By Benabderrezak Youcef

7 ASD 1 – Solved Exercises

All examples use BaridiMob (mobile payment). Read the statement, try alone, then check.

Exercise 1. Read a transfer amount; print the fee (1%) and total (amount+fee). Solution: → Algorithm:
Read(amount) ; fee ← amount*0.01
total ← amount+fee ; Write(fee, total)

→C:
float amount,fee; scanf("%f",&amount);
fee=amount*0.01; printf("%.2f %.2f\n",fee,amount+fee);

Exercise 2. Print “OK” if balance is enough, else “Refused”. Solution: → Algorithm:

If balance ≥ amount Then Write("OK") Else Write("Refused") EndIf

→C:
if(balance>=amount) printf("OK\n"); else printf("Refused\n");

Exercise 3. State code (1=active, 2=blocked, 3=closed) to a word. Solution: → Algorithm:

If s=1 Then Write("Active")
Else If s=2 Then Write("Blocked")
Else Write("Closed") EndIf

→C:
switch(s){case 1:printf("Active\n");break;
case 2:printf("Blocked\n");break;
default:printf("Closed\n");}

Exercise 4. Sum of n transfers with a For loop. Solution: → Algorithm:

64
Algorithms & Data Structures By Benabderrezak Youcef

total ← 0
For i ← 1 to n Do Read(t[i]); total ← total+t[i] EndFor

→C:
int total=0;
for(int i=0;i<n;i++){ scanf("%d",&t[i]); total+=t[i]; }

Exercise 5. Read transfers until 0 (sentinel); sum them (While). Solution: → Algorithm:
total ← 0 ; Read(x)
̸ 0 Do total ← total+x ; Read(x) EndWhile
While x =

→C:
int total=0,x; scanf("%d",&x);
while(x!=0){ total+=x; scanf("%d",&x); }

Exercise 6. Biggest transfer in an array of n. Solution: → Algorithm:

max ← t[0]
For i ← 1 to n-1 Do If t[i]>max Then max ← t[i] EndIf EndFor

→C:
int max=t[0];
for(int i=1;i<n;i++) if(t[i]>max) max=t[i];

Exercise 7. Count transfers above 10 000 DZD. Solution: → Algorithm:

c ← 0
For i ← 0 to n-1 Do If t[i]>10000 Then c ← c+1 EndIf EndFor

→C:
int c=0; for(int i=0;i<n;i++) if(t[i]>10000) c++;

Exercise 8. 2 × 3 table tr[i][j]: print total per row (per user). Solution: → Algorithm:

65
Algorithms & Data Structures By Benabderrezak Youcef

For i ← 0 to 1 Do
s ← 0
For j ← 0 to 2 Do s ← s+tr[i][j] EndFor
Write("User ",i," = ",s)
EndFor

→C:
for(int i=0;i<2;i++){ int s=0;
for(int j=0;j<3;j++) s+=tr[i][j];
printf("User %d = %d\n",i,s); }

Exercise 9. Check a 4-digit PIN vs stored; 3 tries. Solution: → Algorithm:

tries ← 0 ; ok ← False
While tries<3 AND NOT ok Do
Read(pin)
If pin=stored Then ok ← True Else tries ← tries+1 EndIf
EndWhile

→C:
int tries=0,ok=0,pin;
while(tries<3 && !ok){ scanf("%d",&pin);
if(pin==stored) ok=1; else tries++; }

Exercise 10. struct Account: transfer 2000 DZD from a1 to a2. Solution: → Algorithm:
[Link] ← [Link]-2000
[Link] ← [Link]+2000

→C:
[Link]-=2000; [Link]+=2000;

ASD 1 – Homework (statements only)

HW1. Read two transfer amounts and print their average.

HW2. Read an amount; print the 1% fee, but the fee is at least 20 DZD (minimum fee).

66
Algorithms & Data Structures By Benabderrezak Youcef

HW3. Read a balance; print “Rich” if > 1 000 000, “Normal” if > 10 000, else “Low”.

HW4. Read 10 balances and print how many are zero.

HW5. Read n transfers and print the smallest one.

HW6. Read n transfers and print both the smallest and biggest in a single pass.

HW7. Print the multiplication table of 9 (a BaridiMob loyalty points table) using a For loop.

HW8. Read transfers until a negative number; print how many were entered.

HW9. Read a PIN and keep asking until it has exactly 4 digits.

HW10. Compute xn (fee growth) using a loop, without the power operator.

HW11. Read n transfers; print the sum of only the even amounts.

HW12. Print all numbers from 1 to 100 divisible by 7 (batch IDs).

HW13. Read a table 3 × 3 of transfers; print the grand total of all 9 cells.

HW14. Read a 3 × 3 table; print the total of each column (per day).

HW15. Read a 3 × 3 table; find the single biggest cell and its position (row, col).

HW16. Read a name (string) and print it reversed.

HW17. Count the vowels in an account holder’s name.

HW18. Check if a name string is a palindrome (same forwards and backwards).

HW19. Read two names and print “Same” if identical character by character.

67
Algorithms & Data Structures By Benabderrezak Youcef

HW20. Read an amount in DZD and print it in centimes (integer).

HW21. Read n transfers; print the percentage that are above the average.

HW22. Read a year; print if it is a leap year (nested conditions).

HW23. Read 5 monthly balances; print if the balance is always growing.

HW24. Read n transfers; count how many equal the maximum.

HW25. Simulate a fee counter: for amounts 1000, 2000, . . . , 10000, print each fee.

HW26. Read a digit 0–9 and print it as a word (“zero”, “one”, . . . ) with switch.

HW27. Define struct Account; read 3 accounts into an array and print the richest.

HW28. Using enum State, read a code and print whether transfers are allowed (only ACTIVE).

HW29. Read a table of n transfers; replace every amount above 50 000 by 50 000 (a cap).

HW30. Merge two ideas: read n transfers, and for each print “big” or “small” vs the average, then print how many big.

68
Algorithms & Data Structures By Benabderrezak Youcef

MODULE ASD 2
Subprograms, Recursion, Files, Linked Lists

69
Algorithms & Data Structures By Benabderrezak Youcef

8 Subprograms: Functions and Procedures

8.1 Why Subprograms?

A subprogram is a small named block of code you can call many times. It avoids repeating code and splits a big

problem into small pieces (modularity).

• Function = returns a value (e.g. compute a price).

• Procedure = does an action, returns nothing (e.g. print a receipt).

main program

rideCost() applySurge() printBill()

Yassir – a function that computes ride cost:

float rideCost(float distance, float rate) {
return distance * rate;
}
// call it:
float p = rideCost(10, 325); // p = 3250

8.2 Local vs Global Variables

Local variable: born inside a subprogram, dies when it ends. Only that subprogram sees it.

Global variable: declared outside, seen by everyone, lives the whole program.

Prefer local variables. Too many global variables make bugs: any function can change them, and you cannot tell

who.

70
Algorithms & Data Structures By Benabderrezak Youcef

8.3 Passing Parameters

By value: the function gets a copy. Changes stay inside.

By reference (address, & / pointer): the function gets the real variable. Changes are kept outside.

Swap two drivers’ positions – needs by reference:

void swap(int *a, int *b) { // pointers = by reference
int t = *a; *a = *b; *b = t;
}
swap(&x, &y); // real x and y are exchanged

8.4 Five Worked Examples (Algorithm + C)

Each C program has the libraries, the subprogram, and a main that calls it. The organigramme draws the subprogram

body.

Example 1. Function fee(amount) returning 1%.

→ Algorithm:
Function fee(amount): Real // takes an amount
Return amount * 0.01 // gives back the 1% fee

→C:
#include <stdio.h>
float fee(float amount) { // returns a float
return amount * 0.01; // send back the fee
}
int main() {
printf("%.2f\n", fee(5000));// call and print
return 0;
}

→ Organigramme (function fee):

71
Algorithms & Data Structures By Benabderrezak Youcef

Enter fee(amount)

result ←
amount × 0.01

Return result

→ Déroulement (step-by-step run) for the call fee(5000):

call amount returns

fee(5000) 5000 50.0

Example 2. Function maximum(a, b).

→ Algorithm:
Function maximum(a, b): Integer
If a > b Then Return a // a wins
Else Return b EndIf // b wins

→C:
#include <stdio.h>
int maximum(int a, int b) { // returns an int
if (a > b) return a; // a bigger -> give a
else return b; // else give b
}
int main() {
printf("%d\n", maximum(200, 500)); // call and print
return 0;
}

→ Organigramme (function maximum):

72
Algorithms & Data Structures By Benabderrezak Youcef

Enter maximum(a,b)

Yes No
a > b?

Return a Return b

→ Déroulement (step-by-step run) for maximum(200, 500):

call test returns

maximum(200,500) 200>500 false 500

Example 3. Procedure printBill (returns nothing).

→ Algorithm:
Procedure printBill(amount, fee) // no return value
Write("Total=", amount + fee)

→C:
#include <stdio.h>
void printBill(float amount, float fee) { // void = no return
printf("Total=%.2f\n", amount + fee); // print total
}
int main() {
printBill(5000, 50); // call the procedure
return 0;
}

→ Organigramme (procedure printBill):

73
Algorithms & Data Structures By Benabderrezak Youcef

Enter printBill

Write amount + fee

Return (nothing)

→ Déroulement (step-by-step run) for printBill(5000, 50):

amount fee output

5000 50 Total=5050.00

Example 4. swap by reference (needs pointers in C).

→ Algorithm:
Procedure swap(var a, var b) // var = real variable
temp ← a // keep old a
a ← b // a takes b
b ← temp // b takes old a

→C:
#include <stdio.h>
void swap(int *a, int *b) { // pointers = real vars
int temp = *a; // temp = value at a
*a = *b; // a gets b’s value
*b = temp; // b gets old a
}
int main() {
int x = 3, y = 8; // two variables
swap(&x, &y); // pass their addresses
printf("%d %d\n", x, y); // 8 3
return 0;
}

→ Organigramme (procedure swap):

74
Algorithms & Data Structures By Benabderrezak Youcef

Enter swap(a,b)

temp ← a

a←b

b ← temp

Return

→ Déroulement (step-by-step run) for x = 3, y = 8:

step temp x y
start - 3 8
temp=a 3 3 8
a=b 3 8 8
b=temp 3 8 3

Example 5. Function isEnough(balance, amount) boolean.

→ Algorithm:
Function isEnough(balance, amount): Boolean
Return (balance ≥ amount) // true or false

→C:
#include <stdio.h>
int isEnough(float balance, float amount) { // 1 or 0
return balance >= amount; // comparison is the answer
}
int main() {
printf("%d\n", isEnough(5000, 8000)); // prints 0
return 0;
}

75
Algorithms & Data Structures By Benabderrezak Youcef

→ Organigramme (function isEnough):

Enter isEnough

Yes balance ≥ No
amount?

Return true Return false

→ Déroulement (step-by-step run) for isEnough(5000, 8000):

call test returns

isEnough(5000,8000) 5000>=8000 0 (false)

8.5 Recursion

A recursive subprogram calls itself on a smaller version of the same problem. It must have two parts: a base case

– a simple case it can answer directly, which stops the calling; and a recursive case – where it calls itself with

smaller input and builds the answer from the result.

▶ In plain words: Recursion is like a set of Russian dolls: to open the big doll you open a slightly smaller one

inside, and again, until the tiniest doll (the base case) has nothing inside. Or like standing in a queue and asking

“how many people are in front of me?” – you ask the person ahead, who asks the person ahead of them, until the

first person answers “0”; then each answer comes back adding one. Warning: forget the base case and the function

calls itself forever and crashes (stack overflow).

Factorial n! = n × (n − 1)!:

76
Algorithms & Data Structures By Benabderrezak Youcef

int fact(int n) {
if (n <= 1) return 1; // base case
return n * fact(n - 1); // recursive case
}

How fact(3) unfolds:

fact(3)

returns 6 calls

3×fact(2)

returns 2 calls

2×fact(1)

returns 1 calls

fact(1) returns 1

Forget the base case ⇒ infinite recursion ⇒ stack overflow (memory crash).

8.6 Five Worked Examples (Algorithm + C)

A recursive organigramme always has the same shape: a decision (base case?) with one branch returning directly and

the other making a smaller call.

Example 6. Factorial (recursive).

→ Algorithm:
Function factorial(n)
If n ≤ 1 Then Return 1 // base case
Else Return n * factorial(n-1) // smaller call
EndIf

→C:

77
Algorithms & Data Structures By Benabderrezak Youcef

#include <stdio.h>
int factorial(int n) { // n! recursively
if (n <= 1) return 1; // stop at 1
return n * factorial(n-1); // n times (n-1)!
}
int main() {
printf("%d\n", factorial(3)); // prints 6
return 0;
}

→ Organigramme (function factorial):

Enter factorial(n)

Yes
n ≤ 1? Return 1

No

Return n ×
factorial(n-1)

→ Déroulement (step-by-step run) for factorial(3):

call does returns

factorial(3) 3*factorial(2) 6
factorial(2) 2*factorial(1) 2
factorial(1) base case 1

Example 7. Sum 1 + · · · + n (recursive).

→ Algorithm:
Function sum(n)
If n = 0 Then Return 0 // base case
Else Return n + sum(n-1) // add n, recurse
EndIf

→C:

78
Algorithms & Data Structures By Benabderrezak Youcef

#include <stdio.h>
int sum(int n) { // 1+2+...+n
if (n == 0) return 0; // nothing left
return n + sum(n - 1); // n plus the rest
}
int main() {
printf("%d\n", sum(3)); // prints 6
return 0;
}

→ Organigramme (function sum):

Enter sum(n)

Yes
n = 0? Return 0

No

Return n +
sum(n-1)

→ Déroulement (step-by-step run) for sum(3):

call does returns

sum(3) 3+sum(2) 6
sum(2) 2+sum(1) 3
sum(1) 1+sum(0) 1
sum(0) base case 0

Example 8. Power baseexponent (recursive, no pow).

→ Algorithm:
Function power(base, exponent)
If exponent = 0 Then Return 1 // base^0 = 1
Else Return base * power(base, exponent-1)
EndIf

→C:

79
Algorithms & Data Structures By Benabderrezak Youcef

#include <stdio.h>
int power(int base, int exponent) { // base^exponent
if (exponent == 0) return 1; // base case
return base * power(base, exponent-1); // one factor
}
int main() {
printf("%d\n", power(2, 3)); // prints 8
return 0;
}

→ Organigramme (function power):

Enter power(base,exp)

Yes
exp = 0? Return 1

No

Return base ×
power(base, exp-1)

→ Déroulement (step-by-step run) for power(2,3):

call does returns

power(2,3) 2*power(2,2) 8
power(2,2) 2*power(2,1) 4
power(2,1) 2*power(2,0) 2
power(2,0) base case 1

Example 9. Fibonacci (recursive).

→ Algorithm:
Function fib(n)
If n < 2 Then Return n // fib(0)=0, fib(1)=1
Else Return fib(n-1) + fib(n-2) // sum of two before
EndIf

→C:

80
Algorithms & Data Structures By Benabderrezak Youcef

#include <stdio.h>
int fib(int n) { // 0,1,1,2,3,5,...
if (n < 2) return n; // base cases
return fib(n-1) + fib(n-2);// add the two previous
}
int main() {
printf("%d\n", fib(4)); // prints 3
return 0;
}

→ Organigramme (function fib):

Enter fib(n)

Yes
n < 2? Return n

No

Return fib(n-
1)+fib(n-2)

→ Déroulement (step-by-step run) for fib(4):

call does returns

fib(4) fib(3)+fib(2) 3
fib(3) fib(2)+fib(1) 2
fib(2) fib(1)+fib(0) 1

Example 10. GCD by Euclid (recursive).

→ Algorithm:
Function gcd(a, b)
If b = 0 Then Return a // answer found
Else Return gcd(b, a mod b) // shrink the problem
EndIf

→C:

81
Algorithms & Data Structures By Benabderrezak Youcef

#include <stdio.h>
int gcd(int a, int b) { // greatest common divisor
if (b == 0) return a; // b zero -> a is the gcd
return gcd(b, a % b); // recurse on remainder
}
int main() {
printf("%d\n", gcd(12, 8));// prints 4
return 0;
}

→ Organigramme (function gcd):

Enter gcd(a,b)

Yes
b = 0? Return a

No

Return gcd(b,
a mod b)

→ Déroulement (step-by-step run) for gcd(12, 8):

call a mod b returns

gcd(12,8) 4 4
gcd(8,4) 0 4
gcd(4,0) base case 4

82
Algorithms & Data Structures By Benabderrezak Youcef

9 Files

9.1 Why Files?

Variables live in RAM and disappear when the program stops. A file on disk keeps data permanently. Djezzy

saves millions of call records; Jumia saves orders.

9.2 Types of Files and Operations

Type Content Example

Text file readable characters [Link]
Binary file raw bytes, compact [Link]

The 4 steps to use a file (always in this order):

Yes
Open Read / Write End of file? Close

No

Save a client to a text file:

FILE *f = fopen("[Link]", "w"); // open write
fprintf(f, "Amina 0555123456\n"); // write
fclose(f); // close

Modes: "r" read, "w" write (erase), "a" append (add at end).

9.3 Five Worked Examples (Algorithm + C)

Example 1. Write one transfer amount to a file.

83
Algorithms & Data Structures By Benabderrezak Youcef

→ Algorithm:
Open(file, "[Link]", write) // open for writing (erase)
Write(file, amount) // put the amount
Close(file) // save and close

→C:
#include <stdio.h>
int main() {
float amount = 5000; // amount to save
FILE *file = fopen("[Link]", "w"); // "w" = write
fprintf(file, "%.2f\n", amount);// write one line
fclose(file); // always close
return 0;
}

→ Organigramme:

Start

Open file (write)

Write amount

Close file

End

→ Déroulement (step-by-step run) for amount = 5000:

action file content

after write 5000.00

Example 2. Append a line without erasing (mode "a").

84
Algorithms & Data Structures By Benabderrezak Youcef

→ Algorithm:
Open(file, "[Link]", append) // add at the end
Write(file, amount) // new line
Close(file) // close

→C:
#include <stdio.h>
int main() {
float amount = 200; // amount to add
FILE *file = fopen("[Link]", "a"); // "a" = append
fprintf(file, "%.2f\n", amount);// add at the end
fclose(file); // close
return 0;
}

→ Organigramme:

Start

Open file (append)

Write amount at end

Close file

End

→ Déroulement (step-by-step run) file had 5000.00, amount = 200:

action file content

after append 5000.00 then 200.00

Example 3. Sum all amounts in a file.

85
Algorithms & Data Structures By Benabderrezak Youcef

→ Algorithm:
total ← 0 // total
While NOT EndOfFile(file) Do // until file ends
Read(file, amount) // read one number
total ← total + amount
EndWhile

→C:
#include <stdio.h>
int main() {
float amount, total = 0; // value and total
FILE *file = fopen("[Link]", "r"); // "r" = read
while (fscanf(file, "%f", &amount) == 1) // got a number?
total += amount; // add each amount
fclose(file); // close
printf("%.2f\n", total); // print the total
return 0;
}

→ Organigramme:

Start

Open file;
total ← 0

Read amount;
a number Yes
total ←
left?
total+amount

No

Write total

End

86
Algorithms & Data Structures By Benabderrezak Youcef

→ Déroulement (step-by-step run) file = 100, 200, 300:

read amount test total

100 ok 100
200 ok 300
300 ok 600

Example 4. Count the lines in a file.

→ Algorithm:
lines ← 0 // line counter
While NOT EndOfFile(file) Do
ch ← ReadChar(file) // one character
If ch = newline Then // end of a line?
lines ← lines + 1 // count it
EndIf
EndWhile

→C:
#include <stdio.h>
int main() {
int lines = 0, ch; // count and char
FILE *file = fopen("[Link]", "r"); // read mode
while ((ch = fgetc(file)) != EOF) // char by char
if (ch == ’\n’) // newline?
lines++; // one more line
fclose(file); // close
printf("%d\n", lines); // print line count
return 0;
}

→ Organigramme:

87
Algorithms & Data Structures By Benabderrezak Youcef

Start

Open file; lines ←

lines ← 0 lines+1
Y

Yes ch =
char left?
newline?

No

Write lines

End

→ Déroulement (step-by-step run) file = "a\nb\n":

ch is newline? lines
’a’ no 0
’\n’ yes 1
’b’ no 1
’\n’ yes 2

Example 5. Copy a file character by character into another.

→ Algorithm:
While NOT EndOfFile(source) Do
ch ← ReadChar(source) // read from source
WriteChar(dest, ch) // write to destination
EndWhile

→C:
#include <stdio.h>
int main() {
int ch; // current character
FILE *source = fopen("[Link]", "r"); // read
FILE *dest = fopen("[Link]", "w"); // write

88
Algorithms & Data Structures By Benabderrezak Youcef

while ((ch = fgetc(source)) != EOF) // until source ends

fputc(ch, dest); // copy it to dest
fclose(source); fclose(dest); // close both
return 0;
}

→ Organigramme:

Start

Open
source, dest

ch ← read
Yes
char left? source; write
ch to dest
No

Close both

End

→ Déroulement (step-by-step run) source = "Hi":

ch read dest so far

’H’ H
’i’ Hi
EOF stop, dest="Hi"

89
Algorithms & Data Structures By Benabderrezak Youcef

10 Pointers and Dynamic Memory

10.1 What Is a Pointer?

A pointer is a variable that stores the address (the location in memory) of another variable, instead of storing a

normal value. Two operators go with it: &x gives the address of x, and *p gives the value stored at the address in

p (this is called dereferencing).

▶ In plain words: Think of memory as a street of houses, each with an address. A normal variable is the thing

inside a house; a pointer is a paper with a house address written on it. &x = “write down x’s address”; *p = “go

to the address on the paper and look inside”. Pointers matter because they let a function change the real variable

(not a copy), and they let us build structures that grow at run time (linked lists, trees).

address 0x7A
points to
p: 0x7A x: 4.8

10.2 Dynamic Memory

Static memory = fixed size at compile time. Dynamic memory = asked for at run time with malloc, freed with

free. Needed when you do not know the size in advance (e.g. number of ride requests today).

int *t = malloc(n * sizeof(int)); // ask n integers

// ... use t[0..n-1] ...
free(t); // give memory back

Every malloc needs a free. Forgetting = memory leak: the app slowly eats all RAM and crashes.

10.3 Five Worked Examples (Algorithm + C)

Example 1. Change a variable through a pointer.

90
Algorithms & Data Structures By Benabderrezak Youcef

→ Algorithm:
pointer ← address(x) // remember where x is
value_at(pointer) ← 99 // change x through it

→C:
#include <stdio.h>
int main() {
int x = 5; // a variable
int *pointer = &x; // holds address of x
*pointer = 99; // *pointer is x -> x=99
printf("%d\n", x); // prints 99
return 0;
}

→ Organigramme:

Start

pointer ← address(x)

value_at(pointer) ← 99

Write x

End

→ Déroulement (step-by-step run) for x = 5:

step pointer x
pointer=&x addr(x) 5
*pointer=99 addr(x) 99

Example 2. Increment a variable via a function (by reference).

91
Algorithms & Data Structures By Benabderrezak Youcef

→ Algorithm:
Procedure increment(var number) // real variable
number ← number + 1 // add one

→C:
#include <stdio.h>
void increment(int *number) { // pointer to real var
(*number)++; // add 1 to value at it
}
int main() {
int y = 7; // a variable
increment(&y); // pass its address
printf("%d\n", y); // prints 8
return 0;
}

→ Organigramme (procedure increment):

Enter increment(number)

number ←
number + 1

Return

→ Déroulement (step-by-step run) for y = 7:

step y
before 7
after increment 8

Example 3. Allocate an array of size integers, fill 0, free.

→ Algorithm:

92
Algorithms & Data Structures By Benabderrezak Youcef

table ← Allocate(size) // ask memory for size ints

For i ← 0 to size-1 Do // each slot
table[i] ← 0 // set to zero
EndFor
Free(table) // give memory back

→C:
#include <stdio.h>
#include <stdlib.h> // for malloc / free
int main() {
int size = 3, i; // number of slots
int *table = malloc(size * sizeof(int)); // reserve
for (i = 0; i < size; i++) // each slot
table[i] = 0; // fill with 0
free(table); // release memory
return 0;
}

→ Organigramme:

Start

table ←
Allocate(size);
i←0

Yes table[i] ←
i < size?
0; i ← i+1

No

Free(table)

End

93
Algorithms & Data Structures By Benabderrezak Youcef

→ Déroulement (step-by-step run) for size = 3:

step array table

after malloc [ ?, ?, ? ]
after loop [0, 0, 0]
after free (memory freed)

Example 4. Return the biggest through a pointer output.

→ Algorithm:
Procedure findBiggest(table, size, var result)
result ← table[0] // first as candidate
For i ← 1 to size-1 Do
If table[i] > result Then
result ← table[i]
EndIf
EndFor

→C:
#include <stdio.h>
void findBiggest(int *table, int size, int *result) {
*result = table[0]; // start with element 0
for (int i = 1; i < size; i++) // scan the rest
if (table[i] > *result) // found bigger?
*result = table[i]; // store via pointer
}
int main() {
int t[3] = {4, 9, 2}, big; // array and output
findBiggest(t, 3, &big); // pass address of big
printf("%d\n", big); // prints 9
return 0;
}

→ Organigramme (procedure findBiggest):

94
Algorithms & Data Structures By Benabderrezak Youcef

Enter findBiggest

result ← result ←
table[0]; i ← 1 table[i]
Y

Yes table[i]
i < size?
> result?

No

Return

→ Déroulement (step-by-step run) for table = [4, 9, 2]:

i table[i] result
- - 4
1 9 9
2 2 9

Example 5. Reserve an array whose size is read at runtime.

→ Algorithm:
Read(size) // size decided at runtime
table ← Allocate(size) // reserve size slots
Free(table) // free when done

→C:
#include <stdio.h>
#include <stdlib.h> // for malloc / free
int main() {
int size; // unknown until run
scanf("%d", &size); // read the size
int *table = malloc(size * sizeof(int)); // reserve
/* use table[0..size-1] here */
free(table); // release it
return 0;
}

→ Organigramme:

95
Algorithms & Data Structures By Benabderrezak Youcef

Start

Read size

table ← Allocate(size)

Free(table)

End

→ Déroulement (step-by-step run) for size = 5:

step result
read size 5
malloc array of 5 ints

96
Algorithms & Data Structures By Benabderrezak Youcef

11 Linked Lists

11.1 Idea

A linked list is a chain of nodes. Each node holds two things: some data, and a pointer to the next node. A

special head pointer marks the first node, and the last node’s pointer is NULL (meaning “nothing after me”). Unlike

an array, a linked list has no fixed size – it grows and shrinks freely while the program runs.

▶ In plain words: Think of a treasure hunt: each clue (node) holds a message (data) and tells you where the

next clue is (the pointer). You must start at the first clue (head) and follow them one by one; you cannot jump

straight to clue number 5. That is the trade-off: a linked list is great for inserting and removing anywhere (just

change a couple of pointers), but slow to reach the i-th element (you must walk the chain).

head 10 • 20 • 30 • NULL

struct Node {
int data;
struct Node *next;
};

11.2 Array vs Linked List

Array Linked List

Size fixed grows/shrinks
Access element i fast (direct) slow (walk the chain)
Insert/delete middle slow (shift all) fast (change pointers)
Memory one block scattered nodes

11.3 Operations on a Linked List

97
Algorithms & Data Structures By Benabderrezak Youcef

Insert at the head (fastest insertion):

struct Node *newN = malloc(sizeof(struct Node));
newN->data = 5;
newN->next = head; // new node points to old first
head = newN; // head now points to new node

Only pointers move – no shifting like an array. Insert / delete = a few pointer changes.

11.4 Doubly Linked Lists

Each node has two pointers: next and prev. You can walk both directions. Used for browser history (back/for-

ward), music playlists.

A B C

11.5 Stacks and Queues (Special Lists)

Stack (LIFO) – Last In, First Out. Like a pile of plates: add/remove on top only. Operations: push, pop.

Queue (FIFO) – First In, First Out. Like a line at the bakery: add at back, remove at front. Operations: enqueue,

dequeue.

Stack (LIFO) Queue (FIFO)

push/pop
A dequeue enqueue
A B C
B
C

Where they appear in Algeria:

• Stack: the Undo button in an app; function calls (recursion).

• Queue: Yassir ride requests served in order; a printer job queue.

98
Algorithms & Data Structures By Benabderrezak Youcef

11.6 Five Worked Examples (Algorithm + C)

Every program declares struct Node { int data; struct Node *next; }; first.

Example 1. Insert a node at the head.

→ Algorithm:
newNode ← NewNode(value) // make a node
[Link] ← head // it points to old first
head ← newNode // head points to newNode

→C:
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
struct Node *head = NULL; // empty list
struct Node *newNode = malloc(sizeof(struct Node));
newNode->data = 10; // store the value
newNode->next = head; // link to old first
head = newNode; // newNode is first now
return 0;
}

→ Organigramme:

99
Algorithms & Data Structures By Benabderrezak Youcef

Start

newNode ←
NewNode(value)

[Link] ← head

head ← newNode

End

→ Déroulement (step-by-step run) list = 20→30, insert value = 10:

step list
before 20 → 30
after 10 → 20 → 30

Example 2. Count the nodes.

→ Algorithm:
count ← 0 // counter
current ← head // start at first node
While current ̸= NULL Do // until end
count ← count + 1 // count this node
current ← [Link] // move forward
EndWhile

→C:
int countNodes(struct Node *head) {
int count = 0; // counter
struct Node *current = head; // walker
while (current != NULL) { // while a node exists
count++; // count it
current = current->next; // go to next
}
return count; // total nodes

100
Algorithms & Data Structures By Benabderrezak Youcef

→ Organigramme:

Start

count ← 0;
current ← head

count ←
current ̸= Yes
count+1; current
NULL?
← [Link]

No

Write count

End

→ Déroulement (step-by-step run) list = 10→20→30:

current count
10 1
20 2
30 3
NULL stop, count=3

Example 3. Search a value in the list.

→ Algorithm:
current ← head // start at first
While current ̸= NULL Do
If [Link] = value Then // found?
Return True
EndIf
current ← [Link] // next node
EndWhile

101
Algorithms & Data Structures By Benabderrezak Youcef

Return False // not found

→C:
int search(struct Node *current, int value) {
while (current != NULL) { // until end
if (current->data == value) // match?
return 1; // found
current = current->next; // advance
}
return 0; // not found
}

→ Organigramme:

Start

current ← head

loop current ̸= No
Return false
NULL?

Yes

Yes
data = value? Return true

No

current ←
[Link]

→ Déroulement (step-by-step run) list = 10→20→30, value = 20:

[Link] = 20? action

10 no advance
20 yes return true

102
Algorithms & Data Structures By Benabderrezak Youcef

Example 4. Stack push / pop (array-based).

→ Algorithm:
push(value): top ← top+1 ; stack[top] ← value
pop(): value ← stack[top] ; top ← top-1 ; Return value

→C:
#include <stdio.h>
int stack[100], top = -1; // empty stack
void push(int value) { // add on top
top = top + 1; // move top up
stack[top] = value; // store value
}
int pop() { // remove the top
int value = stack[top]; // read top
top = top - 1; // move top down
return value; // give it back
}

→ Organigramme (push):

Enter push(value)

top ← top + 1

stack[top] ← value

Return

→ Déroulement (step-by-step run) push 5, push 8, pop:

op top stack
push 5 0 [5]
push 8 1 [5,8]
pop 0 [5], returns 8

103
Algorithms & Data Structures By Benabderrezak Youcef

Example 5. Queue enqueue / dequeue (array-based).

→ Algorithm:
enqueue(value): queue[back] ← value ; back ← back+1
dequeue(): value ← queue[front] ; front ← front+1 ; Return value

→C:
#include <stdio.h>
int queue[100], front = 0, back = 0; // empty queue
void enqueue(int value) { // add at the back
queue[back] = value; // store value
back = back + 1; // move back
}
int dequeue() { // remove from the front
int value = queue[front]; // read front
front = front + 1; // move front
return value; // give it back
}

→ Organigramme (enqueue):

Enter enqueue(value)

queue[back] ← value

back ← back + 1

Return

→ Déroulement (step-by-step run) enqueue 5, enqueue 8, dequeue:

op front back returns

enqueue 5 0 1 -
enqueue 8 0 2 -
dequeue 1 2 5

104
Algorithms & Data Structures By Benabderrezak Youcef

ASD 2 summary: we made code reusable (functions/recursion), permanent (files), and dynamic (pointers, linked

lists, stacks, queues). ASD 3 uses these to build fast algorithms and tree/graph structures.

105
Algorithms & Data Structures By Benabderrezak Youcef

12 ASD 2 – Solved Exercises

Exercise 1. Function max(a,b) = bigger of two integers. Solution: → Algorithm:

Function max(a,b): If a>b Then Return a Else Return b EndIf

→C:
int max(int a,int b){ return a>b?a:b; }

Exercise 2. Procedure printBill(amount, fee) (returns nothing). Solution: → Algorithm:

Procedure printBill(a,f): Write("Total=", a+f)

→C:
void printBill(float a,float f){ printf("Total=%.2f\n",a+f); }

Exercise 3. Why does swap need pointers? Write it. Solution: By value gives a copy, changes lost; pointers give the

real variables. → Algorithm:

Procedure swap(var a, var b): t ← a; a ← b; b ← t

→C:
void swap(int *a,int *b){ int t=*a; *a=*b; *b=t; }

Exercise 4. Recursive sum 1 + · · · + n. Solution: → Algorithm:

Function s(n): If n=0 Then Return 0 Else Return n+s(n-1) EndIf

→C:

106
Algorithms & Data Structures By Benabderrezak Youcef

int s(int n){ if(n==0) return 0; return n+s(n-1); }

Exercise 5. Recursive power xn . Solution: → Algorithm:

Function pw(x,n): If n=0 Then Return 1 Else Return x*pw(x,n-1) EndIf

→C:
int pw(int x,int n){ if(n==0) return 1; return x*pw(x,n-1); }

Exercise 6. Count lines in [Link]. Solution: → Algorithm:

c ← 0
While NOT EndOfFile(f) Do
ch ← ReadChar(f); If ch=newline Then c ← c+1 EndIf
EndWhile

→C:
FILE *f=fopen("[Link]","r"); int c=0,ch;
while((ch=fgetc(f))!=EOF) if(ch==’\n’) c++;
fclose(f);

Exercise 7. Allocate n integers, fill 0, free. Solution: → Algorithm:

t ← Allocate(n)
For i ← 0 to n-1 Do t[i] ← 0 EndFor
Free(t)

→C:
int *t=malloc(n*sizeof(int));
for(int i=0;i<n;i++) t[i]=0; free(t);

Exercise 8. Insert value 5 at the head of a list. Solution: → Algorithm:

107
Algorithms & Data Structures By Benabderrezak Youcef

n ← NewNode(5); [Link] ← head; head ← n

→C:
Node *n=malloc(sizeof(Node));
n->data=5; n->next=head; head=n;

Exercise 9. Count the nodes of a list. Solution: → Algorithm:

c ← 0; p ← head
While p ̸= NULL Do c ← c+1; p ← [Link] EndWhile

→C:
int c=0; Node*p=head;
while(p){ c++; p=p->next; }

Exercise 10. Stack: push A,B,C then pop twice. What is left? Solution: Push A,B,C ⇒ top=C. Pop→C, pop→B.

Left: A (LIFO). → C :
push(’A’);push(’B’);push(’C’); pop();pop(); // ’A’ remains

ASD 2 – Homework (statements only)

HW1. Write a function fee(amount) returning the 1% fee.

HW2. Write a function isEnough(balance, amount) returning a boolean.

HW3. Write a procedure that prints a line of n stars.

HW4. Write a function that returns the number of digits of an integer.

HW5. Explain local vs global variables with a small example of each.

HW6. Write increment(int *x) that adds 1 to the real variable.

108
Algorithms & Data Structures By Benabderrezak Youcef

HW7. Recursive factorial; then say what fact(5) returns.

HW8. Recursive Fibonacci; draw the call tree for fib(4).

HW9. Recursive function to reverse-print a string.

HW10. Recursive GCD (Euclid) of two numbers.

HW11. Rewrite the recursive sum 1 + · · · + n as a loop; compare.

HW12. Open a file and copy it line by line into a second file.

HW13. Read a file of transfers and print the total.

HW14. Append a new transfer line to [Link] without erasing it (mode a).

HW15. Save an array of 5 accounts to a binary file, then read it back.

HW16. Explain the difference between &x and *p with a drawing.

HW17. Allocate a matrix n × m dynamically and free it correctly.

HW18. What is a memory leak? Give a code example that leaks.

HW19. Define struct Node; build a list of 3 nodes by hand in main.

HW20. Insert a node at the end of a linked list.

HW21. Delete the first node of a linked list (free it).

HW22. Search a value in a linked list; return True/False.

HW23. Reverse a singly linked list.

109
Algorithms & Data Structures By Benabderrezak Youcef

HW24. Compare array vs linked list for insert-at-front; which is faster and why?

HW25. Build a doubly linked list of 3 nodes; walk it forward and backward.

HW26. Implement a stack with an array (push, pop, isEmpty).

HW27. Implement a queue with an array (enqueue, dequeue).

HW28. Use a stack to check if parentheses () in a string are balanced.

HW29. Use a queue to simulate 3 Yassir ride requests served in order.

HW30. Implement a stack using a linked list instead of an array.

110
Algorithms & Data Structures By Benabderrezak Youcef

MODULE ASD 3
Complexity, Sorting, Trees, Graphs

111
Algorithms & Data Structures By Benabderrezak Youcef

13 Algorithmic Complexity

13.1 Why Measure Complexity?

Complexity tells how the time (or memory) an algorithm needs grows when the input size n grows. It does not

depend on the computer – it counts the number of basic operations (comparisons, additions. . . ). We write it with

Big-O: O( f (n)), which keeps only the part that matters for large n.

▶ In plain words: We do not measure complexity in seconds, because seconds change from one computer to

another. Instead we ask: “if I double the data, how much more work?” If doubling n roughly doubles the work,

that is O(n) (good). If doubling n makes the work 4× bigger, that is O(n2 ) (slower). Big-O ignores small details

(constants, the +5) and keeps only the fastest-growing term, because for big n that term decides everything.

Yassir with n = 50 000 intersections: an O(n2 ) algorithm does 2.5 billion steps; an O(n log n) one does ≈ 780 000.

That is the difference between hours and a second.

13.2 Common Complexity Classes

Big-O Name Example

O(1) constant access array[i]
O(log n) logarithmic binary search
O(n) linear scan a list once
O(n log n) linearithmic merge sort, quicksort
O(n2 ) quadratic bubble sort
O(2n ) exponential try all subsets

112
Algorithms & Data Structures By Benabderrezak Youcef

time

O(n2 )

O(2n ) O(n)

O(1)
n

13.3 Computing Complexity

Rules of thumb:

• A simple instruction = O(1).

• A loop of n steps = O(n).

• A loop inside a loop = O(n2 ).

• Keep only the biggest term, drop constants: 3n2 + 5n + 9 → O(n2 ).

13.4 Five Worked Examples (Algorithm + C)

Example 1. O(1): access one array element.

→ Algorithm:
x ← t[i] // one step, size does not matter

→C:
int x=t[i]; /* O(1) */

Example 2. O(n): scan and sum.

→ Algorithm:

113
Algorithms & Data Structures By Benabderrezak Youcef

For i ← 0 to n-1 Do s ← s+t[i] EndFor

→C:
for(int i=0;i<n;i++) s+=t[i]; /* O(n) */

Example 3. O(n2 ): all pairs.

→ Algorithm:
For i ← 0 to n-1 Do
For j ← 0 to n-1 Do count ← count+1 EndFor
EndFor

→C:
for(int i=0;i<n;i++)
for(int j=0;j<n;j++) count++; /* O(n^2) */

Example 4. O(log n): halving loop.

→ Algorithm:
While n > 1 Do n ← n div 2 EndWhile

→C:
while(n>1) n/=2; /* O(log n) */

Example 5. Simplify a step count to Big-O.

→ Algorithm:
5*n*n + 3*n + 100 -> keep biggest -> O(n^2)

→C:

114
Algorithms & Data Structures By Benabderrezak Youcef

/* drop constants and lower terms: O(n^2) */

115
Algorithms & Data Structures By Benabderrezak Youcef

14 Sorting Algorithms

14.1 Overview

Sorting = arrange data in order (prices low→high, drivers by rating). We compare 5 classic sorts.

Algorithm Average Worst Idea

Bubble O(n2 ) O(n2 ) swap neighbors
Selection O(n2 ) O(n2 ) pick the min each time
Insertion O(n2 ) O(n2 ) insert into sorted part
Merge O(n log n) O(n log n) divide & merge
Quick O(n log n) O(n2 ) pivot partition

14.2 Bubble Sort

Walk the array from left to right. Look at two neighbours at a time. If they are in the wrong order (left bigger than

right), swap them. When you reach the end, the biggest value has “bubbled” to the last place. Repeat the whole

walk again for the rest, until one full walk makes no swap – then the array is sorted.

▶ In plain words: Imagine bubbles of air rising in water: the biggest bubble reaches the top first. Here the biggest

number moves to the end on the first pass, the second biggest on the second pass, and so on. It is the simplest sort

to understand, but also one of the slowest (O(n2 )): for 1000 items it does about a million comparisons.

Sort prices [30, 10, 20]:

[ 30, 10, 20 ] → swap → [ 10, 30, 20 ]

[ 10, 30, 20 ] → swap → [ 10, 20, 30 ]

[ 10, 20, 30 ] sorted ✓

116
Algorithms & Data Structures By Benabderrezak Youcef

for (i=0; i<n-1; i++)

for (j=0; j<n-1-i; j++)
if (t[j] > t[j+1]) { swap(&t[j], &t[j+1]); }

14.3 Selection Sort

Look at the whole array and find the smallest element. Swap it into position 0 (the front). Now look at positions

1 to the end, find the smallest there, and swap it into position 1. Keep going: each round places one more element

in its final spot, from left to right.

▶ In plain words: Think of picking players for a team, always choosing the shortest remaining person and lining

them up. After each choice, the front part of the line is sorted and never changes again. Selection sort always does

the same number of comparisons (≈ n2 /2), even if the array is already sorted – so it is steady but not fast.

14.4 Insertion Sort

Keep the left part of the array sorted. Take the next element (the first one of the unsorted right part) and slide it

left, stepping over every bigger element, until it sits in its correct place. Repeat for every element. The sorted part

grows by one each time.

▶ In plain words: This is exactly how most people sort playing cards in their hand: you pick up a new card and

push it left until it is in the right spot, leaving the cards on its left already ordered. Insertion sort is fast when the

array is almost sorted (few slides needed), which makes it useful in real programs even though its worst case is

still O(n2 ).

14.5 Merge Sort (Divide and Conquer)

Divide the array into two halves. Sort each half by calling merge sort again on it (recursion), until a piece has only

one element (already sorted). Then merge: walk the two sorted halves together, always taking the smaller front

element, to build one sorted array. This is a divide-and-conquer method and is always O(n log n).

117
Algorithms & Data Structures By Benabderrezak Youcef

▶ In plain words: Splitting keeps halving the array: 1000 → 500 → 250 → . . . down to single elements. That

is why there are only about log2 n levels (≈ 10 for 1000 items), and each level does n work to merge – giving

n × log n, far faster than n2 . The cost is that merge sort needs extra memory for the merged copy.

38 27 43 3

38 27 43 3

38 27 43 3

divide down → then merge back up sorted: 3 27 38 43

14.6 Quick Sort

Choose one element as the pivot (often the last one). Rearrange the array so that all elements smaller than the

pivot go to its left and all bigger ones to its right – this step is called partition. Now the pivot is in its final place.

Then apply quicksort again to the left part and to the right part. When every part has size 1, the whole array is

sorted.

▶ In plain words: Quicksort is like organising a crowd by height: pick one person, tell everyone shorter to stand

on the left and everyone taller on the right; that person is now correctly placed, and you repeat inside each side.

On average it is O(n log n) and very fast in practice, which is why it is the most used sort. Its worst case is O(n2 )

(a bad pivot, e.g. an already-sorted array), but good pivot choices make this rare.

pivot = 25: [ 10, 20 | 25 | 40, 30 ]

14.7 Five Worked Examples (Algorithm + C)

Example 1. Bubble sort.

→ Algorithm:

118
Algorithms & Data Structures By Benabderrezak Youcef

For i ← 0 to n-2 Do
For j ← 0 to n-2-i Do
If t[j]>t[j+1] Then swap(t[j],t[j+1]) EndIf
EndFor
EndFor

→C:
for(int i=0;i<n-1;i++)
for(int j=0;j<n-1-i;j++)
if(t[j]>t[j+1]){int x=t[j];t[j]=t[j+1];t[j+1]=x;}

Example 2. Selection sort.

→ Algorithm:
For i ← 0 to n-2 Do
m ← i
For j ← i+1 to n-1 Do If t[j]<t[m] Then m ← j EndIf EndFor
swap(t[i],t[m])
EndFor

→C:
for(int i=0;i<n-1;i++){ int m=i;
for(int j=i+1;j<n;j++) if(t[j]<t[m]) m=j;
int x=t[i];t[i]=t[m];t[m]=x; }

Example 3. Insertion sort.

→ Algorithm:
For i ← 1 to n-1 Do
key ← t[i] ; j ← i-1
While j≥0 AND t[j]>key Do t[j+1] ← t[j]; j ← j-1 EndWhile
t[j+1] ← key
EndFor

→C:

119
Algorithms & Data Structures By Benabderrezak Youcef

for(int i=1;i<n;i++){ int key=t[i], j=i-1;

while(j>=0 && t[j]>key){ t[j+1]=t[j]; j--; }
t[j+1]=key; }

Example 4. Merge two sorted arrays into one.

→ Algorithm:
i ← 0; j ← 0; k ← 0
While i<n AND j<m Do
If a[i]≤b[j] Then c[k] ← a[i]; i++ Else c[k] ← b[j]; j++ EndIf
k ← k+1
EndWhile
// copy the rest of a, then b

→C:
int i=0,j=0,k=0;
while(i<n&&j<m) c[k++]=(a[i]<=b[j])?a[i++]:b[j++];
while(i<n) c[k++]=a[i++];
while(j<m) c[k++]=b[j++];

Example 5. Quicksort partition (Lomuto).

→ Algorithm:
pivot ← t[hi] ; i ← lo-1
For j ← lo to hi-1 Do
If t[j]<pivot Then i++; swap(t[i],t[j]) EndIf
EndFor
swap(t[i+1],t[hi]) ; Return i+1

→C:
int part(int t[],int lo,int hi){ int p=t[hi],i=lo-1;
for(int j=lo;j<hi;j++) if(t[j]<p){i++;
int x=t[i];t[i]=t[j];t[j]=x;}
int x=t[i+1];t[i+1]=t[hi];t[hi]=x; return i+1; }

120
Algorithms & Data Structures By Benabderrezak Youcef

15 Trees

15.1 Definitions

▶ In plain words: A tree is like a family tree turned upside down: one ancestor at the top (the root), and branches

going down to children, grandchildren, and so on. Or think of a company: one director at the top, managers below,

employees below them. Unlike a linked list (a straight chain), a tree branches, so one node can lead to several

others.

A tree is a structure of nodes with one root at top; each node has children below. Terms:

• Root – the top node.

• Leaf – a node with no children.

• Parent / Child – direct links.

• Height – longest path from root to a leaf.

B C

D E F

root = A, leaves (green) = D, E, F, height = 2

15.2 Binary Tree

A binary tree: each node has at most 2 children (left and right).

121
Algorithms & Data Structures By Benabderrezak Youcef

struct TreeNode {
int data;
struct TreeNode *left, *right;
};

15.3 Tree Traversals

Visiting all nodes in an order. For binary trees, three classic orders (R = root, L = left, G = right/greater side):

• Prefix (pre-order, R-L-G): root first, then left, then right.

• Infix (in-order, L-R-G): left, then root, then right. Gives sorted order in a BST.

• Postfix (post-order, L-G-R): left, right, then root last.

Traverse this tree:

2 3

4 5

• Pre-order: 1, 2, 4, 5, 3

• In-order: 4, 2, 5, 1, 3

• Post-order: 4, 5, 2, 3, 1

15.4 Binary Search Tree (BST)

A BST keeps order: for every node, everything in its left subtree is smaller than the node, and everything in its

right subtree is bigger. This rule holds at every node. It makes search O(log n) (if the tree is balanced) instead of

O(n).

122
Algorithms & Data Structures By Benabderrezak Youcef

▶ In plain words: The order rule is what makes a BST powerful. To find a value you compare it with the current

node: if it is smaller you go left, if bigger you go right – so you throw away half the tree at every step, like looking

up a word in a dictionary by opening near the right letter instead of reading every page. That is why searching a

million keys takes only about 20 steps.

50

30 70

20 40 60 80

To find 60: 60>50 go right, 60<70 go left, found. Only 3 steps.

Jumia product search: store product IDs in a BST. Searching one ID among a million is ≈ 20 comparisons

(log2 106 ), not a million.

15.5 Five Worked Examples (Algorithm + C)

Example 1. Pre-order traversal (R-L-G).

→ Algorithm:
Procedure pre(node)
If node ̸= NULL Then
Write([Link]); pre([Link]); pre([Link])
EndIf

→C:
void pre(T*n){ if(n){ printf("%d ",n->data);
pre(n->left); pre(n->right);} }

Example 2. In-order traversal (L-R-G) = sorted for a BST.

→ Algorithm:

123
Algorithms & Data Structures By Benabderrezak Youcef

Procedure in(node)
If node ̸= NULL Then in([Link]); Write([Link]); in([Link]) EndIf

→C:
void in(T*n){ if(n){ in(n->left);
printf("%d ",n->data); in(n->right);} }

Example 3. Count nodes (recursive).

→ Algorithm:
Function count(node)
If node = NULL Then Return 0
Else Return 1+count([Link])+count([Link]) EndIf

→C:
int count(T*n){ if(!n) return 0;
return 1+count(n->left)+count(n->right); }

Example 4. Height of a tree (no library).

→ Algorithm:
Function height(node)
If node = NULL Then Return 0
hl ← height([Link]); hr ← height([Link])
If hl>hr Then Return 1+hl Else Return 1+hr EndIf

→C:
int h(T*n){ if(!n) return 0;
int a=h(n->left),b=h(n->right);
return 1+(a>b?a:b); }

Example 5. Search in a BST.

→ Algorithm:

124
Algorithms & Data Structures By Benabderrezak Youcef

Function find(node, v)
If node=NULL Then Return False
If v=[Link] Then Return True
If v<[Link] Then Return find([Link],v)
Else Return find([Link],v) EndIf

→C:
int find(T*n,int v){ if(!n) return 0;
if(v==n->data) return 1;
return v<n->data? find(n->left,v):find(n->right,v); }

125
Algorithms & Data Structures By Benabderrezak Youcef

16 Graphs

16.1 Definition

▶ In plain words: A graph is the natural way to draw a map or a network: cities joined by roads, people joined

by friendships, web pages joined by links, phone towers joined by cables. The dots are vertices and the lines

joining them are edges. A tree is a special graph with no loops and one root; a general graph can have loops and

any connections.

A graph G = (V, E) is a set of vertices V (nodes) linked by edges E. Unlike a tree, it can have cycles and any

connections.

• Directed – edges have arrows (one-way street).

• Weighted – edges have a number (distance, cost).

5
A B
7
3 2

C D
4

A weighted graph: e.g. Algiers zones with road distances (km).

16.2 Representing a Graph

Two ways to store a graph:

• Adjacency matrix – n × n table, cell [i][ j] = 1 (or weight) if edge exists. Simple but O(n2 ) memory.

• Adjacency list – for each vertex, a linked list of its neighbors. Best for sparse graphs (few edges), like real

126
Algorithms & Data Structures By Benabderrezak Youcef

road maps.

Adjacency matrix

0 1 1
1 0 1
1 1 0

16.3 Graph Traversal

Traversal means visiting every vertex once, starting from one vertex. Two classic ways:

• BFS (Breadth-First Search): visit level by level – first the start, then all its direct neighbours, then their

neighbours, and so on. It uses a queue (FIFO). BFS finds the shortest path in an unweighted graph.

• DFS (Depth-First Search): go as deep as possible down one path, and only when you are stuck do you step

back (backtrack) and try another branch. It uses a stack (or recursion).

▶ In plain words: Picture exploring a maze. BFS is like flooding water in from the start: it reaches all rooms 1

step away, then all rooms 2 steps away – so the first time it reaches the exit, that is the shortest route. DFS is like

walking with one hand on the wall: you follow a corridor to its very end, then come back and try the next one.

BFS uses a queue (serve the oldest waiting vertex first); DFS uses a stack (continue from the most recent one).

S B D

BFS from S: S, A, B, C, D (level by level). DFS: S, A, D, B, C (deep first).

127
Algorithms & Data Structures By Benabderrezak Youcef

Yassir routing: the road network is a weighted graph. To find the shortest ride from Bab Ezzouar to Hydra, Yassir

runs a graph algorithm (like Dijkstra, built on BFS ideas + weights) on the adjacency list.

16.4 Five Worked Examples (Algorithm + C)

Example 1. Build an adjacency matrix; add edge (i,j) undirected.

→ Algorithm:
A[i][j] ← 1 ; A[j][i] ← 1

→C:
int A[N][N]={0};
A[i][j]=1; A[j][i]=1;

Example 2. Degree of a vertex (count neighbours).

→ Algorithm:
d ← 0
For j ← 0 to n-1 Do d ← d + A[v][j] EndFor

→C:
int d=0; for(int j=0;j<n;j++) d+=A[v][j];

Example 3. BFS with a queue (no library queue).

→ Algorithm:
enqueue(s); visited[s] ← True
While queue not empty Do
u ← dequeue(); Write(u)
For each neighbour w of u Do
If NOT visited[w] Then visited[w] ← True; enqueue(w) EndIf

128
Algorithms & Data Structures By Benabderrezak Youcef

EndFor
EndWhile

→C:
int q[N],f=0,b=0,vis[N]={0};
q[b++]=s; vis[s]=1;
while(f<b){ int u=q[f++]; printf("%d ",u);
for(int w=0;w<n;w++)
if(A[u][w]&&!vis[w]){vis[w]=1;q[b++]=w;} }

Example 4. DFS (recursive).

→ Algorithm:
Procedure dfs(u)
visited[u] ← True; Write(u)
For each neighbour w of u Do
If NOT visited[w] Then dfs(w) EndIf
EndFor

→C:
void dfs(int u){ vis[u]=1; printf("%d ",u);
for(int w=0;w<n;w++) if(A[u][w]&&!vis[w]) dfs(w); }

Example 5. Check if an edge exists between i and j.

→ Algorithm:
If A[i][j] = 1 Then Write("edge") Else Write("no edge") EndIf

→C:
if(A[i][j]) printf("edge\n"); else printf("no edge\n");

129
Algorithms & Data Structures By Benabderrezak Youcef

17 ASD 3 – Solved Exercises

Exercise 1. Give the Big-O of: (a) one loop over n, (b) two nested loops, (c) a single array[i] access. Solution: (a)

O(n), (b) O(n2 ), (c) O(1).

Exercise 2. Simplify the complexity 5n2 + 3n + 100. Solution: Keep the biggest term, drop constants ⇒ O(n2 ).

Exercise 3. Sort [5, 2, 4, 1] with bubble sort; show each pass. Solution: Pass 1: [2,4,1,5]. Pass 2: [2,1,4,5]. Pass

3: [1,2,4,5]. Sorted.

Exercise 4. How many comparisons does selection sort do on n = 4? Solution: 3+2+1 = 6 comparisons = n(n−1)/2,

so O(n2 ).

Exercise 5. Why is merge sort O(n log n)? Solution: It splits log2 n times (halving), and each level merges all n

elements ⇒ n × log n.

Exercise 6. Build a BST by inserting 50, 30, 70, 20, 60. Draw it. Solution: Root 50; 30 left; 70 right; 20 left-left; 60

under 70 on its left. Left<node<right holds everywhere.

Exercise 7. Give pre-, in-, post-order of the tree: root 1, children 2 (left) and 3 (right); 2 has children 4,5. Solution:

Pre: 1 2 4 5 3. In: 4 2 5 1 3. Post: 4 5 2 3 1.

Exercise 8. In a balanced BST of 1 000 000 keys, how many steps to search? Solution: ≈ log2 (106 ) ≈ 20 steps. That

is why BSTs are fast.

 
0 1 1
 
 
Exercise 9. Represent this graph as an adjacency matrix: edges A-B, A-C, B-C (3 vertices). Solution: 1 0 1 –
 
1 1 0

130
Algorithms & Data Structures By Benabderrezak Youcef

symmetric because the graph is undirected.

Exercise 10. Give BFS and DFS order from S for: S-A, S-B, A-C, B-C. Solution: BFS (queue, level by level): S, A,

B, C. DFS (stack/deep): S, A, C, B.

ASD 3 – Homework (statements only)

HW1. Give the Big-O of a loop that halves n each step.

HW2. Give the Big-O of three nested loops.

HW3. Order these by speed: O(n2 ), O(log n), O(n), O(1), O(n log n).

HW4. For n = 1000, estimate steps for O(n) vs O(n2 ).

HW5. Write bubble sort in C and count the swaps on [3,1,2].

HW6. Write selection sort in C.

HW7. Write insertion sort and trace it on [4,3,5,1].

HW8. Explain the merge step of merge sort with an example.

HW9. Trace quicksort on [6,2,8,4] with pivot = last element.

HW10. Which sorts are O(n log n)? Which are O(n2 )? Make a table.

HW11. When is quicksort O(n2 )? Give the bad case.

HW12. Sort an array of BaridiMob transfers descending; which sort do you pick and why?

HW13. Define: root, leaf, height, parent, child of a tree.

131
Algorithms & Data Structures By Benabderrezak Youcef

HW14. Draw a binary tree of height 3 with 7 nodes (full tree).

HW15. Insert 40,20,60,10,30 into a BST and draw it.

HW16. Delete the root of a small BST; explain the rule.

HW17. Give the in-order of a BST and show it is always sorted.

HW18. Write a recursive function that counts the nodes of a binary tree.

HW19. Write a recursive function for the height of a binary tree.

HW20. Write pre-order traversal in C (recursive).

HW21. Search a value in a BST (recursive); give its complexity.

HW22. What is a complete binary tree? Draw one and one that is not.

HW23. Define a graph; give the difference between directed and undirected.

HW24. Represent a 4-vertex graph as both a matrix and adjacency lists.

HW25. When is an adjacency list better than a matrix? Explain with road maps.

HW26. Write BFS using a queue (pseudo-code).

HW27. Write DFS using recursion (pseudo-code).

HW28. Give BFS and DFS orders for a graph you draw with 5 vertices.

HW29. Model the Algiers metro as a graph; find a path between two stations by BFS.

HW30. Explain why BFS finds the shortest path in an unweighted graph.

132
Algorithms & Data Structures By Benabderrezak Youcef

Summary: The Whole Journey

Module Topic Key Idea

ASD 1 Sequence read → process → write
ASD 1 Conditions If/Else, switch
ASD 1 Loops While, Repeat, For
ASD 1 Arrays 1D, 2D, strings
ASD 1 Custom types struct, enum
ASD 2 Subprograms functions, procedures
ASD 2 Recursion base case + smaller call
ASD 2 Files permanent storage
ASD 2 Pointers address + malloc/free
ASD 2 Linked lists nodes + next; stack (LIFO), queue (FIFO)
ASD 3 Complexity Big-O: O(1) . . . O(2n )
ASD 3 Sorting n2 : bubble/selection/insertion; n log n: merge/quick
ASD 3 Trees binary, BST, traversals (pre/in/post)
ASD 3 Graphs vertices+edges, BFS & DFS

Evaluation: Exam (60%) + Continuous Assessment (40%)

ASD 1 (S1) | ASD 2 (S2) | ASD 3 (S3)

Recommended language: C — IDE: CodeBlocks / DevCpp

133