APPLIED ALGORITHMS

CONTENTS

• Cumulative array
• 2-pointing technique

APPLIED ALGORITHMS
Data structures and advanced techniques
Cumulative array, 2-pointing technique

3 4
Cumulative array Cumulative array

• Illustrative exercise (P.02.02.01). Given the sequence a1, a2, …, an. Execute Q queries, each query is • Illustrative exercise (P.02.02.01). Given the sequence a1, a2, …, an. Execute Q queries, each query is
characterized by a pair of indices (i, j) in which we need to calculate the sum ai + ai+1 + . . . + aj. characterized by a pair of indices (i, j) in which we need to calculate the sum ai + ai+1 + . . . + aj.
• Direct algorithm: • Algorithm uses cumulative array:
• For each query, we traverse the array from ai to aj to calculate the sum of the elements in this • Calculate the sum of elements in cumulative array Sk = a1 + a2 + … + ak (k = 1, 2, …, n), S0 = 0
subrange. • Complexity O(n)
• The worst-case complexity of each query is O(n). sum(i, j){ • The query (i, j) has the value of Sj - Si-1 Input a1, a2, …, an and Q;

• The worst-case complexity of Q queries is O(Qn). T = 0; • Complexity of each query: O(1) S0 = 0;

for k = 1 to n do
for k = i to j do • Complexity of Q queries: O(n) + O(Q)
Sk = Sk-1 + ak;
T = T + ak ;
return T;
for q = 1 to Q do {
}
Input i, j;
res = Sj – Si-1;
output(res);
}

5 6

Cumulative array Cumulative array

• Given 2D array a[1..n, 1..m], cumulative array S[1..n, 1..m] is defined as following: • Illustrative exercise (P.02.02.02). Given the 2D array a[1..n, 1..m]. Execute Q queries, each query is
• S[0, j] = 0, S[i, 0] = 0, i = 0, 1, …, n and j = 0, 1, . . ., m characterized by a set of indices (a, b, c, d) and defined as follows:
• S[i, j] = ∑ ∑ 𝑎[𝑘, 𝑞], i = 1, …, n and j = 1, . . ., m query[a, b, c, d] = ∑ ∑ 𝑎[𝑘, 𝑞]
• Recursive formula : S[i, j] = S[i-1,j] + S[i, j-1] – S[i-1, j-1] + a[i,j] • Direct algorithm:
• Algorithm to calculate cumulative array • Each query, we perform 2 nested loops to traverse all elements and calculate the sum
• Complexity O(nm) for i = 0 to n do S[i,0] = 0; • The worst-case complexity of each query is O(nm)
for j = 0 to m do S[0,j] = 0;
for i = 1 to n do {
for j = 1 to n do {
S[i,j] = S[i-1,j] + S[i,j-1] –
S[i-1,j-1] + a[i,j];
}
}

7 8
Cumulative array 2-pointing technique

• Illustrative exercise (P.02.02.02). Given the 2D array a[1..n, 1..m]. Execute Q queries, each query is • In many problems, we have to traverse a sequence a1, a2, …, an to search for objects characterized
characterized by a set of indices (a, b, c, d) and defined as follows: by 2 indices (i, j) on the sequence (for example, a subsequence consists of consecutive elements or
pairs of 2 elements of a sequence) that satisfies some certain properties.
query[a, b, c, d] = ∑ ∑ 𝑎[𝑘, 𝑞]
• Use 2 nested loops to traverse through all pairs of 2 indices (i, j): complexity O(n2)
• Algorithm that uses cumulative algorithm: • Use 2 pointers to move in 1 direction or to move in 2 opposite directions: complexity O(n)
• Formular: query[a, b, c, d] = S[c, d] – S[c, b-1] – S[a-1, d] + S[a-1, b-1]
• The worst-case complexity of each query is O(1)

9 10

2-pointing technique 2-pointing technique

• Illustrative exercise 2.1 (P.02.02.03). Given the sequence a[1], a[2], . . ., a[n] is sorted in ascending • Illustrative exercise 2.1 (P.02.02.03). Given the sequence a[1], a[2], . . ., a[n] is sorted in ascending
order (distinct elements: no elements with the same value). Given the value Q, count the number of order (distinct elements: no elements with the same value). Given the value Q, count the number of
pairs of 2 indices i and j such that a[i] + a[j] = Q. pairs of 2 indices i and j such that a[i] + a[j] = Q.

• Direct algorithm res = 0; • Algorithm that uses 2-pointing technique res = 0;

• Use 2 nested loops to browse through all pairs (i, j) for i = 1 to n do { • Variable i moves from left to right and variable j moves i = 1; j = n;
and check the condition a[i] + a[j] = Q for j = i+1 to n do { from right to left through the sequence while i < j do {
• Complexity O(n2) if a[i] + a[j] = Q then • Complexity O(n) if a[i] + a[j] = Q then {
res = res + 1; res = res + 1; i = i + 1; j = j – 1;
} }else if a[i] + a[j] < Q then
} i = i + 1;
Output(res); else
j = j – 1;
}
Output(res);

11 12
2-pointing technique 2-pointing technique

• Illustrative exercise 2.2 (P.02.02.04). Given a sequence of non-negative numbers a[1], a[2], . . ., a[n]. • Illustrative exercise 2.2 (P.02.02.04). Given a sequence of non-negative numbers a[1], a[2], . . ., a[n].
Given the value Q, find the longest subsequence (consisting of a number of consecutive elements: Given the value Q, find the longest subsequence (consisting of a number of consecutive elements:
a[i], a[i+1],…,a[j]) whose sum is less than or equal to Q. a[i], a[i+1],…,a[j]) whose sum is less than or equal to Q.

• Direct algorithm res = 0; • Algorithm that uses 2-pointing technique res = 0; S = 0;

• Use 2 nested loops to consider all starting and ending for i = 1 to n do { • Variable L moves from left to right and variable R L = 1;
positions of a subsequence and check whether the S = 0; moves from right to left through the sequence for R = 1 to n do {
sum is less than or equal to Q? for j = i to n do { • Complexity O(n) S = S + a[R];
• Complexity O(n2) S = S + a[j]; while S > Q do {
if S <= Q then { S = S – a[L]; L = L + 1;
res = max(res, j – i + 1); }
} res = max(res, R – L + 1);
} }
} Output(res);
Output(res);

13 14

THANK YOU !

15