chore: name of first year folder

9 files changed, 344 insertions, 0 deletions

diff --git a/1_anno/Programmazione_2/algorithms/binarysearch.cc b/1_anno/Programmazione_2/algorithms/binarysearch.cc
new file mode 100644
index 0000000..c9b4cd7
--- /dev/null
+++ b/1_anno/Programmazione_2/algorithms/binarysearch.cc
@@ -0,0 +1,33 @@
+#include<iostream>
+
+using namespace std;
+
+bool bs(int a[], int i, int j, int x) {
+    if(j<i) return false;
+    int mid = i+(j-i)/2;
+    if(a[mid] == x)
+        return true;
+    if(a[mid] > x)
+        return bs(a, i, mid-1, x);
+    return bs(a, mid+1, j, x);
+}
+
+bool bs2(int a[], int i, int j, int x) {
+    while(i <= j) {
+        int mid = i+(j-i)/2;
+        if(a[mid] == x) return true;
+        if(a[mid] < x)
+            i = mid+1;
+        else
+            j = mid-1;
+    }
+    return false;
+}
+
+int main() {
+    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+    for(int i = 0; i < 12; ++i)
+        cout << i << ' '<<bs(a, 0, 9, i) << ' ' << bs2(a, 0, 9, i) << endl;
+    return 0;
+}
+
diff --git a/1_anno/Programmazione_2/algorithms/cbrt.cc b/1_anno/Programmazione_2/algorithms/cbrt.cc
new file mode 100644
index 0000000..30c7792
--- /dev/null
+++ b/1_anno/Programmazione_2/algorithms/cbrt.cc
@@ -0,0 +1,37 @@
+#include<iostream>
+
+using namespace std;
+
+int cbrt(int n) {
+    int i = 0;
+    int j = n;
+    int q = (i+j)/2;
+    while(q*q*q != n) {
+        q = (i+j)/2;
+        if(q*q*q < n)
+            i=q;
+        else
+            j=q;
+    }
+    return q;
+}
+
+double cbrt2(int n) {
+    int i = 1;
+    while(i*i*i <= n)
+        ++i;
+    // precision
+    
+    --i;
+    while(i*i*i < n)
+        i+=0.000001;
+    
+    return i;
+}
+
+int main() {
+    int i;
+    cin >> i;
+    cout << i << ' ' << cbrt(i) << endl;
+    return 0;
+}
diff --git a/1_anno/Programmazione_2/algorithms/insertionsort.cc b/1_anno/Programmazione_2/algorithms/insertionsort.cc
new file mode 100644
index 0000000..9b309d6
--- /dev/null
+++ b/1_anno/Programmazione_2/algorithms/insertionsort.cc
@@ -0,0 +1,42 @@
+#include<iostream>
+
+using namespace std;
+
+void insertionsort(int a[], int n) {
+    for(int i = 1; i < n; ++i) {
+        int j = i-1;
+        int key = a[i];
+        while(j > -1 && a[j] > key) {
+            swap(a[j+1], a[j]);
+            --j;
+        }
+        a[j+1] = key;
+    }
+}
+
+void insertionsort_rec(int a[], int n) {
+    if(n < 2) return;
+    insertionsort_rec(a, n-1);
+ 
+    int key = a[n-1];
+    int j = n-2;
+
+    while(j > -1 && a[j] > key) {
+        swap(a[j+1], a[j]);
+        --j;
+    }
+
+    a[j+1] = key;
+
+}
+
+int main() {
+    int arr[10] = {3, 450, 12, 4, -1, 0, 24, 95, 123, 0};
+    for(int i = 0; i < 10; ++i)
+        cout << *(arr+i) << ' ';
+    cout << endl;
+    insertionsort_rec(arr, 10);
+    for(int i = 0; i < 10; ++i)
+        cout << *(arr+i) << ' ';
+    return 0;
+}
diff --git a/1_anno/Programmazione_2/algorithms/log.cc b/1_anno/Programmazione_2/algorithms/log.cc
new file mode 100644
index 0000000..1e49a2e
--- /dev/null
+++ b/1_anno/Programmazione_2/algorithms/log.cc
@@ -0,0 +1,25 @@
+#include<iostream>
+
+using namespace std;
+
+double log(double n) {
+    if(n <= 2) return 1.0;
+    return 1.0 + log(n/2);
+}
+
+int log2(double n) {
+    int a = 1;
+
+    while(n > 2) {
+        n /= 2;
+        ++a;
+    }
+
+    return a;
+}
+
+int main() {
+    for(int i = 0; i < 25; ++i)
+        cout << i << ' ' << log(i) << ' ' << log2(i) << endl;
+    return 0;
+}
diff --git a/1_anno/Programmazione_2/algorithms/mergesort.cc b/1_anno/Programmazione_2/algorithms/mergesort.cc
new file mode 100644
index 0000000..68d28cb
--- /dev/null
+++ b/1_anno/Programmazione_2/algorithms/mergesort.cc
@@ -0,0 +1,52 @@
+#include<iostream>
+
+using namespace std;
+
+void merge(int A[], int l, int q, int r) {
+    int i = l;
+    int j = q+1;
+    int k = l;
+    int B[r];
+
+    while((i <= q) && (j <= r)) {
+        if(A[i] <= A[j])
+            B[k] = A[i++];
+        else
+            B[k] = A[j++];
+
+        k++;
+    }
+
+    while(i <= q)
+        B[k++] = A[i++];
+
+    while(j <= r)
+        B[k++] = A[j++];
+
+    for(k = l; k <= r; ++k) 
+        A[k] = B[k];
+}
+
+void mergesort(int A[], int l, int r) {
+    if(l < r) {
+        int q = (l+r)/2;
+        mergesort(A, l, q);
+        mergesort(A, q+1, r);
+        merge(A, l, q, r);
+    }
+}
+
+
+int main() {
+    int a[] = {7,1,22,3,2,12,27,31,6};
+    for(int i = 0; i < 9; ++i) {
+        cout << a[i] << ' ';
+    }
+    cout << endl;
+    mergesort(a, 0, 8);
+    for(int i = 0; i < 9; ++i) {
+        cout << a[i] << ' ';
+    }
+
+    return 0;
+}
diff --git a/1_anno/Programmazione_2/algorithms/pow.cc b/1_anno/Programmazione_2/algorithms/pow.cc
new file mode 100644
index 0000000..16cf419
--- /dev/null
+++ b/1_anno/Programmazione_2/algorithms/pow.cc
@@ -0,0 +1,25 @@
+#include<iostream>
+
+using namespace std;
+
+int pow(int x, int y) {
+    int a = 1;
+    
+    for(int i = 0; i < y; ++i)
+        a*=x;
+    
+    return a;
+}
+
+
+int pow2(int x, int y) {
+    if(y < 1) return 1;
+    
+    return x*pow(x, y-1);
+}
+
+int main() {
+    cout << pow(2, 5) << endl;
+    cout << pow2(2, 5) << endl;
+    return 0;
+}
diff --git a/1_anno/Programmazione_2/algorithms/quicksort.cc b/1_anno/Programmazione_2/algorithms/quicksort.cc
new file mode 100644
index 0000000..795bd7b
--- /dev/null
+++ b/1_anno/Programmazione_2/algorithms/quicksort.cc
@@ -0,0 +1,38 @@
+#include<iostream>
+
+using namespace std;
+
+int partition(int A[], int l, int r) {
+    int x = A[r];
+    int i = l-1;
+
+    for(int j = l; j < r; ++j) {
+        if(A[j] <= x) {
+            swap(A[++i], A[j]);
+        }
+    }
+    swap(A[++i], A[r]);
+    return i;
+}
+
+void quicksort(int A[], int l, int r) {
+    if(l < r) {
+        int q = partition(A, l, r);
+        quicksort(A, l, q-1);
+        quicksort(A, q+1, r);
+    }
+}
+
+int main() {
+    int a[] = {7,1,22,3,2,12,27,31,6};
+    for(int i = 0; i < 9; ++i) {
+        cout << a[i] << ' ';
+    }
+    cout << endl;
+    quicksort(a, 0, 8);
+    for(int i = 0; i < 9; ++i) {
+        cout << a[i] << ' ';
+    }
+
+    return 0;
+}
diff --git a/1_anno/Programmazione_2/algorithms/selectionsort.cc b/1_anno/Programmazione_2/algorithms/selectionsort.cc
new file mode 100644
index 0000000..57dcc17
--- /dev/null
+++ b/1_anno/Programmazione_2/algorithms/selectionsort.cc
@@ -0,0 +1,46 @@
+#include<iostream>
+#include<algorithm>
+
+using namespace std;
+
+void selectionsort(int a[], int n) {
+    for(int i = 0; i < n-1; ++i) {
+        int min = i;
+        for(int j = i+1; j < n; ++j) {
+            if(a[j] < a[min])
+                min = j;
+        }
+
+        swap(a[min], a[i]);
+    }
+}
+
+int min_i(int a[], int i, int j) {
+    if(i == j) return i;
+
+    int k = min_i(a, i+1, j);
+    return (a[i] < a[k]) ? i : k;
+}
+
+void selectionsort_rec(int* a, int b, int e=0) {
+    if(b == e) return;
+
+    int key = min_i(a, e, b-1);
+    if(key != e)
+        swap(a[key], a[e]);
+
+    selectionsort_rec(a, b, e+1);
+}
+
+int main() {
+    int arr[] = {3,450,12,4,-1,0,24,95,123,0};
+    for(int i = 0; i < 10; ++i) {
+        cout << *(arr+i) << ' ';
+    }
+    cout << endl;
+    selectionsort_rec(arr, 10);
+    for(int i = 0; i < 10; ++i) {
+        cout << *(arr+i) << ' ';
+    }
+    return 0;
+}
diff --git a/1_anno/Programmazione_2/algorithms/sqrt.cc b/1_anno/Programmazione_2/algorithms/sqrt.cc
new file mode 100644
index 0000000..aa6b032
--- /dev/null
+++ b/1_anno/Programmazione_2/algorithms/sqrt.cc
@@ -0,0 +1,46 @@
+#include<iostream>
+
+using namespace std;
+
+double abs(double n) {
+    if(n < 0) return -n;
+
+    return n;
+}
+
+
+double sq(int n) {
+    double x = n;
+    double y = 1;
+    while(x-y > 0.0000001) {
+        x = (x+y)/2;
+        y = n/x;
+    }
+    return x;
+}
+
+double sq2_n(double n, double a) {
+    if(abs(a*a - n) <= 0.000001) {
+        return a;
+    }
+
+    return sq2_n(n, (a+n/a)/2);
+}
+
+double sq2(int n) {
+    return sq2_n(n, n/2);
+}
+
+double sqrt_d(int n) {
+    double x = 1;
+    while(abs(x*x-n)>=0.0000001) {
+        x = ((n/x)+x)/2;
+    }
+    return x;
+}
+
+int main() {
+    cout << sq(81) << endl;
+    cout << sq2(81) << endl;
+    return 0;
+}