ubuntu C++ configurations

build-essential : tools and libraries that are required to compile a program. For example, if you need to work on a C/C++ compiler, you need to install essential meta-packages on your system before starting the C compiler installation. When installing the build-essential packages, some other packages such as G++, dpkg-dev, GCC and make, etc. also install on your system.

Cmake + Ninja

GDB: The GNU Project Debugger

then for Qt and vcpkg

Besides build-essential and cmake you need to install git

for vcpkg

sudo apt-get install curl zip unzip tar
sudo apt-get install pkg-config
apt install gperf
sudo apt-get install bison
sudo apt install git
sudo apt install autopoint  
sudo apt install gettext
sudo apt install libtool 

for Qt

sudo apt-get install mesa-common-dev
sudo apt install libglu1-mesa-dev -y
sudo apt-get install libglfw3-dev libgl1-mesa-dev libglu1-mesa-dev
sudo apt install libfontconfig1-dev libfreetype6-dev libx11-dev libx11-xcb-dev libxext-dev libxfixes-dev libxi-dev libxrender-dev libxcb1-dev libxcb-glx0-dev libxcb-keysyms1-dev libxcb-image0-dev libxcb-shm0-dev libxcb-icccm4-dev libxcb-sync-dev libxcb-xfixes0-dev libxcb-shape0-dev libxcb-randr0-dev libxcb-render-util0-dev libxcb-util-dev libxcb-xinerama0-dev libxcb-xkb-dev libxkbcommon-dev libxkbcommon-x11-dev

Conic Sections

Common Parts of Conic Sections

A focus is a point about which the conic section is constructed. In other words, it is a point about which rays reflected from the curve converge. A parabola has one focus about which the shape is constructed; an ellipse and hyperbola have two.

A directrix is a line used to construct and define a conic section. The distance of a directrix from a point on the conic section has a constant ratio to the distance from that point to the focus. As with the focus, a parabola has one directrix, while ellipses and hyperbolas have two.

Eccentricity

  • 0 < eccentricity < 1 we get an ellipse,
  • eccentricity = 1 a parabola, and
  • eccentricity > 1 a hyperbola.

A circle has an eccentricity of zero, so the eccentricity shows us how “un-circular” the curve is. The bigger the eccentricity, the less curved it is.

Porabolla

A parabola is a curve where any point is at an equal distance from:

  • a fixed point (the focus ), and
  • a fixed straight line (the directrix )

Ellipse

“F” is a focus, “G” is a focus,and together they are called foci (pronounced “fo-sigh”).
The total distance from F to P to G stays the same
Well f+g is equal to the length of the major axis.

Hyperbola

A hyperbola is two curves that are like infinite bows.
Looking at just one of the curves:
any point P is closer to F than to G by some constant amount
The other curve is a mirror image, and is closer to G than to F.

  • an axis of symmetry (that goes through each focus)
  • two vertices (where each curve makes its sharpest turn)
  • the distance between the vertices (2a on the diagram) is the constant difference between the lengths PF and PG
  • two asymptotes which are not part of the hyperbola but show where the curve would go if continued indefinitely in each of the four directions

Hyperbolic functions

Catenary (hanging cable)

Math Problems 1

Problem 1

what is the area of the rectangle?
the minimum area of the triangle satisfied these conditions?

part 1

so the area of a rectangle is

xy=12

part 2

Problem 2

find the radius of biggest circuit

take first two circuits
hypotenuse of both are collinear

Problem 3

a cable of 80 meters hanging from the top of two poles there are two 50 meters from the ground
what is the distance from two poles if center of cable 20 meters above the ground ?

Problem 4

find the area of the red segments

C++ Useful Libraries

random standard c++ library

#include<random>
std::default_random_engine generator;
std::uniform_int_distribution<int> distribution(1,6);
int dice_roll = distribution(generator);  //between [1,6]
#include<random>
std::default_random_engine generator;
std::uniform_real_distribution<double> distribution(0.0,2.0);
double random = distribution(generator);//between [0.0,2.0)

simd library( single instruction multiple data)

C++ wrappers for SIMD intrinsics and parallelized, optimized mathematical functions (SSE, AVX, NEON, AVX512)

#include <iostream>
#include "xsimd/xsimd.hpp"

namespace xs = xsimd;

int main(int argc, char* argv[])
{
    xs::batch<double, xs::avx2> a(1.5, 2.5, 3.5, 4.5);
    xs::batch<double, xs::avx2> b(2.5, 3.5, 4.5, 5.5);
    auto mean = (a + b) / 2;
    std::cout << mean << std::endl;
    return 0;
}
#include <cstddef>
#include <vector>
#include "xsimd/xsimd.hpp"

