---
# System prepended metadata

title: Condensed DSA course with C++ - Code transcripts
tags: [C++, DSA]

---

# 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());
}
```