# Condensed DSA course with C++ - Code transcripts
###### tags: `C++` `DSA`
Author: [thucngch](http://fb.com/thucngch)
# Session 1 - 2020 Sep 17, 20:30
- Primality check
- Prime generation techniques
## Code
```cpp=
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
typedef vector<int> vi_t;
bool is_prime(int n) {
if (n < 2) return false;
for (int d = 2; d <= sqrt(n); d++) {
if (n % d == 0) return false;
}
return true;
}
vi_t primes(int n) {
vi_t p;
for (int i=2; i <= n; i++) {
if (is_prime(i)) p.push_back(i);
}
return p;
}
vi_t primes_sieve(int n) {
vi_t p;
int check[n+1];
for (int i=0; i<n+1; i++) check[i] = 1;
check[0] = check[1] = 0;
for (int d = 2; d <= sqrt(n); d++) {
if (check[d]) {
for (int k = d*d; k < n+1; k += d) {
check[k] = 0;
}
}
}
for (int i=2; i <= n; i++) {
if (check[i]) p.push_back(i);
}
return p;
}
int main() {
int m;
cin >> m;
// cout << "Is Prime: " << is_prime(m);
cout << "All prime not greater than " << m << ":" << endl;
vi_t p = primes_sieve(m);
// for (int i=0; i < p.size(); i++) {
// cout << p[i] << " ";
// }
cout << endl << "Total: " << p.size() << " primes!";
}
```
## Problems
See in Google Drive docs.
# Session 2 - 2020 Sep 20, 10:00
- File I/O
- GCD / LCM
- Modulos
- Logarithmic Exponentiation
- Integer Factorization
- Number of combinations
- Fibonacci, fast n-th fibonacci calculation
## File input / output
```cpp=
#include <iostream>
#include <fstream>
using namespace std;
int main() {
ifstream fi;
fi.open("fileio.inp");
ofstream fo;
fo.open("fileio.out");
int a, b;
fi >> a >> b;
string s;
fi.ignore(); // skip to next line
getline(fi, s);
fo << a + b << endl;
fo << "Hello " << s << endl;
fi.close();
fo.close();
}
```
## Math
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MOD = 1000000007;
//(a + b) % p === a%p + b%p
//(a - b) % p === a%p - b%p
//(a * b) % p === a%p * b%p
//(a / b) % p === a%p / b%p --> NOT TRUE
int pow1(int a, int n) {
int p = 1;
for (int i = 0; i < n; i ++) {
p = (p*a) % MOD;
}
return p;
}
int pow2(int a, int n) {
if (n==0) return 1;
long long b = pow2(a, n/2);
long long p = (b*b) % MOD;
if (n%2) p = (p*a) % MOD;
return int(p);
}
int fibo1(int n) {
int f1 = 0, f2 = 1;
for (int i = 0; i < n; i++) {
int tmp = f1;
f1 = f2;
f2 = (tmp + f2) % MOD;
}
return f1;
}
int fibo2(int n) {
// fibo2(n) <-- fibo2(n/2)
}
vector<int> factorization(int n) {
// TODO: 12 = 2 2 3 --> 2^2 x 3
vector<int> v;
int p = 2;
while (n >= p*p) {
while (n % p == 0) {
v.push_back(p);
n /= p;
}
p += 1;
}
if (n>1) v.push_back(n);
return v;
}
int gcd(int m, int n) {
return __gcd(m, n);
}
int lcm(int m, int n) {
return m * n / gcd(m, n);
}
int combination(int n, int k) {
// F1. C(n, k) = n * (n-1) * (n-2) * ... (n-k+1) / k!
// F2. C(n, k) = n! / (k! * (n-k)!)
// F3. C(n,k) = C(n-1, k) + C(n-1, k-1) --> Pascal's triangle
// 1
// 1 1
// 1 2 1
// 1 3 3 1
// 1 4 6 4 1
// 1 5 10 10 5 1
}
int main() {
// int a, n;
// cin >> a >> n;
// cout << pow2(a, n);
// int n;
// cin >> n;
// vector<int> f = factorization(n);
// for (int i = 0; i < f.size(); i++) {
// cout << f[i] << " ";
// }
int a, b;
cin >> a >> b;
cout << gcd(a, b) << " " << lcm(a, b);
}
```
# Session 3 - 2020 Sep 24, 19:30
- Array
- Vector
- Sliding windows
```cpp
// nhap vao 1 mang so nguyen
// 1. Tim so lon nhat
// 2. So luong so lon nhat
// 3. Chi so cua so lon nhat dau tien va cuoi cung
#include <iostream>
#include <fstream>
using namespace std;
int main() {
int n;
ifstream cin("array.INP");
cin >> n;
int a[n];
for (int i=0; i<n; i++) cin >> a[i];
int vmax = a[0], imax1 = 0, imax2 = 0, cmax = 1;
for (int i=0; i<n; i++) {
if (a[i] > vmax) {
vmax = a[i];
cmax = 1;
imax1 = i;
} else if (a[i] == vmax) {
cmax += 1;
imax2 = i;
}
}
cout << vmax << " " << cmax << " " << imax1 << " " << imax2;
cin.close();
}
```
```cpp
// nhap vao mot mang a gom n so nguyen, va so k <= n
// tim gia tri lon nhat cua tong k so lien tiep trong mang a.
#include <iostream>
#include <fstream>
using namespace std;
int main() {
int n, k;
ifstream cin("sliding_windows.INP");
cin >> n >> k;
int a[n];
for (int i=0; i<n; i++) cin >> a[i];
int sum_k = 0, max_sum;
for (int i=0; i<k; i++) sum_k += a[i];
max_sum = sum_k;
for (int i=1; i<=n-k; i++) {
sum_k = sum_k - a[i-1] + a[i+k-1];
if (sum_k > max_sum) max_sum = sum_k;
}
cout << max_sum;
cin.close();
}
```
```cpp
// nhap vao 1 ma tran, in ra ma tran chuyen vi (doi dong thanh cot)
#include <iostream>
#include <fstream>
using namespace std;
int main() {
int n, m;
ifstream cin("matrix.INP");
cin >> n >> m;
int a[n][m];
int b[m][n];
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
cin >> a[i][j];
b[j][i] = a[i][j];
}
}
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
cout << b[i][j] << " ";
}
cout << endl;
}
cin.close();
}
```
```cpp
// nhap vao 1 so n, in ra ma tran nxn so theo chieu xoan oc, vi du:
// 1 2 3 4
// 12 13 14 5
// 11 16 15 6
// 10 9 8 7
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
int n;
cin >> n;
int a[n][n];
int i = 0, j = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
a[i][j] = 0;
}
}
int di[4] = {0, 1, 0, -1};
int dj[4] = {1, 0, -1, 0};
int dir = 0;
for (int d=1; d<=n*n; d++) {
a[i][j] = d;
int i_new = i + di[dir];
int j_new = j + dj[dir];
if (i_new<0 || i_new>=n || j_new<0 || j_new>=n || a[i_new][j_new]>0) {
dir = (dir + 1) % 4;
i_new = i + di[dir];
j_new = j + dj[dir];
}
i = i_new;
j = j_new;
}
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
cout << setfill('0') << setw(2) << a[i][j] << " ";
}
cout << endl;
}
}
```
# Session 4 - 2020 Sep 27, 10:00
- Balanced parentheses
- Large integer computation
- Word processing
```cpp
// Kiem tra day ngoac tron hop le
#include "iostream"
using namespace std;
int main() {
string s;
cin >> s;
int balance = 0;
for (char c: s) {
if (c=='(') balance += 1;
else balance -= 1;
if (balance < 0) { cout << "NOK"; return 0;}
}
if (balance == 0) cout << "OK";
else cout << "NOK";
}
```
```cpp
// kiem tra day ngoac nhieu loai co hop le khong
// using string as a stack
#include "iostream"
using namespace std;
int main() {
string brackets;
cin >> brackets;
string s = ""; // stack
for (char c: brackets) {
if (c=='(' || c=='[' || c=='{' ) s += c;
else {
int n = s.size();
if (n == 0) { cout << "NOK"; return 0;}
char ch = s[n-1];
if ((c==')' && ch != '(') || (c==']' && ch != '[')
|| (c=='}' && ch != '{')) {
cout << "NOK"; return 0;
} else {
s = s.substr(0, n-1);
}
}
}
if (s.size() == 0) cout << "OK";
else cout << "NOK";
}
```
```cpp
// kiem tra day ngoac nhieu loai co hop le khong
// using STL stack
#include "iostream"
#include "stack"
using namespace std;
int main() {
string brackets;
cin >> brackets;
stack<char> s;
for (char c: brackets) {
if (c=='(' || c=='[' || c=='{' ) s.push(c);
else {
if (s.empty()) { cout << "NOK"; return 0;}
char ch = s.top();
if ((c==')' && ch != '(') || (c==']' && ch != '[')
|| (c=='}' && ch != '{')) {
cout << "NOK"; return 0;
}
s.pop();
}
}
if (s.empty()) cout << "OK";
else cout << "NOK";
}
```
```cpp
// cong 2 so lon
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
string s1, s2, s = "";
cin >> s1 >> s2;
if (s1.size() > s2.size()) swap(s1, s2);
reverse(s1.begin(), s1.end());
reverse(s2.begin(), s2.end());
int n = s2.size() - s1.size();
for (int i=0; i<n; i++) s1 += '0';
int carry = 0;
for (int i=0; i<s1.size(); i++) {
int sum= s1[i]-'0' + s2[i]-'0' + carry;
s += sum%10 + '0';
carry = sum / 10;
}
if (carry>0) s += carry + '0';
reverse(s.begin(), s.end());
cout << s;
}
```
```cpp
// word processing
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
int word_count(string s){
s = " " + s;
int count = 0;
for (int i=0; i<s.size()-1; i++) {
if (s[i] == ' ' && s[i+1]!=' ') count += 1;
}
return count;
}
vector<string> word_split(string s){
vector<string> res;
istringstream ss(s);
do {
string word;
ss >> word;
if (word.size() > 0) res.push_back(word);
} while (ss);
return res;
}
int main() {
string s;
getline(cin, s);
cout << word_count(s) << endl;
vector<string> words = word_split(s);
for (int i=0; i<words.size(); i++)
cout << "`" << words[i] << "`" << endl;
}
```
# Session 5 - 2020 Oct 04, 10:00
```cpp
#include <iostream>
using namespace std;
// max(a[1..n])
// = (max(a[1..n-1]), a[n])
// max(a[1..1]) = a[1]
int max1(int a[], int n) { // recursive
if (n==1) return a[0];
int vmax = max1(a, n-1);
if (vmax > a[n-1]) return vmax;
return a[n-1];
}
// max1([5 9 7 2 1 8])
// max1([5 9 7 2 1]) vs 8
// (max1([5 9 7 2]) vs 1) vs 8
// ...
// (max1([5]) vs 9) vs ... vs 8
// 5 vs 9 vs ... vs 8
int max2(int a[], int n) { // dp
int vmax = a[0];
for (int i=1; i < n; i++)
if (a[i] > vmax) vmax=a[i];
return vmax;
}
int main() {
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
cin >> a[i];
cout << max1(a, n) << endl;
cout << max2(a, n) << endl;
return 0;
}
```
```cpp
#include <iostream>
using namespace std;
// fibo(n) = fibo(n-1) + fibo[n-2]
// fibo(0) = fibo(1) = 1
int fibo1(int n) { // recursive: top-down
if (n<2) return 1;
return fibo1(n-1) + fibo1(n-2);
}
int fibo2(int n) { // dp: bottom-top
int a[n+1];
a[0] = a[1] = 1;
for (int i=2; i <= n; i++)
a[i] = a[i-1] + a[i-2];
return a[n];
}
int main() {
int n;
cin >> n;
cout << fibo1(n) << endl;
cout << fibo2(n) << endl;
return 0;
}
```
```cpp
#include <iostream>
#include <vector>
using namespace std;
// Longest Increasing Subsequence
int main() {
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
cin >> a[i];
int lis[n];
lis[0] = 1;
int p[n]; // tracing array, store index of previous item in current LIS
p[0] = -1;
for (int i = 1; i < n; i++) {
int Lmax = 1, imax = -1;
for (int j = 0; j<i; j++) {
if (a[j] < a[i] && lis[j]+1>Lmax) {
Lmax = lis[j] + 1;
imax = j;
}
}
lis[i] = Lmax;
p[i] = imax;
}
int vmax = lis[0], imax = 0;
for (int i = 0; i < n; i++) {
cout << lis[i] << " ";
if (vmax < lis[i]) {
vmax = lis[i];
imax = i;
}
}
cout << endl << vmax << endl;
for (int i = 0; i < n; i++) {
cout << p[i] << " ";
}
vector<int> res;
while (imax > -1) {
res.push_back(a[imax]);
imax = p[imax];
}
cout << endl;
for (int i = res.size()-1; i >= 0; i--) {
cout << res[i] << " ";
}
return 0;
}
```
# Session 6 - 2020 Oct 08, 19:30
```cpp=
// https://practice.geeksforgeeks.org/problems/longest-common-subsequence/0
#include <iostream>
#include <algorithm>
using namespace std;
int lcs(string s1, string s2, int n, int m) {
if (n == 0 || m == 0) return 0;
if (s1[n-1] == s2[m-1])
return 1 + lcs(s1, s2, n-1, m-1);
int l1 = lcs(s1, s2, n-1, m);
int l2 = lcs(s1, s2, n, m-1);
return max(l1, l2);
}
int lcs2(string s1, string s2, int n, int m) {
int dp[n+1][m+1]; // dp[i][j] = LCS(s1, s2, i, j)
for (int i = 0; i<=n; i++)
for (int j = 0; j<=m; j++) {
if (i == 0 || j==0) dp[i][j] = 0;
else if (s1[i-1] == s2[j-1]) {
dp[i][j] = 1 + dp[i-1][j-1];
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[n][m];
}
int main() {
int T;
cin >> T;
string s1, s2;
for (int i=0; i<T; i++) {
int n, m;
cin >> n >> m;
cin >> s1;
cin >> s2;
// cout << s1 << endl << s2 << endl;
cout << lcs2(s1, s2, n, m) << endl;
}
}
```
```cpp=
// https://practice.geeksforgeeks.org/problems/edit-distance3702/1
#include <iostream>
#include <algorithm>
using namespace std;
int ed(string s, string t, int n, int m) {
if (n==0) return m;
if (m==0) return n;
if (s[n-1] == t[m-1]) return ed(s, t, n-1, m-1);
return 1 + min(min(ed(s, t, n, m-1), ed(s, t, n-1, m)),
ed(s, t, n-1, m-1));
}
int ed2(string s, string t, int n, int m) {
int dp[n+1][m+1];
for (int i = 0; i<= n; i++)
for (int j = 0; j<= m; j++) {
if (i==0) dp[i][j] = j;
else if (j==0) dp[i][j] = i;
else if (s[i-1]==t[j-1]) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = 1 + min(min(dp[i][j-1], dp[i-1][j]),
dp[i-1][j-1]);
}
return dp[n][m];
}
int main() {
string s, t;
cin >> s;
cin >> t;
cout << ed2(s, t, s.size(), t.size());
}
```
Sign in with Wallet
Connect another wallet