namespace xs = xsimd;
using vector_type = std::vector<double, xsimd::aligned_allocator<double>>;

void mean(const vector_type& a, const vector_type& b, vector_type& res)
{
    std::size_t size = a.size();
    constexpr std::size_t simd_size = xsimd::simd_type<double>::size;
    std::size_t vec_size = size - size % simd_size;

    for(std::size_t i = 0; i < vec_size; i += simd_size)
    {
        auto ba = xs::load_aligned(&a[i]);
        auto bb = xs::load_aligned(&b[i]);
        auto bres = (ba + bb) / 2.;
        bres.store_aligned(&res[i]);
    }
    for(std::size_t i = vec_size; i < size; ++i)
    {
        res[i] = (a[i] + b[i]) / 2.;
    }
}
#include <cstddef>
#include <vector>
#include "xsimd/xsimd.hpp"
#include "xsimd/stl/algorithms.hpp"

namespace xs = xsimd;
using vector_type = std::vector<double, xsimd::aligned_allocator<double>>;

void mean(const vector_type& a, const vector_type& b, vector_type& res)
{
    xsimd::transform(a.begin(), a.end(), b.begin(), res.begin(),
                     [](const auto& x, const auto& y) { (x + y) / 2.; });
}

dlfcn Lybrary

Tree Traversals

Depth-First Search and Breadth-First Search

class Node{
    int value;
    Node *parent;
    std::vector<Node*> childs;
public:
    Node(int v):value(v){

    }
    void AppendChild(Node* n){
        n->parent=this;
        childs.push_back(n);
    }
    void RemoveChild(Node* n){
        n->parent=nullptr;
        this->childs.erase(std::find(childs.begin(),childs.end(),n));
    }
    void AppendChilds(std::initializer_list<Node*> childs){
        for(Node* n:childs)
            this->AppendChild(n);
    }
    std::vector<Node*> GetChildren(){
        return childs;
    }
    Node* GetParent(){
        return parent;
    }
    Node* GetRoot(){
        Node* root=this;
        while(root->GetParent())
            root=parent->GetParent();
        return root;
    }
    operator int(){
        return value;
    }
};

void DFS(Node* root){
    qDebug()<<*root;
    std::vector<Node*> nodes=root->GetChildren();
    for(Node* n:nodes)
        DFS(n);
}

void BFS(Node* root){
    std::queue<Node*> nodes;
    nodes.push(root);
    while(nodes.size()>0){
        Node* current=nodes.front();
        nodes.pop();
        qDebug()<<*current;
        for(Node* n : current->GetChildren())
            nodes.push(n);
    }
}

int main(int argc, char *argv[])
{
    QGuiApplication a(argc, argv);
    Node n1=1,n2=2,n3=3,n4=4,n5=5,n6=6,n7=7,n8=8,n9=9,n10=10,n11=11,n12=12,n13=13,n14=14,n15=15,n16=16,n17=17,n18=18,n19=19;
    n1.AppendChilds({&n2,&n3});
    n2.AppendChilds({&n4,&n5});
    n3.AppendChilds({&n6,&n7});
    n4.AppendChilds({&n8,&n9});
    n5.AppendChilds({&n10,&n11});
    n6.AppendChilds({&n12,&n13});
    n7.AppendChilds({&n14,&n15});
    n8.AppendChilds({&n16,&n17});
    n9.AppendChilds({&n18,&n19});
    BFS(&n1);

    return a.exec();
}

Binary Tree Traversals

struct Node {
    int data;
    struct Node *left, *right;
    Node(int data)
    {
        this->data = data;
        left = right = NULL;
    }
};
 
/* Given a binary tree, print its nodes according to the
"bottom-up" postorder traversal. */
void printPostorder(struct Node* node)
{
    if (node == NULL)
        return;
 
    // first recur on left subtree
    printPostorder(node->left);
 
    // then recur on right subtree
    printPostorder(node->right);
 
    // now deal with the node
    cout << node->data << " ";
}
 
/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct Node* node)
{
    if (node == NULL)
        return;
 
    /* first recur on left child */
    printInorder(node->left);
 
    /* then print the data of node */
    cout << node->data << " ";
 
    /* now recur on right child */
    printInorder(node->right);
}
 
/* Given a binary tree, print its nodes in preorder*/
void printPreorder(struct Node* node)
{
    if (node == NULL)
        return;
 
    /* first print data of node */
    cout << node->data << " ";
 
    /* then recur on left sutree */
    printPreorder(node->left);
 
    /* now recur on right subtree */
    printPreorder(node->right);
}
 
