DATA STRUCTURES

AND ALGORITHMS

CONTENTS

1. Illustrative example

2. Basic concepts about algorithm

DATA STRUCTURES AND ALGORITHMS 3. Asymptotic notations
WEEK 1 : THE BASIC CONCEPTS 4. Algorithmic analysis techniques

3 4
OBJECTIVES CONTENTS

After this lesson, students can:

1. Illustrative example
1. Understand some basic concepts about algorithm
2. Basic concepts about algorithm
2. Know to use asymptotic notation to analyze the complexity of an
3. Asymptotic notations
algorithm
4. Algorithmic analysis techniques
3. Know how to analyze the complexity of an algorithm

5 6

1. ILLUSTRATIVE EXAMPLE 1. ILLUSTRATIVE EXAMPLE

• The maximum subarray problem:  Method 1: Brute force

• Browse all possible subarray off the given array: ai, ai+1 , …, aj where
• Given an array of n numbers: a1, a2, … , an
0 ≤ i ≤ j ≤ n-1, and calculate the sum of all elements in subarray to find the maximum sum.
• The contiguous subarray ai, ai+1 , …, aj with 1 ≤ i ≤ j ≤ n is a subarray of the given array and

∑ 𝑎 is called as the value of this subarray int maxSum = a[0];

for (int i = 0; i <= n-1; i++) {
• The task is to find the maximum value of all possible subarrays, in other words, find the for (int j = i; j <= n-1; j++) {
int sum = 0;
maximum ∑ 𝑎 . The subarray with the maximum value is called as the maximum subarray. for (int k = i; k <= j; k++) sum += a[k];
if (sum > maxSum) maxSum = sum;
}
Example: Given the array -2, 11, -4, 13, -5, 2 then the maximum subarray is 11, -4, 13 with the }

value = 11+ (-4)+13 =20

7 8
1. ILLUSTRATIVE EXAMPLE 1. ILLUSTRATIVE EXAMPLE

 Method 1: Brute force  Method 2: Brute force with better implementation

• Browse all possible subarray off the given array: ai, ai+1 , …, aj where Index i 0 1 2 3 4 5

0 ≤ i ≤ j ≤ n-1, and calculate the sum of all elements in subarray to find the maximum sum. a[i] -2 11 -4 13 -5 2

i = 0:
• Analyze the algorithm: we count the number of time the statement sum += a[k] that the 9 + (-4)=5 5
18 + (-5)=13 13

algorithm need to perform. The number is: (-2),(-2, 11), (-2,11, -4), (-2,11,-4,13), (-2,11,-4,13,-5), (-2,11,-4,13,-5,2)

-2+11 = 9 9 5+13=18 18
n 1 n 1 n 1 n 1
(n  i )(n  i  1)
int maxSum = a[0];

i 0 j i
( j  i  1)  (1  2  ...  (n  i ))  
i0 i 0 2 • We could see that, we can calculate the sum of the elements from position i to j from the
for (int i = 0; i<=n-1; i++) {
1 n 1 n n
 1  n( n  1)(2n  1) n( n  1)  sum of the elements from i to j-1 with just one addition:
  k ( k  1)    k 2   k   
for (int j = i; j<=n-1; j++) {

2 
int sum = 0; j j 1
2 k 1 2  k 1 k 1  2 6
 a[k ]  a[ j ]   a[k ]
for (int k=i; k<=j; k++) sum += a[k];
if (sum > maxSum) maxSum = sum;
} n3 n 2 n
}
   k i k i
6 2 3
The sum of elements from i to j The sum of elements from i to j-1

9 10

1. ILLUSTRATIVE EXAMPLE 1. ILLUSTRATIVE EXAMPLE

 Method 2: Brute force with better implementation  Method 2: Brute force with better implementation
j j 1 • Analyze the algorithm: We count the number of summation operations that the algorithm
 a[k ]  a[ j ]   a[k ]
