Data Structures and Algorithms 2

Chapter 1
Programming : A General Overview

Dr. Fouzia ANGUEL

2nd year / S3

September 2024 – January 2025

 2
Course Outline

❖ Introduction

❖ Mathematics Review
- Exponent
- Logarithms
- Series
- Proofs
• Proof By Induction
- Sum of arithmetic serie
- Sum of squares
- Fibonacci numbers
• Proof By Counter Example
• Proof By Contradiction

❖ Recursion
- Recursion vs Iteration
 3

Introduction

What Is an Algorithm?

An algorithm is an explicit sequence of instructions, performed

on data, to accomplish a desired objective.

Example
Problem : determine the kth largest number in a group of
N numbers.

Selection problem
 4

Introduction

Selection problem

Algorithm 1

- read the N numbers into an array,

- sort the array in decreasing order

- return the element in position k.

 5

Introduction
Selection problem

Algorithm 2
- read the first k elements into an array and
sort them (in decreasing order).

- A new element, is ignored or it is placed in

its correct spot in the array, bumping one
element out of the array.

- The element in the kth position is returned

as the answer.
 6

Introduction

● An algorithm is considered correct if, for every input instance, it

terminates with the correct output.

● We say that a correct algorithm solves the given computational

problem.

● An incorrect algorithm might not terminate at all on some input

instances,

● or it might halt with an answer other than the desired one.

 7
Introduction
Selection problem
Simulation
● Using a random file of 30 million elements and
k =15,000,000.

● It showed that neither algorithm finishes in a reasonable

amount of time;

● Each one requires several days of computer processing to

terminate (although eventually with a correct answer).

● The proposed algorithms work, BUT they cannot be considered

good algorithms.

● In many problems, writing a working program is not good

enough.

● If the program is to be run on a large data set then the running

time becomes an issue .
 Introduction 8

How to estimate the running time of a program?

How can we tell which algorithm is better?
❖ We could implement both algorithms, run them both
Expensive and error prone

❖ Preferably, we should analyze them mathematically

Algorithm analysis

- measuring the resources needed for its execution,

time (how long the algorithm takes to run) and

space (how much memory the algorithm uses).

- It helps evaluate the efficiency of an algorithm, especially when

the input size becomes large.
 9

Mathematics Review

Exponents
XA XB = XA+B

XAB = (XA)B = (XB)A

XN +XN = 2XN ≠ X2N

2N +2N = 2N+1
 10
Mathematics Review

Logarithms
In computer science, all logarithms are to the base 2 unless
specified otherwise :
XA = B if and only if logx B = A

logA B = logC B / logCA A,B,C > 0 , A ≠ 0

log (AB ) = log A + log B A,B > 0

log (A/B ) = log A - log B
log (AB ) = B log A
alog n = nlog a
log 1 = 0 log 2 =1 log 1024 = 10 log 1048 576 = 10
Mathematics Review 11

Arithmetic series
Each term in an arithmetic series is increased by a constant value
(usually 1) :

Proof 1: write out the series twice and add each column
1 + 2 + 3 + ... + n – 2 + n – 1 + n
+ n + n – 1 + n – 2 + ... + 3 + 2 + 1
(n + 1) + (n + 1) + (n + 1) + . . . + (n + 1) + (n + 1) + (n + 1)

= n (n + 1)
Since we added the series twice, we must divide the result by 2
Mathematics Review 12

Geometric series
The next series we will look at is the geometric series with common
ratio r:

and if |r| < 1 then it is also true that

 13

Geometric series

proof : multiply by

Telescoping series:
all but the first and last terms cancel
 14

Geometric series

A common geometric series will involve the ratios r = ½ and r = 2:

Mathematics Review 15

Proofs
The two most common ways of proving statements in data-structure
analysis are proof by induction and proof by contradiction .

The best way of proving that a theorem is false is by exhibiting a

counterexample.
Proof by induction

➢ Prove that a property holds for input size 1 (base case)

➢ Assume that the property holds for input size 1,...n
(inductive hypothesis).
➢ Show that the property holds for input size n+1
(next value ).
Then, the property holds for all input sizes, n.
(this proves the theorem)
Mathematics Review
16
Proof by induction

Example 1: Let’s prove by induction the sum of the arithmetic serie :

The statement is true for n = 0:

Assume that the statement is true for an arbitrary n:

We must show that

Mathematics Review 17
Proof by induction
Then, for n + 1, we have:

By assumption, the second sum is known:

- The statement is true for n = 0 and

- the truth of the statement for n implies the truth of the statement for n + 1.
- Therefore, by the process of mathematical induction, the statement is true
for all values of n ≥ 0.
Mathematics Review
Proof by induction 18

Example 2 : Sum of Squares

Now we show that

1 + 22 + 32 +.........n2 =

1(1+1)(2+1)/6 = 1 Thus the property holds for n = 1 (base case)

Assume that the property holds for n=1,..m, thus

1 + 22 + 32 +.........m2 = m(m + 1)(2m + 1)/6

and show the property for m + 1,

1 + 22 + 32 +.........m2 +(m+1)2 = (m+1)(m + 2)(2m+3)/6 ?

1 + 22 + 32 +.........m2 +(m+1)2 = (m)(m + 1)(2m+1)/6 + (m+1)2