/* Driver program to test above functions*/
int main()
{
    struct Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
 
    cout << "\nPreorder traversal of binary tree is \n";
    printPreorder(root);
 
    cout << "\nInorder traversal of binary tree is \n";
    printInorder(root);
 
    cout << "\nPostorder traversal of binary tree is \n";
    printPostorder(root);
 
    return 0;
}

Arithmetic Expression Tree

after that we can calculate the tree by postfix or post-order

Sorting Algorithms

 it is sometimes useful to know if a sorting algorithm is stable
A sorting algorithm is stable if it preserves the original order of elements with equal key values (where the key is the value the algorithm sorts by). For example,

Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
Example:


First Pass: 
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1. 
( 1 5 4 2 8 ) –>  ( 1 4 5 2 8 ), Swap since 5 > 4 
( 1 4 5 2 8 ) –>  ( 1 4 2 5 8 ), Swap since 5 > 2 
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Second Pass: 
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) 
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2 
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 
( 1 2 4 5 8 ) –>  ( 1 2 4 5 8 ) 
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass: 
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 
template<class T>
void Swap(T* p1,T* p2){
    T p3=*p1;
    *p1=*p2;
    *p2=p3;
    return;
}

template<typename T ,int size>
void BubbleSort(T (&t)[size]){
    for(int i=1;i<size;i++){
        for(int ii=0;ii<size-i;ii++){
            if(t[ii]>t[ii+1])
                Swap(t+(ii+1),t+(ii));
        }
    }
}

Insertion Sort

void insertionSort(int arr[], int n)
{
    int i, key, j;
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Merge Sort

void merge(int array[], int const left, int const mid, int const right)
{
    auto const subArrayOne = mid - left + 1;
    auto const subArrayTwo = right - mid;

    auto *leftArray = new int[subArrayOne],
         *rightArray = new int[subArrayTwo];

    for (auto i = 0; i < subArrayOne; i++)
        leftArray[i] = array[left + i];
    for (auto j = 0; j < subArrayTwo; j++)
        rightArray[j] = array[mid + 1 + j];
 
    auto indexOfSubArrayOne = 0, 
        indexOfSubArrayTwo = 0; 
    int indexOfMergedArray = left; 
 
    while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo) {
        if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]) {
            array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
            indexOfSubArrayOne++;
        }
        else {
            array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
            indexOfSubArrayTwo++;
        }
        indexOfMergedArray++;
    }

    while (indexOfSubArrayOne < subArrayOne) {
        array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
        indexOfSubArrayOne++;
        indexOfMergedArray++;
    }

    while (indexOfSubArrayTwo < subArrayTwo) {
        array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
        indexOfSubArrayTwo++;
        indexOfMergedArray++;
    }
}

void mergeSort(int array[], int const begin, int const end)
{
    if (begin >= end)
        return; 
    auto mid = begin + (end - begin) / 2;
    mergeSort(array, begin, mid);
    mergeSort(array, mid + 1, end);
    merge(array, begin, mid, end);
}

Quick Sort

The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.

#include <bits/stdc++.h>
using namespace std;

void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

int partition (int arr[], int low, int high)
{
    int pivot = arr[high]; // pivot
    int i = (low - 1); // Index of smaller element and indicates the right position of pivot found so far
 
    for (int j = low; j <= high - 1; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
 

Counting Sort

void countSort(char arr[])
{
    char output[strlen(arr)];
    int count[RANGE + 1], i;
    memset(count, 0, sizeof(count));
    for (i = 0; arr[i]; ++i)
        ++count[arr[i]];
    for (i = 1; i <= RANGE; ++i)
        count[i] += count[i - 1];
    for (i = 0; arr[i]; ++i) {
        output[count[arr[i]] - 1] = arr[i];
        --count[arr[i]];
    }
    for (i = 0; arr[i]; ++i)
        arr[i] = output[i];
}
void countSort(vector<int>& arr)
{
    int max = *max_element(arr.begin(), arr.end());
    int min = *min_element(arr.begin(), arr.end());
    int range = max - min + 1;
 
    vector<int> count(range), output(arr.size());
    for (int i = 0; i < arr.size(); i++)
        count[arr[i] - min]++;
 
    for (int i = 1; i < count.size(); i++)
        count[i] += count[i - 1];
 
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }
 
    for (int i = 0; i < arr.size(); i++)
        arr[i] = output[i];
}