k i k i
need to execute, it means count the number of times that the statement sum += a[j] is
executed. The number of summation operations is:
The sum of elements from i to j The sum of elements from i to j-1 n 1
n2 n
 (n  i)  n  (n  1)  ...  1 
i 0

2 2
int maxSum = a[0]; int maxSum = a[0]; int maxSum = a[0];
for (int i=0; i<=n-1; i++) {
for (int i=0; i<=n-1; i++) { for (int i=0; i<=n-1; i++) {
int sum = 0;
for (int j=i; j<=n-1; j++) { int sum = 0;
for (int j=i; j<=n-1; j++) {
int sum = 0; for (int j=i; j<=n-1; j++) {
sum += a[j];
for (int k=i; k<=j; k++) sum += a[k]; sum += a[j]; if (sum > maxSum) maxSum = sum;
if (sum > maxSum) maxSum = sum; if (sum > maxSum) maxSum = sum; }
} } }
} }

11 12
1. ILLUSTRATIVE EXAMPLE CONTENTS

 The number of times that the summation operations need to do is:

n3 n2 n
1. Illustrative example
• Method1. Brute force  
6 2 3
2 2. Basic concepts about algorithm
• Method 2. Brute force with better implementation n  n
2 2
 For the same problem, we have proposed two algorithms that require different numbers of 3. Asymptotic notations
operations, and therefore will require different calculation times.
4. Algorithmic analysis techniques
 The table below shows the calculation time of the above two algorithms, with the
assumption: the computer can perform 108 additions per second.

Complexity n=10 Time (sec) n=100 Time (sec) n=104 Time n=106 Time
n3 103 10-5 106 10-2 sec 1012 2.7 hours 1018 115 days
n2 100 10-6 10000 10-4 sec 108 1 sec 1012 2.7 hours

13 14

2. BASIC CONCEPTS ABOUT ALGORITHM 2. BASIC CONCEPTS ABOUT ALGORITHM

 An algorithm for solving a given problem is a defined procedure that includes a finite sequence of • Given 2 or more algorithms to solve the same problem, how do we select the best one?
steps that need to be performed to obtain an output from a given input (input) of the problem. • Some criteria for selecting an algorithm:
1) Is it easy to implement, understand, modify?
2) How long does it take to run it to completion? TIME
3) How much of computer memory does it use? SPACE

Input Algorithm Output

 Some basic characteristics of the algorithm:
 Precision
 Finiteness
 Uniqueness
 Generality

15 16
2. BASIC CONCEPTS ABOUT ALGORITHM 2. BASIC CONCEPTS ABOUT ALGORITHM

 Complexity of an algorithm:  Types of computation time:

• How to measure the computation time?
Best-case:
 The computation time of an algorithm depends on the size of input data (size increases, then
T(n) = minimum time of algorithm on any input of size n.
computation time increases).
Average-case:
 Thus, analyze running time as a function of input size. However, in some cases, even on
inputs of the same size, running time can be very different T(n) = expected time of algorithm over all inputs of size n.
• Example: In order to find the first prime number in an array: the algorithm scans the array Worst-case:
from left to right
• Array 1: 3 9 8 12 15 20 (algorithm stops when considering the first element) T(n) = maximum time of algorithm on any input of size n.
• Array 2: 9 8 3 12 15 20 (algorithm stops when considering the 3rd element)
• Array 3: 9 8 12 15 20 3 (algorithm stops when considering the last element)
 There are 3 types of computation time

17 18

2. BASIC CONCEPTS ABOUT ALGORITHM CONTENTS

 There are two ways to evaluate the computation time:

• Experimental Evaluation of computation time: 1. Illustrative example
• Write a program implementing the algorithm
• Run the program with inputs of varying size and composition 2. Basic concepts about algorithm
• Use a method like clock( ) to get an accurate measure of the actual running time
3. Asymptotic notations

4. Algorithmic analysis techniques

• Theory: use asymptotic notations