= (m+1)[m(2m+1)/6 +m+1]
= (m+1)[2m2 + m + 6m +6]/6

= (m+1)(m + 2)(2m + 3)/6

Mathematics Review 19
Proof by induction
Fibonacci Numbers
Example 3 :
Sequence of numbers, F0 F1 , F2 , F3 ,.......

F0 = 1, F1 = 1

Fi = Fi-1 + Fi-2 (Recurrence relation )

F2 = 2 , F3 = 3 , F4 = 5

Prove that Fn < (5/3)n for i>= 1

Base case:
F1 = 1 < (5/3 )
F2 = 2 < (5/3 )2
Mathematics Review 20
Proof by induction

We assume that the theorem is true for i= 1,...k (inductive hypothesis)

We need to show Fk+1 < (5/3)k+1 ?
We have :

Fk+1 = Fk + Fk-1

Fk+1 < (5/3)k + (5/3)k-1

< (⅗)(5/3)k+1 + (⅗)2(5/3)k+1
< ( (⅗)+ (⅗)2) (5/3)k+1
< (24/25) (5/3)k+1
Fk+1 < (5/3)k+1
proving the theorem
Mathematics Review 21

Proof by Counterexample

➢ Want to prove something is not true!

➢ Give an example to show that it does not hold!

Example: is FN < N2 ?

No, F11 = 144 > 121!

➢ However, if you were to show that FN < N2 is true

then you would need to show for all N, and not just one number.
Mathematics Review 22

Proof by Contradiction

➢ Suppose you want to prove a theorem .

➢ Assume that the theorem is false .

➢ Then show that you arrive at an impossibility and

hence the original assumption was erroneous .

Example: The proof that there is an infinite

number of prime numbers .
Mathematics Review 23

Proof by Contradiction
We assume that the theorem is false,
the number of primes is finite, k. So that The largest prime is Pk
Let P1, P2, ... , Pk be all the primes
Consider the number N = 1 + P1 * P2* ..... * Pk
N is larger than Pk , thus N is not prime (hypothesis)
So N must be the product of some primes.
However, none of the primes P1, P2 , ... , Pk divide N exactly.
So N is not a product of primes. (contradiction)

because every number is either prime or a product of primes

 Introduction to recursion 24
Let’s consider the following function f valid on nonnegative integers,
that satisfies :
f(0) = 0
f(x) = 2f(x − 1) + x2 x>0

A function that is defined in terms of itself is called recursive.

the recursive implementation of f

1. int f( int x )
2. {
3. if( x == 0 )
4. return 0;
5. else
6. return 2 * f( x - 1 ) + x * x;
7. }

A recursive function is a subroutine which calls itself, with different parameters.

 Introduction to recursion 25

Basic rules of recursion :

1. Base cases. You must always have some base cases, which can be
solved without recursion.

2. Making progress. For the cases that are to be solved recursively,

they should progressively move towards the base case.

3. Design rule. Assume that all the recursive calls work.

4. Compound interest rule. Never duplicate work by solving the same

instance of a problem in separate recursive calls.
 Introduction to recursion 26

Example 1 : Printing numbers digit by digit

We wish to print out a positive integer, n.

Our routine will have the heading printOut(n).
Assume that the only I/O routine available printDigit(m) will take a
single-digit number and outputs it.

1. void printOut( int n ) // Print nonnegative n

2. {
3. if( n >= 10 )
4. {printOut( n / 10 );}
5. printDigit( n % 10 );
6. }

Recursive routine to print an integer

 Introduction to recursion 27

Example 1 : Printing numbers digit by digit

Proof :Recursion and induction

Let us prove rigorously that the recursive number printing program works,
we’ll use a proof by induction.
- First, if n has one digit, then the program is trivially correct,
- Assume then that printOut works for all numbers of k or fewer digits.
- A number of k + 1 digits is expressed by its first k digits (n/10)
followed by its least significant digit.
by the inductive hypothesis, (n/10) is correctly printed,
and the last digit is n mod 10,

so the program prints out any (k+1)-digit number correctly.

 Introduction to recursion 28

Example 2 : Factorial

To evaluate factorial(n)
factorial(n) = n*(n-1)*...*2* 1

= n * factorial(n-1)

The recursive routine

1. int Factorial(int m)
2. {
3. If (m == 1 ) return 1
4. else return ( m * Factorial(m-1)) ;
5. }
 Introduction to recursion 29

Example 2 : Factorial

Recursion Versus Iteration

• Factorial of n (n>0) can be iteratively computed as follows:

factorial = 1
for j=1 to n
factorial ← factorial * j

• Compare to the recursive version.

• In general, iteration is more efficient than recursion because of

maintenance of state information, so use it when it simplifies the
problem.
 30
Introduction to recursion
Towers of Hanoi

- Source peg, Destination peg, Auxiliary peg

- k disks on the source peg,

- a bigger disk can never be on top of a smaller disk

Need to move all k disks to the destination peg using the auxiliary
peg, without ever keeping a bigger disk on the smaller disk.
 31
Introduction to recursion
Tower of Hanoi(k, source, auxiliary, destination)
{
If k=1 move disk from source to destination; (base case)
Else,
{
Tower of Hanoi(top k-1, source, destination,
auxiliary);
Move the kth disk from source to destination;
Tower of Hanoi(k-1, auxiliary, source, destination);
}
}