APPLIED ALGORITHMS
CONTENTS
• Introduction
• Standard Template Library (STL) in C++
APPLIED ALGORITHMS
General introduction
Data structure library
3 4
INTRODUCTION INTRODUCTION
• Objective of the subject • Subjects
• Study some advanced data structures and algorithms • Backtracking, branching and bounding
• Apply effective algorithms and data structures to solve complex computational problems • Data structures: stack, queue, set, disjoint set (các tập rời nhau), priority queue (hàng đợi ưu
• Analyze the effectiveness of the algorithm tiên), segment tree (câu phân đoạn)
• Practice algorithmic programming skills • Cumulative array technique (kỹ thuật mảng cộng dồn), 2 pointer technique, bit representation
and processing
• Practice
• Greedy algorithm, divide and conquer, dynamic programming
• Programming to solve applied computational problems
• Algorithms on graphs: DFS, BFS, Strongly Connected Components, Shortest Path, Minimum
• Submit source code to the automatic scoring system through test cases Spanning Tree, Max-Flow, Max-Matching
• Each exercise will be described in detail about the problem statement, format of input data • Geometric algorithm (Thuật toán hình học)
and output results
• String processing algorithm (Thuật toán xử lý xâu)
5 6
INTRODUCTION - Example (P.01.01.01) INTRODUCTION - Example (P.01.01.01)
• Given 2 integers a and b, calculate sum of them. • Given 2 integers a and b, calculate sum of them.
• Data • Data
• Line 1 consists of 2 integers a and b (0 <= a, b <= 1019) • One line consists of 2 integers a and b (0 <= a, b <= 1019)
• Result • Result
• Write a number which is them sum of a and b • Write a number which is them sum of a and b
#include <bits/stdc++.h>
using namespace std;
Stdin Stdout
int main(){
35 8
int a,b;
cin >> a >> b;
int res = a + b;
cout << res;
return 0;
}
7 8
INTRODUCTION - Example (P.01.01.01) INTRODUCTION - Example (P.01.01.01)
• Given 2 integers a and b, calculate sum of them. • Given 2 integers a and b, calculate sum of them.
• Data • Data
• One line consists of 2 integers a and b (0 <= a, b <= 1019) • One line consists of 2 integers a and b (0 <= a, b <= 1019)
• Result • Result
• Write a number which is them sum of a and b • Write a number which is them sum of a and b
#include <bits/stdc++.h> #include <bits/stdc++.h>
using namespace std; using namespace std;
int main(){ int main(){
int a,b; unsigned long long a,b;
cin >> a >> b; cin >> a >> b;
int res = a + b; unsigned long long res = a + b;
cout << res;
Overflow when a and cout << res;
return 0;
b are large numbers return 0;
} }
9 10
INTRODUCTION - Example (P.01.01.01) INTRODUCTION - Example (P.01.01.01)
• Given 2 integers a and b, calculate sum of them. • Given 2 integers a and b, calculate sum of them.
• Data • Data
• One line consists of 2 integers a and b (0 <= a, b <= 1019) • One line consists of 2 integers a and b (0 <= a, b <= 1019)
#include <bits/stdc++.h>
• Result • Result
using namespace std;
• Write a number which is them sum of a and b • Write a number which is them sum of a and b
int main(){
#include <bits/stdc++.h> unsigned long long a,b, a1, b1,a2,b2;
using namespace std; cin >> a >> b;
int main(){ a1=a/10; b1=b/10;
unsigned long long a,b; a2 = a%10; b2 = b%10;
cin >> a >> b; unsigned long long c1 = a1+b1+(a2+b2)/10;
a = 10000000000000000000, b = 10000000000000000000 unsigned long long res = a + b; unsigned long long c2 = (a2+b2)%10;
res = 1553255926290448384 (still overflow)
cout << res; if (c1 > 0) cout << c1 << c2;
return 0; else cout << c2;
}
SOLVED!!
return 0;
}
11 12
Standard Template Library (STL) in C++ Standard Template Library (STL) in C++
• Standard Template Library (STL) in C++ • Dynamic array
• Vector, List • Linear array
• String • Operations: access, add, remove elements
• Stack, Queue #include <bits/stdc++.h> 1 2 3 4 5 6 7 8 9 10
• Set using namespace std; 4 5 6 7 8 9 10
• Map int main() {
• Priority queue vector<int> V;
V.push_back(1); V.push_back(2);
for(int i = 3; i <= 10; i++) V.push_back(i);
for(int i = 0; i < [Link](); i++) cout << V[i] << " ";
cout << endl;
[Link]([Link](), [Link]() + 3);
for(int i = 0; i < [Link](); i++) cout << V[i] << " ";
cout << endl;
}
13 14
Standard Template Library (STL) in C++ - List Standard Template Library (STL) in C++ - List
• Doubly linked list • Doubly linked list
• Linear data structure • Linear data structure
• Operations: add elements to the beginning, the end, after a position, remove an element from • Operations: add elements to the beginning, the end, after a position, remove an element from
the list the list
#include <bits/stdc++.h> 1 2 6 6 3 4 5 #include <bits/stdc++.h> item at position p is 3
using namespace std; using namespace std; 1 2 4 5
int main() { int main() {
list<int> L; list<int> L;
for(int v = 1; v <= 5; v++) L.push_back(v); for(int v = 1; v <= 5; v++) L.push_back(v);
list<int>::iterator p; list<int>::iterator p;
p = [Link](); p = [Link](); advance(p,2);
advance(p,2); cout << "item at position p is " << *p << endl;
[Link](p,2,6);//insert 2 occurrences of 6 after position p [Link](p);//remove the item at position p
for(p = [Link](); p!= [Link](); p++) cout << *p << " "; for(p = [Link](); p!= [Link](); p++) cout << *p << " ";
} }
15 16
Standard Template Library (STL) in C++ - String Standard Template Library (STL) in C++ - Stack
• Represents a string of characters • Linear data structure
• Operations: assign, concatenate strings, replace substrings, extract substrings, etc. • Operations: Add and remove elements with the Last In First Out (LIFO) principle
#include <bits/stdc++.h> s1 = hello, s2 = hello world #include <bits/stdc++.h> PUSH 1
using namespace std; s2 = hello world, length = 11 using namespace std; PUSH 2
int main() { [Link](2,6) = llo wo int main() { PUSH 3
string s1 = "hello"; new s2 = hello abc stack<int> S; PUSH 4
string s2 = s1 + " world"; for(int i = 1; i <= 5; i++){ PUSH 5
cout << "s1 = " << s1 << ", s2 = " << s2 << endl; [Link](i); cout << "PUSH " << i << endl; POP 5
string ss = [Link](2,6); } POP 4
cout << "s2 = " << s2 << ", length = " << [Link]() << endl; while(![Link]()){ POP 3
cout << "[Link](2,6) = " << ss << endl; int e = [Link](); [Link](); cout << "POP " << e << endl; POP 2
[Link](6, 5, "abc"); } POP 1
cout << "new s2 = " << s2 << endl; }
}
17 18
Standard Template Library (STL) in C++ - Queue Standard Template Library (STL) in C++ - Set
• Linear data structure • Store elements without repeating values
• Operations: Add and remove elements with the First In First Out (FIFO) principle • Operations: add, remove, search
#include <bits/stdc++.h> Queue push 1 #include <bits/stdc++.h> abc def xyz
using namespace std; Queue push 2 using namespace std;
int main() { Queue push 3 int main() {
queue<int> Q; Queue push 4 set<string> S;
for(int e = 1; e <= 5; e++){ Queue push 5 [Link]("abc"); [Link]("def"); [Link]("xyz");
[Link](e); cout << "Queue push " << e << endl; Queue POP 1 [Link]("abc");
} Queue POP 2
while(![Link]()){ Queue POP 3 set<string>::iterator p;
int e = [Link](); [Link](); cout << "Queue POP " << e << endl; Queue POP 4 for(p = [Link](); p != [Link](); p++) cout << *p << " ";
} Queue POP 5 cout << endl;
} }
19 20
Standard Template Library (STL) in C++ - Set Standard Template Library (STL) in C++ - Set
• Store elements without repeating values • Store elements without repeating values
• Operations: add, remove, search • Operations: add, remove, search
#include <bits/stdc++.h> xau def exists in S #include <bits/stdc++.h> abc def
using namespace std; using namespace std;
int main() { int main() {
set<string> S; set<string> S;
[Link]("abc"); [Link]("def"); [Link]("xyz"); [Link]("abc"); [Link]("def"); [Link]("xyz");
string s1 = "def"; string s1 = "xyz";
set<string>::iterator p = [Link](s1); [Link](s1);
if(p == [Link]()) set<string>::iterator p;
cout << "xau " << s1 << " does not exist" << endl; for(p = [Link](); p != [Link](); p++) cout << *p << " ";
else cout << endl;
cout << "xau " << s1 << " exists in S" << endl; }
}
21 22
Standard Template Library (STL) in C++ - Set Standard Template Library (STL) in C++ - Set
• The set structure in C++ provides the function upper_bound(k): returns a pointer to the smallest • The set structure in C++ provides the function upper_bound(k): returns a pointer to the smallest
element that is greater than k in the set. If k is greater than or equal to the largest element, the element that is greater than k in the set. If k is greater than or equal to the largest element, the
function returns a pointer to the position after the last element of the set function returns a pointer to the position after the last element of the set
#include <bits/stdc++.h>
#include <bits/stdc++.h> upper_bound(3) = 4 lower_bound(3) = 4
using namespace std;
using namespace std; upper_bound(4) = 6 lower_bound(4) = 4
int main() {
int main() { no upper_bound of 10 no lower_bound of 11
set<int> S;
set<int> S;
for(int v = 1; v <= 5; v++) [Link](2*v);
for(int v = 1; v <= 5; v++) [Link](2*v); set<int>::iterator p = S.lower_bound(3);
set<int>::iterator p = S.upper_bound(3); cout << "lower_bound(3) = " << *p << endl;
cout << "upper_bound(3) = " << *p << endl; p = S.lower_bound(4);
p = S.upper_bound(4); cout << "lower_bound(4) = " << *p << endl;
cout << "upper_bound(4) = " << *p << endl; p = S.lower_bound(11);
p = S.upper_bound(10); if(p == [Link]()) cout << "no lower_bound of 11" << endl;
if(p == [Link]()) cout << "no upper_bound of 10" << endl; else cout << "lower_bound of 11 = " << *p << endl;
} }
23 24
Standard Template Library (STL) in C++ - Map Standard Template Library (STL) in C++ - Priority Queue
• A data structure that stores pairs of (key, value) • Store elements, retrieve the element with the largest/smallest key efficiently
• Operation: add a pair of (key, value); query the value corresponding to a given key. #include <bits/stdc++.h>
#include <bits/stdc++.h> value of key abc = 1 #define pii pair<int,int> pq pop 100
using namespace std; xyzt is mapped to value 10 using namespace std; pq pop 30
int main() { abc is mapped to value 1 int main() { pq pop 5
map<string, int> M; def is mapped to value 2 priority_queue<int> pq; pq pop 1
M["abc"] = 1; M["def"] = 2; M["xyzt"] = 10; value of 1234 = 0 [Link](5); [Link](1); [Link](100); [Link](30);
string k = "abc"; while(![Link]()){
cout << "value of key " << k << " = " << M[k] << endl; int e = [Link](); [Link]();
for(map<string,int>::iterator p = [Link](); p != [Link](); p++) cout << "pq pop " << e << endl;
cout << p->first << " is mapped to value " << p->second << endl; }
string k1 = "1234"; }
cout << "value of " << k1 << " = " << M[k1] << endl;
}
25 26
Standard Template Library (STL) in C++ - Priority Queue Standard Template Library (STL) in C++ - Priority Queue
• Store elements, retrieve the element with the largest/smallest key efficiently • Store elements, retrieve the element with the largest/smallest key efficiently
#include <bits/stdc++.h> #include <bits/stdc++.h>
#define pii pair<int,int> PQ pop (9,-900) #define pii pair<int,int> PQ pop (1,-10)
using namespace std; PQ pop (4,-40) using namespace std; PQ pop (4,-40)
int main() { PQ pop (1,-10) int main() { PQ pop (9,-900)
priority_queue<pii> PQ; priority_queue<pii, vector<pii>, greater<pii> > PQ;
[Link](make_pair(4,-40)); [Link](make_pair(4,-40));
[Link](make_pair(1,-10)); [Link](make_pair(1,-10));
[Link](make_pair(9,-900)); [Link](make_pair(9,-900));
while(![Link]()){ while(![Link]()){
pii e = [Link](); [Link](); pii e = [Link](); [Link]();
cout << "PQ pop (" << [Link] << "," << [Link] << ")" << endl; cout << "PQ pop (" << [Link] << "," << [Link] << ")" << endl;
} }
} }
27 28
THANK YOU !
29