19 20
3. ASYMPTOTIC NOTATION 3. ASYMPTOTIC NOTATION

 Các ký hiệu tiệm cận (asymptotic notation):  Asymptotic notation:

Q, W, O, w Q, W, O, w
• Được sử dụng để mô tả thời gian tính của thuật toán, mô tả tốc độ tăng của thời gian chạy • Used to describe the calculation time of an algorithm, describing the increase in
phụ thuộc vào kích thước dữ liệu đầu vào. runtime depending on the input data size.

• Ví dụ, khi nói thời gian tính của thuật toán cỡ Q (n2), tức là, thời gian tính tỉ lệ thuận với n2 • For example, when saying the computation time isQ(n2), that is, the computation time
cộng thêm các đa thức bậc thấp hơn. is proportional to n2 plus lower order terms.

21 22

3. ASYMPTOTIC NOTATION 3. ASYMPTOTIC NOTATION

3.1. Asymptotic notation theta Q 3.1. Asymptotic notation theta Q

•For a given function g(n), we denote by 𝚯(g(n)) the set of functions:  Example: Prove that 10n2 - 3n = 𝚯(n2)
Q(g(n)) = {f(n): there exists constants c1, c2 and n0 such that: We need to show with which values of the constants n0, c1, c2 then the inequality in the definition of
0  c1g(n)  f(n)  c2g(n), for all n  n0 } the theta notation is correct:
(Set of all functions that have the same rate of growth as g(n)) 𝑐 𝑛 ≤ 𝑓 𝑛 = 10𝑛 − 3𝑛 ≤ 𝑐 𝑛 ∀n ≥ n0
•When we say that one function is theta of another, we mean that neither function goes to infinity Suggestion: Make c1 a little smaller than the leading (the highest) coefficient, and c2 a little bigger.
faster than the other.
 Select: c1 = 1, c2 = 11, n0 = 1 then we have
n2 ≤ 10n2 – 3n ≤ 11n2, for n ≥ 1
 ∀n ≥ 1: 10n2 - 3n = 𝚯(n2)
Note: For polynomial functions: To compare the growth rate, it is necessary to look at the term with
the highest coefficient

23 24
3. ASYMPTOTIC NOTATION 3. ASYMPTOTIC NOTATION
3.2. Asymptotic notation big Oh O 3.2. Asymptotic notation big Oh O
 For a given function g(n), we denote by O(g(n)) the set of functions:  Note: f(n) = 50n3 + 20n + 4 is O(n3)
O(g(n)) = {f(n): there exists positive constants c and n0 such that: Would be correct to say is O(n3+n)
Not useful, as n3 exceeds by far n, for large values
f(n)  cg(n) for all n  n0 }
Would be correct to say is O(n5)
(Set of all functions whose rate of growth is the same as or lower than that of g(n)) OK, but g(n) should be as close as possible to f(n)
 Simple Rule: Drop lower order terms and constant factors
• O(g(n)) is the set of functions that go to infinity no faster than g(n).
 Example: Prove that 2n + 10 = O(n) • Example:
 f(n) = 2n+10, g(n) = n  All these functions are O(n): n, 3n, 61n + 5, 22n – 5, …
• Need to find constants c and n0 such that:  All these functions are O(n2): n2, 9 n2, 18 n2+ 4n – 53, …
2n + 10  cn for all n  n0
 All these functions are O(n log n): n(log n), 5n(log 99n), 18 + (4n – 2)(log (5n + 3)),...
 (c  2) n  10
 n  10/(c  2)
 Select c = 3 and n0 = 10
25 26

3. ASYMPTOTIC NOTATION CONTENTS

3.2. Asymptotic notation Omega Ω

1. Illustrative example
 For a given function g(n), we denote by Ω(g(n)) the set of functions:
W(g(n)) = {f(n): there exists positive constants c and n0 such that: 2. Basic concepts about algorithm
cg(n)  f(n) for all n  n0 }
3. Asymptotic notations
(Set of all functions whose rate of growth is the same as or higher than that of g(n))
4. Algorithmic analysis techniques
 W(g(n)) is the set of functions that go to infinity no slower than g(n)
 Example: Prove that 5n2 = W(n)
Need to find c and n0 such that cn  5n2 for n  n0
Inequality is correct when c = 1 and n0 = 1

27 28
4. ALGORITHMIC ANALYSIS TECHNIQUES 4. ALGORITHMIC ANALYSIS TECHNIQUES

1. Consecutive Statements: The sum of running time of each segment. 4. If/Else

Running time of “P; Q”, where P is implemented first, then Q, is if (condition)
Time(P; Q) = Time(P) + Time(Q) , S1;
or if using asymptotic Theta: else
Time(P; Q) = Q(max(Time(P), Time(Q)). S2;

2. FOR loop: The number of iterations times the time of the inside statements. The testing time plus the larger running time of the S1 and S2.
for i =1 to m do P(i);
Assume running time of P(i) is t(i), then the running time of for loop is ∑ 𝑡(𝑖)

3. Nested loops: The product of the number of iterations times the time of the inside
statements.
for i =1 to n do
for j =1 to m do P(j);
Assume the running time of P(j) is t(j), then the running time of this nested loops is:

29 30

4. ALGORITHMIC ANALYSIS TECHNIQUES 4. ALGORITHMIC ANALYSIS TECHNIQUES

 Example  The characteristic statement is the statement being executed with frequency at least as
well as any statement in the algorithm.
Case1: for (i=0; i<n; i++)
 If the execution time of each statement is bounded above by a constant, then the
for (j=0; j<n; j++) O(n2) running time of the algorithm will be the same size as the number of times the
k++;
execution of the characteristic statement. Thus, in order to evaluate the running time,
Case 2: for (i=0; i<n; i++) one can count the number of times the characteristic statement being executed
k++;  Example 1: Function to calculate Fibonacci numbers f0=0; f1=1; fn= fn-1 + fn-2
O(n2)
for (i=0; i<n; i++)
for (j=0; j<n; j++) function Fibiter(n)
k++; i=0;
j=1; The number of times this characteristic
Case 3: for (int i=0; i<n-1; i++)
for k=1 to n-1 do statement being executed is n
for (int j=0; j<i; j++) O(n2) j = i + j;
int k+=1;  The running time of Fibiter is O(n)
i = j – i;
return j;

31 32
4. ALGORITHMIC ANALYSIS TECHNIQUES 4. ALGORITHMIC ANALYSIS TECHNIQUES

 Example 2: The maximum subarray problem  Example 2: The maximum subarray problem
• Method 1: Brute force • Method 2: Brute force with better implementation

int maxSum = a[0];

for (int i=0; i<n; i++) { int maxSum = a[0];
for (int j=i; j<n; j++) { for (int i=0; i<n; i++) {
int sum = 0;  Select the statement sum+=a[k] as the int sum = 0;  Select the statement sum+=a[k] as the
for (int k=i; k<=j; k++) characteristic statement for (int j=i; j<n; j++) { characteristic statement
sum += a[j];
sum += a[k];  Computation of the algorithm: O(n3)  Computation of the algorithm: O(n2)
if (sum > maxSum) if (sum > maxSum)
maxSum = sum; maxSum = sum;
} }
} }

33 34

4. ALGORITHMIC ANALYSIS TECHNIQUES

SUMMARY AND SUGGESTIONS
 Example 3: Give asymptotic big-Oh notation for the running time T(n) of the following
statement segment: 1. The lesson presented basic concepts of
a)
algorithms and algorithm complexity
int x = 0;
for (int i = 1; i <= n; i *= 2) x=x+1;
2. Following this lesson, learners will learn
b)
int x = 0; about recursion - general diagram and
for (int i = n; i > 0; i /= 2) x=x+1;
some examples

35 36
THANK YOU !

37