Add Sem02

11 files changed, 388 insertions, 3 deletions

diff --git a/README.md b/README.md
index 937d47a..e9ca9b0 100644
--- a/README.md
+++ b/README.md
@@ -1,4 +1,7 @@
 # Код от семинаритe по структури от данни 2024/2025 - Информационни системи
 
 ## Тема 1
-Сложност на алгоритми. Сложност по време и сложност по памет. Анализ на итеративни алгоритми и примери. Алгоритми за сортиране (bubble sort, insertion sort, selection sort) и алгоритми за търсене (linear search, binary search).
\ No newline at end of file
+Сложност на алгоритми. Сложност по време и сложност по памет. Анализ на итеративни алгоритми и примери. Алгоритми за сортиране (bubble sort, insertion sort, selection sort) и алгоритми за търсене (linear search, binary search).
+
+## Тема 2
+Анализ на рекурсивни алгоритми. Quick sort и merge sort. Структури от данни. Динамичен масив (vector) използващ итератори. Амортизирана сложност и амортизиран анализ на операцията по добавяне в динамичен масив.
\ No newline at end of file
diff --git a/Seminar01/README.md b/Seminar01/README.md
index e0fd932..31453f0 100644
--- a/Seminar01/README.md
+++ b/Seminar01/README.md
@@ -219,4 +219,47 @@ unsigned log_down(unsigned n, unsigned base = 2)
 
 Алгоритъм, който генерира всички подмножества на множество с големина n, би имал сложност Θ(2^n).
 
-## Сортиращи алгоритми - bubble sort. Анализ на сложността на bubble sort.
\ No newline at end of file
+## Сортиращи алгоритми. Свойства на сортиращите алгоритми.
+
+1. Стабилност - Запазва се относителната наредба на елементите с еднакви ключове. 
+    * Не винаги сортираме числа. При сортиране на записи (примерно информация за студенти) сортираме по ключ (примерно факултетен номер).
+    * Ако получим списък от записи за оценките на студенти от някой изпит, сортирани по имена, и ги сортираме със стабилен сортиращ алгоритъм по оценки, студентите с еднакви оценки ще останат сортирани и по имена.
+    * Ако ги сортираме с нестабилен сортиращ алгоритъм това не е сигурно.
+
+2. Адаптивност - Сортиращ алгоритъм нарицаме "адаптивен" ако се взема предвид текущата наредба на елементите.
+3. in-place - Алгоритъм наричаме `in-place` ако не се използва допълнителна памет за неговата работа.
+
+## Bubble sort
+* Best case: Θ(n)
+* Average case: Θ(n^2)
+* Worst case: Θ(n^2)
+
+* Стабилен сортиращ алгоритъм заради строгото неравенство.
+* Адаптивен - Зависи от това какво разбираме под `почти сортиран` масив.
+    * [1, 2, 3, 4, 5, 4] - Bubble sort би се справил добре върху този вход.
+    * [2, 3, 4, 5, 1]    - В случая отново ще имаме Θ(n^2) стъпки.
+* in-place: да
+
+## Selection sort
+* Best case: Θ(n^2)
+* Average case: Θ(n^2)
+* Worst case: Θ(n^2)
+
+* Нестабилен сортиращ алгоритъм.
+* Адаптивен - не
+* in-place - да
+
+
+## Insertion sort
+* Best case: Θ(n)
+* Average case: Θ(n^2)
+* Worst case: Θ(n^2)
+
+* Стабилен сортиращ алгоритъм.
+* Адаптивен - да
+* in-place - да
+
+## Binary search
+* Best case: Θ(1)
+* Average case: Θ(log(n))
+* Worst case: Θ(log(n))
\ No newline at end of file
diff --git a/Seminar01/src/searching-algorithms/binary-search.cpp b/Seminar01/src/searching-algorithms/binary-search.cpp
index b5befb0..7404e0a 100644
--- a/Seminar01/src/searching-algorithms/binary-search.cpp
+++ b/Seminar01/src/searching-algorithms/binary-search.cpp
@@ -27,7 +27,21 @@ int binarySearch(const T* arr, size_t size, T elem)
     return -1;
 }
 
+constexpr unsigned EXAMPLE_SIZE = 7;
+
 int main()
 {
-    
+    int example[EXAMPLE_SIZE] = { 1, 2, 4, 8, 16, 32, 64 };
+    int needle = 4;
+
+    int index = binarySearch(example, EXAMPLE_SIZE, needle);
+    if(index == -1)
+    {
+        std::cout << "Unable to find the element" << std::endl;
+    }
+    else
+    {
+        std::cout << "Element " << needle << " found at " 
+            << index << " position: " << example[index] << std::endl; 
+    }
 }
\ No newline at end of file
diff --git a/Seminar02/README.md b/Seminar02/README.md
new file mode 100644
index 0000000..1ffcc53
--- /dev/null
+++ b/Seminar02/README.md
@@ -0,0 +1,119 @@
+# Втори семинар по структури от данни - 17.10.2024
+
+## Анализ на рекурсивни алгоритми.
+В първи семинар разгледахме метод за анализиране на итеративни алгоритми. Този метод не работи когато анализираме рекурсивни алгоритми. За да намерим сложността на рекурсивен алгоритъм използваме рекурентни уравнения.
+
+### Рекурентно уравнение
+* Рекурентно уравнение е уравнение, което изразява общия член на някаква редица от числа чрез предишните членове.
+
+Рекурентните уравнения описват рекурсивни алгоритми. Разбира се, както рекурсивните алгоритми имат дъно, така и рекурентните уравнения имат начални условия.
+
+Нека разгледаме следния пример:
+```cpp
+void sum_rec(int* arr, unsigned size, int& sum)
+{
+    if(size == 0)
+        return;
+    
+    sum += arr[0];
+    
+    return sum_rec(arr + 1, size - 1, sum);
+}
+```
+
+Какво би било рекурентното уравнение, което описва този рекурсивен алгоритъм? Нека с променливата `n` означаваме големината на масива.
+
+* Разглеждаме дъното. При n = 0 имаме Θ(1) работа.
+* В противен случай, имаме едно добавяне и извикване на алгоритъма с вход `n - 1`.
+
+Съставяме уравнението:
+* T(0) = 1
+* T(n) = T(n - 1) + 1
+
+Решение на рекурентно уравнение наричаме затворена формула. Решение на горния пример би било:
+$$
+T(n) = n + 1
+$$
+
+## Методи за решаване на рекурентни уравнения
+
+### 1. Чрез развиване
+Винаги можем да започнем да развиваме рекурентното уравнение търсейки някаква закономерност.
+$$
+T(n) = T(n - 1) + \theta(1) = T(n - 2) + \theta(1) + \theta(1) = \newline
+T(0) + \theta(1) + \dots + \theta(1) = \newline
+(n + 1) * \theta(1) = \theta(n)
+$$
+
+### Чрез дърво на рекурсията
+Всеки рекурсивен алгоритъм образува дърво на рекурсията. Разглеждайки броя върхове и работата, която се "извършва" във всеки връх, височината на дървото и т.н. можем да направим изводи за решението на рекурентната редица. 
+
+Нека разгледаме следното рекурентно уравнение:
+* T(0) = 1
+* T(1) = 1
+* T(n) = 2 * T(n / 2) + n
+
+Това рекурентно уравнение описва работата на алгоритъмът `Merge Sort`, който ще разгледаме съвсем скоро. Как изглежда дървото на рекурсията?
+
+![tree-merge](media/rec_tree.png)
+
+Височината на това дърво е приблизително log(n). При стойност на параметъра `k = log_2(n)` стойността в листото е 1.
+На всяко ниво имаме Θ(n) работа. Трябва да забележим, че работата за ниво j се смята по следната формула:
+$$
+2^j * \frac{\theta(n)}{2^j} = \theta(n)
+$$ 
+
+Това ще рече броят на върховете на всяко ниво умножен по работата, която се извършва във върха на дървото.
+
+Щом броя на нивата е Θ(log(n)) а на всяко ниво се извършва Θ(n) работа, то търсената сложност е Θ(n log(n)).
+
+### Други методи
+
+## Примери
+Нека разгледаме някои примери за рекурентни уравнения.
+$$ 
+T(0) = \theta(1)
+\newline
+T(n) = 3T(n - 1) + \theta(1)
+$$
+
+Дървото на рекурсията би изглеждало по следния начин:
+![tree-recur](media/recurr2.png)
+
+Нивата на това дърво ще са n на брой. Всеки елемент е с единица по - малък от баща си. Също така, на всяко ниво има 3^j върха, където j е номерът на нивото (номерираме от 0). Всеки възел извършва Θ(1) работа. Сумираме по нива:
+$$
+\sum_{i = 0}^n 3^i * \theta(1) = \frac{3^{n + 1} - 1}{2} * \theta(1) = \theta(3^n)
+$$
+
+## Алгоритмична схема "разделяй и владей"
+* Разделяй - Ако входът е достатъчно голям той се разделя на части и се преминава към стъпката **владей**. В противен случай (ако входът е достатъчно малък) задачата се решава по някакъв тривиален начин. (пример е дъното на рекурсията в `Merge Sort` където масив с големина 0 или 1 е тривиално сортиран.)
+* Владей   - Пускаме алгоритъма върху всяка от частите и получаваме резултатите.
+* Комбинирай - Използваме тези резултати за да получим желания от нас резултат.
+
+## Алгоритъмът Merge Sort
+Първо, нека се запознаем с функцията `merge`. Тя приема два сортирани масива и като резултат създава сортиран масив. Важно условие е масивите да са сортирани. Ако това не е така функцията не прави нищо логично.
+
+Ако имаме масив с n елемента и успешно сортираме лявата и дясната половина, то извиквайки функцията `merge` ще получим желания сортиран масив. Но как да сортираме лявата и дясната половина?
+
+Спомняме си, че пишем сортиращ алгоритъм. Извиквам mergeSort рекурсивно върху лявата и дясната половина на масива и след като ги сортира викаме функцията merge. mergeSort ще продължи да разбива масива на две, после левия и десния подмасив на още две и т.н.  
+
+Масив от един елемент е сортиран и ще използваме този случай като дъно на рекурсията.
+
+Нека разгледаме следната диаграма:
+![merge](media/merge.png)
+
+Оцветените в зелено клетки са подмасивите, на които вече е бил извикан merge.
+
+Следната диаграма представя визуално как работи функцията `merge`:
+![merge-func](media/merge-func.png)
+
+Двата масива са сортирани, та има смисъл да гледаме единствено най - левите елементи. На всяка стъпка избираме по - малкия и го слагаме в резултатен масив. Трябва, разбира се, да се разгледа и случая в който масивите не са с равни дължини.
+
+Сложността на `Merge Sort` се описва чрез рекурентната редица, използвана като пример за решение използващо метода с дърво на рекурсията. И в трита случая имаме Θ(n log(n))
+
+Стабилен - Да
+Адаптивен - Не
+in-place - Не
+Сложност по памет - Θ(n)
+
+## Алгоритъмът Quick Sort
\ No newline at end of file
diff --git a/Seminar02/media/merge-func.png b/Seminar02/media/merge-func.png
new file mode 100644
index 0000000..61db955
--- /dev/null
+++ b/Seminar02/media/merge-func.png
diff --git a/Seminar02/media/merge.png b/Seminar02/media/merge.png
new file mode 100644
index 0000000..08fbfa0
--- /dev/null
+++ b/Seminar02/media/merge.png
diff --git a/Seminar02/media/rec_tree.png b/Seminar02/media/rec_tree.png
new file mode 100644
index 0000000..37c39cd
--- /dev/null
+++ b/Seminar02/media/rec_tree.png
diff --git a/Seminar02/media/recurr2.png b/Seminar02/media/recurr2.png
new file mode 100644
index 0000000..5ea9a0f
--- /dev/null
+++ b/Seminar02/media/recurr2.png
diff --git a/Seminar02/src/sorting-algorithms/merge-sort-dummy.cpp b/Seminar02/src/sorting-algorithms/merge-sort-dummy.cpp
new file mode 100644
index 0000000..b5b2b1c
--- /dev/null
+++ b/Seminar02/src/sorting-algorithms/merge-sort-dummy.cpp
@@ -0,0 +1,54 @@
+#include <iostream>
+
+template<typename T>
+void merge(T* arr1, unsigned len1, 
+           T* arr2, unsigned len2)
+{
+	T* resultArray = new T[len1 + len2];
+
+	unsigned cursor1 = 0;
+	unsigned cursor2 = 0;
+	unsigned resultCursor = 0;
+
+	while (cursor1 < len1 && cursor2 < len2)
+	{
+		if (arr1[cursor1] <= arr2[cursor2])
+			resultArray[resultCursor++] = arr1[cursor1++];
+		else
+			resultArray[resultCursor++] = arr2[cursor2++];
+	}
+
+	while (cursor1 < len1)
+		resultArray[resultCursor++] = arr1[cursor1++];
+    
+	while (cursor2 < len2)
+		resultArray[resultCursor++] = arr2[cursor2++];
+
+	for (size_t i = 0; i < len1 + len2; i++)
+		arr1[i] = resultArray[i];
+    
+	delete[] resultArray;
+}
+
+template <typename T>
+void mergeSort(T* arr, unsigned len)
+{
+	if (len < 2)
+		return;
+
+	unsigned mid = len / 2;
+
+	mergeSort(arr, mid);
+	mergeSort(arr + mid, len - mid);
+
+	merge<T>(arr, mid, arr + mid, len - mid);
+}
+
+int main()
+{
+	int arr[4] = { 9, 6, 5, 8 };
+	mergeSort(arr, 4);
+
+	for (int i = 0; i < 4; i++)
+		std::cout << arr[i] << " ";
+}
\ No newline at end of file
diff --git a/Seminar02/src/sorting-algorithms/merge-sort.cpp b/Seminar02/src/sorting-algorithms/merge-sort.cpp
new file mode 100644
index 0000000..3ae3c09
--- /dev/null
+++ b/Seminar02/src/sorting-algorithms/merge-sort.cpp
@@ -0,0 +1,87 @@
+#include <iostream>
+#include <vector>
+#include <algorithm>
+
+template<class T>
+void merge(T* firstArray, unsigned firstSize, 
+           T* secondArray, unsigned secondSize,
+           T* buffer)
+{
+    unsigned firstIter = 0;
+    unsigned secondIter = 0;
+    unsigned resultIter = 0;
+
+    while(firstIter < firstSize && secondIter < secondSize)
+    {
+        if(firstArray[firstIter] > secondArray[secondIter])
+        {
+            buffer[resultIter] = secondArray[secondIter];
+            secondIter++;
+        }
+        else
+        {
+            buffer[resultIter] = firstArray[firstIter];
+            firstIter++;
+        }
+        resultIter++;
+    }
+
+    while(firstIter < firstSize)
+    {
+        buffer[resultIter++] = firstArray[firstIter++];
+    }
+
+    while(secondIter < secondSize)
+    {
+        buffer[resultIter++] = secondArray[secondIter++];
+    }
+
+    for (size_t i = 0; i < firstSize + secondSize; i++)
+    {
+        firstArray[i] = buffer[i];
+    }
+}
+
+
+template<class T>
+void mergeSortStep(T* arr, unsigned size, T* buffer)
+{
+    if(size < 2)
+        return;
+    
+    unsigned mid = size / 2;
+    mergeSortStep(arr, mid, buffer);
+    mergeSortStep(arr + mid, size - mid, buffer);
+
+    merge(arr, mid, arr + mid, size - mid, buffer);
+
+    for (size_t i = 0; i < size; i++)
+        arr[i] = buffer[i];
+}
+
+template<class T>
+void mergeSort(T* arr, unsigned size)
+{
+    if(size < 2)
+        return;
+    
+    T* buffer = new T[size];
+    mergeSortStep(arr, size, buffer);
+    delete[] buffer;
+}
+
+int main()
+{
+    std::vector<int> numbers;
+    unsigned size = rand() % 10000;
+    numbers.resize(size);
+
+    for (size_t i = 0; i < size; i++)
+    {
+        numbers[i] = rand() % 10000;
+    }
+
+    mergeSort(numbers.data(), numbers.size());
+
+    std::cout << std::is_sorted(numbers.begin(), numbers.end()) << std::endl;
+}
\ No newline at end of file
diff --git a/Seminar02/src/sorting-algorithms/quick-sort.cpp b/Seminar02/src/sorting-algorithms/quick-sort.cpp
new file mode 100644
index 0000000..3069738
--- /dev/null
+++ b/Seminar02/src/sorting-algorithms/quick-sort.cpp
@@ -0,0 +1,65 @@
+#include <iostream>
+#include <algorithm> // std::is_sorted
+#include <vector>    // std::vector
+
+/// @brief Reorders the elements in such a way that all elements for which are less than pivot 
+// precede all elements which are greater or equal to pivot. Relative order of the elements is not preserved.
+// TODO: remove copy somehow???
+template <class T>
+size_t partition(T* pArr, size_t len)
+{
+    if (pArr[0] > pArr[len - 1])
+        std::swap(pArr[0], pArr[len - 1]);
+
+    T& partitioningElement = pArr[len - 1];
+    size_t left = 0;
+    size_t right = len - 1;
+
+    while (true)
+    {
+        while (pArr[++left] < partitioningElement)
+            ;
+
+        while (pArr[--right] > partitioningElement)
+        {
+            if (left == right)
+                break;
+        }
+
+        if (left >= right)
+            break;
+
+        std::swap(pArr[left], pArr[right]);
+    }
+
+    std::swap(pArr[left], partitioningElement);
+    return left;
+}
+
+template<class T>
+void quickSort(T* arr, unsigned size)
+{
+    if(size < 2)
+        return;
+    
+    unsigned pivotPos = partition(arr, size);
+
+    quickSort(arr, pivotPos);
+    quickSort(arr + pivotPos + 1, size - pivotPos - 1);
+}
+
+int main()
+{
+    std::vector<int> numbers;
+    unsigned size = rand() % 10000;
+    numbers.resize(size);
+
+    for (size_t i = 0; i < size; i++)
+    {
+        numbers[i] = rand() % 10000;
+    }
+
+    quickSort(numbers.data(), numbers.size());
+
+    std::cout << std::is_sorted(numbers.begin(), numbers.end());
+}
\ No newline at end of file