Website Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
Commit7eee5a78005a9a569186d2c8b4b645a818ab9bf1 (patch)
Author
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-06 07:04:44 -0400
Committer
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-06 07:04:44 -0400
Files84594e0af29cefa5aae76ace5f8eb81484400e31
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar.gz
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.zip
Parent0841635826cb03c0e74cd75ec3c97c4c3b594d8b (diff)
Cleanup
99 files changed, 1 insertions, 6917 deletions
-rw-r--r--Additional/Additional-2022-CS/README.md68
-rw-r--r--Additional/Additional-2022-CS/concatenate-queues.cpp70
-rw-r--r--Additional/Additional-2022-CS/equalize.cpp60
-rw-r--r--Additional/Additional-2022-CS/merge-sorted.cpp51
-rw-r--r--Additional/Additional-2022-CS/oddEvenList.cpp55
-rw-r--r--Additional/Additional-2022-CS/rearange.cpp55
-rw-r--r--Additional/Additional-2022-CS/reverse-nodes-in-k-group.cpp54
-rw-r--r--Additional/Additional-2023-SI/IntervalCollection.cpp103
-rw-r--r--Additional/Additional-2023-SI/MergeIntoList.cpp117
-rw-r--r--Additional/Additional-2023-SI/queue-insertion.cpp109
-rw-r--r--Additional/Additional-2023-SI/readme.md13
-rw-r--r--Additional/Additional-2023-SI/rearrange.cpp112
-rw-r--r--README.md16
-rw-r--r--Seminar01/README.md74
-rw-r--r--Seminar01/Сложност.pdfbin217353 -> 0 bytes
-rw-r--r--Seminar02/README.md92
-rw-r--r--Seminar02/bonusTask01.cpp51
-rw-r--r--Seminar02/recursion.cpp33
-rw-r--r--Seminar02/task01.cpp51
-rw-r--r--Seminar02/task02.cpp24
-rw-r--r--Seminar02/task03.cpp59
-rw-r--r--Seminar02/task04.cpp47
-rw-r--r--Seminar02/Стек.pdfbin174971 -> 0 bytes
-rw-r--r--Seminar03/Linked-Queue.hpp162
-rw-r--r--Seminar03/QueueTests.cpp28
-rw-r--r--Seminar03/README.md185
-rw-r--r--Seminar03/media/arr-queue.pngbin3564 -> 0 bytes
-rw-r--r--Seminar03/media/qexample.pngbin9249 -> 0 bytes
-rw-r--r--Seminar03/task01.cpp27
-rw-r--r--Seminar03/task02.cpp93
-rw-r--r--Seminar03/task03.cpp41
-rw-r--r--Seminar04/README.md209
-rw-r--r--Seminar04/find-middle.cpp28
-rw-r--r--Seminar04/insert-at-beg.cpp20
-rw-r--r--Seminar04/linked-list-utils.h74
-rw-r--r--Seminar04/media/AmortizedAnalysis.pngbin1586478 -> 0 bytes
-rw-r--r--Seminar04/reorder-linked-list.cpp160
-rw-r--r--Seminar04/reverse-linked-list.cpp25
-rw-r--r--Seminar05/LinkedList.hpp326
-rw-r--r--Seminar05/README.md342
-rw-r--r--Seminar05/list-cheat-sheet.cpp122
-rw-r--r--Seminar06/DLLSkeleton.cpp70
-rw-r--r--Seminar06/DoublyLinkedList.hpp294
-rw-r--r--Seminar06/Linked-List-Palindrome.cpp29
-rw-r--r--Seminar06/README.md73
-rw-r--r--Seminar06/insertSorted.cpp63
-rw-r--r--Seminar06/linkedListCycle.cpp33
-rw-r--r--Seminar06/media/dll.pngbin10452 -> 0 bytes
-rw-r--r--Seminar06/task02.cpp110
-rw-r--r--Seminar07/README.md2
-rw-r--r--Seminar07/counting-sort.cpp40
-rw-r--r--Seminar07/Сортиращи алгоритми.pdfbin335838 -> 0 bytes
-rw-r--r--Seminar08/README.md193
-rw-r--r--Seminar08/height.cpp14
-rw-r--r--Seminar08/inorder-traversal.cpp23
-rw-r--r--Seminar08/insert-in-bst.cpp36
-rw-r--r--Seminar08/media/left-child-right-sibling.pngbin22100 -> 0 bytes
-rw-r--r--Seminar08/media/stick.pngbin13709 -> 0 bytes
-rw-r--r--Seminar08/media/subtree.pngbin32004 -> 0 bytes
-rw-r--r--Seminar08/media/tree-first-example.pngbin16135 -> 0 bytes
-rw-r--r--Seminar08/media/tree-second-example.pngbin20847 -> 0 bytes
-rw-r--r--Seminar08/min-max-elem.cpp64
-rw-r--r--Seminar08/tree-utils.h230
-rw-r--r--Seminar09/README.md119
-rw-r--r--Seminar09/exam1.cpp35
-rw-r--r--Seminar09/media/rotations.pngbin50960 -> 0 bytes
-rw-r--r--Seminar09/solutions.cpp140
-rw-r--r--Seminar10/AVLTree.hpp203
-rw-r--r--Seminar10/README.md456
-rw-r--r--Seminar10/media/avl-disbalance-0.pngbin51881 -> 0 bytes
-rw-r--r--Seminar10/media/avl-disbalance-1.pngbin87543 -> 0 bytes
-rw-r--r--Seminar10/media/avl-disbalance.pngbin52310 -> 0 bytes
-rw-r--r--Seminar10/wordle.cpp55
-rw-r--r--Seminar11/DFS-Additional.cpp200
-rw-r--r--Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.cpp82
-rw-r--r--Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.h50
-rw-r--r--Seminar11/Graph-Impl/AdjacencyListGraph/src.cpp19
-rw-r--r--Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp97
-rw-r--r--Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h52
-rw-r--r--Seminar11/README.md187
-rw-r--r--Seminar11/bfs-dfs.cpp65
-rw-r--r--Seminar11/media/dfs-example.gifbin611116 -> 0 bytes
-rw-r--r--Seminar11/media/dir-graph.pngbin10387 -> 0 bytes
-rw-r--r--Seminar11/media/graph.pngbin10829 -> 0 bytes
-rw-r--r--Seminar11/media/matrix.pngbin26595 -> 0 bytes
-rw-r--r--Seminar11/media/weighted-dirscted-graph (1).pngbin19387 -> 0 bytes
-rw-r--r--Seminar11/media/weighted-graph.pngbin16585 -> 0 bytes
-rw-r--r--Seminar11/media/weighted-list.pngbin42035 -> 0 bytes
-rw-r--r--Seminar11/package.json0
-rw-r--r--Seminar12/Dijkstra.cpp97
-rw-r--r--Seminar12/README.md146
-rw-r--r--Seminar13/README.md20
-rw-r--r--Seminar13/task01.cpp85
-rw-r--r--Seminar13/task02.cpp41
-rw-r--r--Seminar14/README.md211
-rw-r--r--Seminar14/SeparateChaining.hpp110
-rw-r--r--Seminar14/media/insert-first.pngbin2682 -> 0 bytes
-rw-r--r--Seminar14/media/insert-second.pngbin2759 -> 0 bytes
-rw-r--r--Seminar14/src.cpp18
diff --git a/Additional/Additional-2022-CS/README.md b/Additional/Additional-2022-CS/README.md
deleted file mode 100644
index 96b8018..0000000
--- a/Additional/Additional-2022-CS/README.md
+++ /dev/null
@@ -1,68 +0,0 @@
-# Задачи за допълнително упражнение 22.11.2022
-
-## Задача първа - Merge linked lists
-Да се напише функция, която получава два сортирани списъка с елементи цели числа, обединява ги в един сортиран списък и връща резултата.
-
-**Пример:**
-
-Вход:
-* l1 = [1, 2, 4, 8, 16]
-* l2 = [1, 2, 3, 5, 7, 9, 11]
-
-Изход:
-
-* [1, 1, 2, 2, 3, 4, 5, 7, 8, 9, 11, 16]
-
-## Задача втора
-Даден е едносвъран списък, чийто елементи са числа. Напишете функция rearange, която пренарежда елементите, така че първо да бъдат четните числа, после нечетните. Относителната наредба между числата трябва да се запази. Решението ви трябва да работи за O(n) време и O(1) памет.
-
-Пример:
-
-Вход:
-
-* 3 -> 5 -> 2 -> 9 -> 4
-
-Изход:
-
-* 2 -> 4 -> 3 -> 5 -> 9
-
-## Задача трета
-Даден е свързан списък, чиито елементи са числа. Напишете функция oddEvenList, която пренарежда списъка така, че в първо да бъдат възлите на нечетни **позиции** а след това тези на четни. Решението ви трябва да работи в O(n) време и O(1) памет. Считаме първата позиция за нечетна.
-
-Пример:
-
-Вход:
-* 1 -> 2 -> 3 -> 4 -> 5
-
-Изход:
-* 1 -> 3 -> 5 -> 2 -> 4
-
-Вход:
-* 2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7
-
-Изход:
-* 2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4
-
-## Задача четвърта - Reverse nodes in K-group
-Да се напише функция, която приема едносвързан списък и естествено число k. За k знаем, че е по - голямо от 0, но по - малко от дължината на списъка. K група наричаме възлите на индекси [0..k-1], [k..2k-1] и тн. Да се обърнат всички K групи.
-
-Пример:
-
-Вход: [1, 2, 3, 4, 5], k = 2
-
-Тук K групите са (1, 2), (3, 4). В резултата те са обърнати.
-
-Изход: [2, 1, 4, 3, 5]
-
-Вход: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17], k = 4
-
-Тук K групите са (1, 2, 3, 4), (5, 6, 7, 8), (9, 10, 11, 12), (13, 14, 15, 16). В резултата те са обърнати.
-
-Изход: [4, 3, 2, 1, 8, 7, 6, 5, 12, 11, 10, 9, 16, 15, 14, 13, 17]
-
-## Задача пета
-Нека е даден списък L с елементи стекове. Възлите на L са от тип Node<std::stack>. Да се дефинира подходящо параметризирана функция equalize(L), която размества елементите на стековете така, че да няма два стека в L с разлика в броя на елементите, по-голяма от 1.
-
-## Задача шеста
-Даден е свързан списък с една връзка L, чийто елементи са опашки.
-Да се напише функция, което конкатенира всички последователни опашки, чиито елементи отговарят на даден предикат p. \ No newline at end of file
diff --git a/Additional/Additional-2022-CS/concatenate-queues.cpp b/Additional/Additional-2022-CS/concatenate-queues.cpp
deleted file mode 100644
index c3f772e..0000000
--- a/Additional/Additional-2022-CS/concatenate-queues.cpp
+++ /dev/null
@@ -1,70 +0,0 @@
-#include"../Seminar04/linked-list-utils.h"
-#include<iostream>
-#include<queue>
-
-using ListNode = LinkedListNode<std::queue<int>>;
-
-void concatenate(std::queue<int>& to, std::queue<int>& from) {
- while(!from.empty()) {
- to.push(from.front());
- from.pop();
- }
-}
-
-bool all(std::queue<int> q, bool (*pred)(int)) {
- while(!q.empty()) {
- if(!pred(q.front())) {
- return false;
- }
- q.pop();
- }
-
- return true;
-}
-
-void concatenateSimilarQueues(ListNode* ll, bool (*pred)(int)) {
- if(!ll || !ll->next)
- return;
-
- ListNode* iter = ll;
-
- while(iter && iter->next) {
- if(all(iter->data, pred)) {
- while(iter->next && all(iter->next->data, pred)) {
- ListNode* toDelete = iter->next;
- iter->next = iter->next->next;
- concatenate(iter->data, toDelete->data);
-
- delete toDelete;
- }
- }
- iter = iter->next;
- }
-}
-
-void printQueue(std::queue<int> q) {
- std::cout << "[ ";
- while(!q.empty()) {
- std::cout << q.front() << " ";
- q.pop();
- }
- std::cout << " ]" << std::endl;
-}
-
-int main() {
- ListNode* ll = fromList({
- std::queue<int>({1, 2, 3}),
- std::queue<int>({4, 5, 6, 7, 8, 8, 9}),
- std::queue<int>({12, 14, 16}),
- std::queue<int>({101, 102}),
- std::queue<int>({103, 104, 105})
- });
-
- concatenateSimilarQueues(
- ll,
- [](int x) -> bool { return x < 10 || x > 100; }
- );
-
- printLinkedList(ll, printQueue);
- freeList(ll);
-} \ No newline at end of file
diff --git a/Additional/Additional-2022-CS/equalize.cpp b/Additional/Additional-2022-CS/equalize.cpp
deleted file mode 100644
index 263ccd2..0000000
--- a/Additional/Additional-2022-CS/equalize.cpp
+++ /dev/null
@@ -1,60 +0,0 @@
-#include<iostream>
-#include"../Seminar04/linked-list-utils.h"
-#include<stack>
-
-using ListNode = LinkedListNode<std::stack<int>>;
-
-// O(k*n) памет, където n е дължината на списъка а k размера на най - големия стек
-// O(k*n) време
-void equalize(ListNode* ll) {
- std::stack<int> temp;
- ListNode* iter = ll;
-
- while(iter) {
- while(!iter->data.empty()) {
- temp.push(iter->data.top());
- iter->data.pop();
- }
- iter = iter->next;
- }
-
- iter = ll;
-
- while(!temp.empty()) {
- if(iter == nullptr) {
- iter = ll;
- }
- iter->data.push(temp.top());
- temp.pop();
- iter = iter->next;
- }
-}
-
-void printStack(std::stack<int> s) {
- int size = s.size();
-
- std::cout << "[";
-
- while (!s.empty()) {
- std::cout << s.top() << " ";
- s.pop();
- }
-
- std::cout << "] -> " << size << std::endl;
-}
-
-int main() {
- ListNode* ll = fromList(
- {
- std::stack<int>({1, 4}),
- std::stack<int>({6, 7, 8, 9, 5}),
- std::stack<int>({10, 11, 12}),
- std::stack<int>({1, 41}),
- std::stack<int>({6, 7, 8, 9, 5, 7, 9, 0, 10, 20, 30})
- }
- );
-
- equalize(ll);
- printLinkedList(ll, printStack);
- freeList(ll);
-} \ No newline at end of file
diff --git a/Additional/Additional-2022-CS/merge-sorted.cpp b/Additional/Additional-2022-CS/merge-sorted.cpp
deleted file mode 100644
index b801a72..0000000
--- a/Additional/Additional-2022-CS/merge-sorted.cpp
+++ /dev/null
@@ -1,51 +0,0 @@
-#include<iostream>
-#include"../Seminar04/linked-list-utils.h"
-
-using ListNode = LinkedListNode<int>;
-
-ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
- if(list1 == nullptr)
- return list2;
-
- if(list2 == nullptr)
- return list1;
-
- ListNode* start = nullptr;
- ListNode* iter = nullptr;
-
- while(list1 != nullptr && list2 != nullptr) {
- ListNode*& toInsert = (list1->data > list2->data) ? list2 : list1;
-
- if(iter == nullptr) {
- start = toInsert;
- iter = toInsert;
- }
- else {
- iter->next = toInsert;
- iter = iter->next;
- }
-
- toInsert = toInsert->next;
- }
-
- ListNode* rest = (list1 == nullptr) ? list2 : list1;
-
- while(rest != nullptr) {
- iter->next = rest;
- iter = iter->next;
- rest = rest->next;
- }
-
- iter->next = nullptr;
- return start;
-}
-
-int main() {
- ListNode* l1 = new ListNode(1, new ListNode(2, new ListNode(4)));
- ListNode* l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
-
- ListNode* r = mergeTwoLists(l1, l2);
-
- printLinkedList(r);
- freeList(r);
-} \ No newline at end of file
diff --git a/Additional/Additional-2022-CS/oddEvenList.cpp b/Additional/Additional-2022-CS/oddEvenList.cpp
deleted file mode 100644
index 05a95ac..0000000
--- a/Additional/Additional-2022-CS/oddEvenList.cpp
+++ /dev/null
@@ -1,55 +0,0 @@
-#include"../Seminar04/linked-list-utils.h"
-
-using ListNode = LinkedListNode<int>;
-
-ListNode* oddEvenList(ListNode* head) {
- if(head == nullptr || head->next == nullptr)
- return head;
-
- ListNode* oddStart = nullptr;
- ListNode* oddIter = nullptr;
-
- ListNode* evenStart = nullptr;
- ListNode* evenIter = nullptr;
-
- bool odd = true;
-
- while(head) {
- ListNode*& curr = odd ? oddIter : evenIter;
-
- if(curr == nullptr) {
- curr = head;
- if(odd)
- oddStart = head;
- else
- evenStart = head;
- }
- else {
- curr->next = head;
- curr = curr->next;
- }
-
- head = head->next;
- odd = !odd;
- }
-
- oddIter->next = evenStart;
-
- if(evenIter != nullptr)
- evenIter->next = nullptr;
-
- return oddStart;
-}
-
-int main() {
- ListNode* l = fromList({1, 2, 3, 4, 5});
-
- ListNode* result = oddEvenList(l);
- printLinkedList(result);
- freeList(result);
-
- ListNode* ls = fromList({2, 1, 3, 5, 6, 4, 7});
- result = oddEvenList(ls);
- printLinkedList(result);
- freeList(result);
-} \ No newline at end of file
diff --git a/Additional/Additional-2022-CS/rearange.cpp b/Additional/Additional-2022-CS/rearange.cpp
deleted file mode 100644
index 48dacff..0000000
--- a/Additional/Additional-2022-CS/rearange.cpp
+++ /dev/null
@@ -1,55 +0,0 @@
-#include<iostream>
-#include"../Seminar04/linked-list-utils.h"
-
-using ListNode = LinkedListNode<int>;
-
-ListNode* rearange(ListNode* head) {
- ListNode* oddStart = nullptr;
- ListNode* oddIter = nullptr;
-
- ListNode* evenStart = nullptr;
- ListNode* evenIter = nullptr;
-
- while(head != nullptr) {
- if(head->data % 2 == 1) {
- if(oddIter == nullptr) {
- oddStart = head;
- oddIter = head;
- }
- else {
- oddIter->next = head;
- oddIter = oddIter->next;
- }
- }
- else {
- if(evenIter == nullptr) {
- evenStart = head;
- evenIter = head;
- }
- else {
- evenIter->next = head;
- evenIter = evenIter->next;
- }
- }
-
- head = head->next;
- }
-
- if(evenStart == nullptr)
- return oddStart;
-
- evenIter->next = oddStart;
-
- if(oddIter != nullptr)
- oddIter->next = nullptr;
-
- return evenStart;
-}
-
-int main() {
- ListNode* ll = new ListNode(3, new ListNode(5, new ListNode(2, new ListNode(9, new ListNode(4)))));
- ListNode* res = rearange(ll);
-
- printLinkedList(res);
- freeList(res);
-} \ No newline at end of file
diff --git a/Additional/Additional-2022-CS/reverse-nodes-in-k-group.cpp b/Additional/Additional-2022-CS/reverse-nodes-in-k-group.cpp
deleted file mode 100644
index 70b63fd..0000000
--- a/Additional/Additional-2022-CS/reverse-nodes-in-k-group.cpp
+++ /dev/null
@@ -1,54 +0,0 @@
-#include<iostream>
-#include"../Seminar04/linked-list-utils.h"
-
-using ListNode = LinkedListNode<int>;
-
-ListNode* getNext(ListNode* head, int k) {
- while(k && head) {
- head = head->next;
- --k;
- }
-
- return head;
-}
-
-ListNode* reverse(ListNode*& head) {
- ListNode* next = nullptr;
- ListNode* prev = nullptr;
- ListNode* it = head;
- ListNode* tmp = head;
-
- while(it) {
- next = it->next;
- it->next = prev;
- prev = it;
- it = next;
- }
-
- head = prev;
- return tmp;
-}
-
-ListNode* reverseKGroup(ListNode* head, int k) {
- ListNode* end = getNext(head, k - 1);
-
- if(end == nullptr)
- return head;
-
- ListNode* next = end->next;
-
- end->next = nullptr;
-
- ListNode* last = reverse(head);
- ListNode* res = reverseKGroup(next, k);
-
- last->next = res;
- return head;
-}
-
-int main() {
- ListNode* ll = fromList({1, 2, 3, 4, 5, 6, 7,8 ,9,10, 11, 12, 13, 14, 15, 16, 17});
- ll = reverseKGroup(ll, 4);
- printLinkedList(ll);
- freeList(ll);
-} \ No newline at end of file
diff --git a/Additional/Additional-2023-SI/IntervalCollection.cpp b/Additional/Additional-2023-SI/IntervalCollection.cpp
deleted file mode 100644
index 0ac2c76..0000000
--- a/Additional/Additional-2023-SI/IntervalCollection.cpp
+++ /dev/null
@@ -1,103 +0,0 @@
-#include <iostream>
-#include <vector>
-#include <algorithm>
-
-class IntervalCollection
-{
- using Iterator = std::vector<std::pair<int, int>>::iterator;
- using ConstIterator = std::vector<std::pair<int, int>>::const_iterator;
-
- Iterator getRightmostInterval(int x)
- {
- std::pair<int, int> searcher = { x, x };
- return std::lower_bound(
- intervals.begin(),
- intervals.end(),
- searcher,
- [](const std::pair<int, int>& first, const std::pair<int, int>& second) -> bool
- {
- return first.second < second.second;
- }
- );
- }
-
- ConstIterator getRightmostIntervalConst(int x) const
- {
- std::pair<int, int> searcher = { x, x };
- return std::lower_bound(
- intervals.begin(),
- intervals.end(),
- searcher,
- [](const std::pair<int, int>& first, const std::pair<int, int>& second) -> bool
- {
- return first.second < second.second;
- }
- );
- }
-
-public:
- void insert(int x)
- {
- Iterator right = getRightmostInterval(x);
- bool begin = (right == intervals.begin());
-
- Iterator left = begin ? intervals.end() : right - 1;
-
- bool needLeftMerge = !begin && (x - 1 == left->second);
- bool needRightMerge = (right != intervals.end()) && (x + 1 == right->first);
-
- if (right != intervals.end() && x >= right->first && x <= right->second)
- {
- return;
- }
-
- if (needLeftMerge && needRightMerge)
- {
- left->second = right->second;
- intervals.erase(right);
- }
- else if (needLeftMerge)
- {
- left->second = x;
- }
- else if (needRightMerge)
- {
- right->first = x;
- }
- else
- {
- intervals.insert(right, { x, x });
- }
- }
-
- bool contains(int x) const
- {
- ConstIterator right = getRightmostIntervalConst(x);
- return (right != intervals.end() && x >= right->first && x <= right->second);
- }
-
- void print() const
- {
- for (const auto& x : intervals)
- {
- std::cout << x.first << " " << x.second << std::endl;
- }
- }
-private:
- std::vector<std::pair<int, int>> intervals;
-};
-
-int main()
-{
- IntervalCollection ic;
-
- ic.insert(1);
- ic.insert(3);
- ic.insert(2);
- ic.insert(5);
- ic.insert(7);
- ic.insert(4);
- ic.insert(6);
-
- std::cout << ic.contains(1) << " " << ic.contains(10);
-} \ No newline at end of file
diff --git a/Additional/Additional-2023-SI/MergeIntoList.cpp b/Additional/Additional-2023-SI/MergeIntoList.cpp
deleted file mode 100644
index 7d575aa..0000000
--- a/Additional/Additional-2023-SI/MergeIntoList.cpp
+++ /dev/null
@@ -1,117 +0,0 @@
-#include <iostream>
-
-struct ListNode
-{
- int val;
- ListNode *next;
- ListNode(int x, ListNode *n = nullptr) : val(x), next(n) {}
-};
-
-ListNode *advance(ListNode *from, size_t index)
-{
- while (index)
- {
- if (from == nullptr)
- {
- return nullptr;
- }
-
- from = from->next;
- --index;
- }
-
- return from;
-}
-
-ListNode *getTail(ListNode *list)
-{
- if (!list || !list->next)
- {
- return list;
- }
-
- while (list->next)
- {
- list = list->next;
- }
- return list;
-}
-
-void freeRagne(ListNode *from, ListNode *to)
-{
- while (from != to)
- {
- ListNode *node = from;
- from = from->next;
- delete node;
- }
-}
-
-void free(ListNode *ll)
-{
- while (ll)
- {
- ListNode *toDelete = ll;
- ll = ll->next;
- delete toDelete;
- }
-}
-
-ListNode *addFront(ListNode *destination, ListNode *target, size_t to)
-{
- ListNode *tail = getTail(target);
- ListNode *end = advance(destination, to + 1);
- tail->next = end;
- freeRagne(destination, end);
- return target;
-}
-
-ListNode *mergeInBetween(ListNode *destination, ListNode *target, size_t from, size_t to)
-{
- if (from == 0)
- {
- return addFront(destination, target, to);
- }
-
- ListNode *predBegin = advance(destination, from - 1);
- if (!predBegin)
- {
- return nullptr;
- }
-
- ListNode *postEnd = advance(predBegin, to - from + 2);
- ListNode *toDeleteHolder = predBegin->next;
- ListNode *targetTail = getTail(target);
-
- predBegin->next = target;
- targetTail->next = postEnd;
-
- freeRagne(toDeleteHolder, postEnd);
-
- return destination;
-}
-
-int main()
-{
- ListNode *fst = new ListNode(1,
- new ListNode(2,
- new ListNode(3,
- new ListNode(4,
- new ListNode(6)))));
-
- ListNode *snd = new ListNode(3,
- new ListNode(4,
- new ListNode(5)));
-
- ListNode *ans = mergeInBetween(fst, snd, 1, 3);
-
- ListNode *it = ans;
-
- while(it)
- {
- std::cout << it->val << " ";
- it = it->next;
- }
-
- free(ans);
-} \ No newline at end of file
diff --git a/Additional/Additional-2023-SI/queue-insertion.cpp b/Additional/Additional-2023-SI/queue-insertion.cpp
deleted file mode 100644
index f27416a..0000000
--- a/Additional/Additional-2023-SI/queue-insertion.cpp
+++ /dev/null
@@ -1,109 +0,0 @@
-#include <iostream>
-
-struct Node
-{
- Node* next = nullptr;
- int data = 0;
- Node(int data, Node* next = nullptr) : data(data), next(next){}
-};
-
-struct Queue
-{
- Node* head = nullptr;
- Node* tail = nullptr;
-};
-
-void push(Queue& q, int el)
-{
- if (q.head == nullptr)
- q.head = q.tail = new Node(el);
- else
- {
- Node* newNode = new Node(el);
- q.tail->next = newNode;
-
- q.tail = newNode;
- }
-}
-void pop(Queue& q)
-{
- if (!q.head)
- return;
- Node* toDelete = q.head;
- q.head = q.head->next;
- delete toDelete;
-}
-
-void insert(Queue& q, int el)
-{
- Node* iter = q.head;
-
- while (iter)
- {
- if (iter->data % 10 == el % 10)
- {
- break;
- }
- iter = iter->next;
- }
-
- if (iter)
- {
- Node* newNode = new Node(el);
- newNode->next = iter->next;
- iter->next = newNode;
- }
- else
- {
- if (!q.head)
- {
- Node* newNode = new Node(el);
- q.head = q.tail = newNode;
- }
- else
- {
- Node* newNode = new Node(el);
- q.tail->next = newNode;
- q.tail = newNode;
- }
- }
-}
-
-void print(const Queue& q)
-{
- const Node* it = q.head;
-
- while(it)
- {
- std::cout << it->data << " ";
-
- it = it->next;
- }
-}
-void free(Queue& q)
-{
- while (q.head)
- {
- Node* toDelete = q.head;
- q.head = q.head->next;
-
- delete toDelete;
- }
-
-}
-int main()
-{
- Queue q;
-
- push(q, 1);
- push(q, 2);
- push(q, 4);
- push(q, 8);
- push(q, 16);
-
- insert(q, 12);
-
- print(q);
-
- free(q);
-} \ No newline at end of file
diff --git a/Additional/Additional-2023-SI/readme.md b/Additional/Additional-2023-SI/readme.md
deleted file mode 100644
index 8ffe953..0000000
--- a/Additional/Additional-2023-SI/readme.md
+++ /dev/null
@@ -1,13 +0,0 @@
-## Разгледани структури от STL
-
-* std::vector
-* std::list
-* std::forward_list
-
-## Разгледани функции от STL
-* std::sort()
-* std::lower_bound()
-* std::upper_bound()
-* std::find()
-* std::find_if()
-* std::list::splice \ No newline at end of file
diff --git a/Additional/Additional-2023-SI/rearrange.cpp b/Additional/Additional-2023-SI/rearrange.cpp
deleted file mode 100644
index e5ad080..0000000
--- a/Additional/Additional-2023-SI/rearrange.cpp
+++ /dev/null
@@ -1,112 +0,0 @@
-#include <iostream>
-
-struct Node
-{
- Node* next = nullptr;
- Node* prev = nullptr;
- int data = 0;
- Node(int data, Node* next = nullptr, Node* prev = nullptr) : data(data), next(next), prev(prev) {}
-};
-
-Node* rearange(Node* head)
-{
- Node* evensBegin = nullptr;
- Node* evensEnd = nullptr;
- Node* oddsBegin = nullptr;
- Node* oddsEnd = nullptr;
-
- Node* iter = head;
-
- while (iter)
- {
- if (iter->data % 2 == 0)
- {
- if (!evensBegin)
- {
- evensBegin = evensEnd = iter;
- iter->prev = nullptr;
- }
- else
- {
- evensEnd->next = iter;
- iter->prev = evensEnd;
- evensEnd = iter;
- }
- }
- else
- {
- if (!oddsBegin)
- {
- oddsBegin = oddsEnd = iter;
- iter->prev = nullptr;
- }
- else
- {
- oddsEnd->next = iter;
- iter->prev = oddsEnd;
- oddsEnd = iter;
- }
- }
- iter = iter->next;
- }
- if(evensEnd)
- evensEnd->next = nullptr;
- if(oddsEnd)
- oddsEnd->next = nullptr;
-
- // concat
- if (!evensBegin)
- return oddsBegin;
- if (!oddsBegin)
- return evensBegin;
-
- evensEnd->next = oddsBegin;
- oddsBegin->prev = evensEnd;
- return evensBegin;
-}
-
-Node* push_front(Node* list, int elem)
-{
- if(!list)
- {
- return new Node(elem);
- }
-
- Node* toReturn = new Node(elem, list);
- list->prev = toReturn;
- return toReturn;
-}
-
-void free(Node* l)
-{
- Node* it = l;
-
- while(it)
- {
- Node* toDelete = it;
- it = it->next;
- delete toDelete;
- }
-}
-
-int main()
-{
- Node* l = nullptr;
-
- for (size_t i = 0; i < 50; i++)
- {
- l = push_front(l, 50 - i);
- }
-
- l = rearange(l);
-
- Node* it = l;
-
- while(it)
- {
- std::cout << it->data << " ";
- it = it->next;
- }
-
- free(l);
-} \ No newline at end of file
diff --git a/README.md b/README.md
index 7ee2d10..aaf19b5 100644
--- a/README.md
+++ b/README.md
@@ -1,15 +1 @@
-# Код от семинаритe по СДП - Компютърни науки
-* Тема 1: Технически преговор - указатели и памет. Дефиниция на структура от данни. Сложност.
-* Тема 2: Стек.
-* Тема 3: Опашки и декове.
-* Тема 4: Динамичен масив. Свързан списък (част 1).
-* Тема 5: Итератори. std::list. Задачи за упражнение [тук най-долу](Seminar05/README.md)
-* Тема 6: Двойно свързани списъци. Задачи върху списъци. [Упражнение - реализирайте двойно свързан списък](Seminar06/DLLSkeleton.cpp)
-* Тема 7: Сортиращи алгоритми.
-* Тема 8: Дървета. Двоични дървета. Двоични наредени дървета.
-* Тема 9: Дървета 2. Балансирани дървета. Ротации. Задачи върху дървета.
-* Тема 10: Самобалансиращи се дървета. AVL дървета. std::set, std::multiset, std::map, std::multimap
-* Тема 11: Графи. BFS и DFS.
-* Тема 12: Пътища в графи. Най - къси пътища в графи.
-* Тема 13: Задачи върху графи.
-* Тема 14: Речници. Хеш таблици. \ No newline at end of file
+# Код от семинаритe по структури от данни 2024/2025 - Информационни системи \ No newline at end of file
diff --git a/Seminar01/README.md b/Seminar01/README.md
deleted file mode 100644
index 47f9f83..0000000
--- a/Seminar01/README.md
+++ /dev/null
@@ -1,74 +0,0 @@
-# Указатели и памет.
-
-## Указатели и референции. Работа с памет.
-Указателите, които вече добре познаваме, са променливи, които съхраняват адреса на обект в паметта. Указателите най - често са използвани за:
-* Да заделяме динамично памет в heap-а
-* Итерираме елементите на масив или друга структура от данни
-* Подаваме функции като аргументи на други функции
-
-и много други.
-
-Указателите са удобен и изключително гъвкав инструмент, с който често ще ни се налага да работим.
-Нека разгледаме следния сценарий.
-```c++
-int main() {
- int a = 10;
- int b = 12;
- int* ptr = &a;
-}
-```
-Искаме да напишем функция, която приема указател и променлива и кара указателя да сочи към адреса на тази променлива. Дали следния код ще свърши работа:
-```c++
-#include<iostream>
-
-void redirect(int* ptr, int dest) {
- ptr = &dest;
-}
-
-int main() {
- int a = 10;
- int b = 12;
- int* ptr = &a;
-
- redirect(ptr, b);
- std::cout << *ptr; // *ptr връща стойността записана в този адрес
-}
-```
-Очевидно това не сработи, но защо? Във функцията *redirect* на *ptr* се прави **копие**. После това копие започва да сочи към *dest*, но на нас това не ни помага! Ние искаме да пренасочим **самия указател а не неговото копие**. Тук на помощ идват референциите (или псевдонимите). Ако пренапишем функцията по следния начин
-
-```c++
-void redirect(int*& ptr, int& dest) {
- ptr = &dest;
-}
-```
-то вече функцията върши желаната работа. Когато приемаме обект по референция **копие не се прави**. Това важи за всички типове - включително и за указателите.
-Можем да правим указатели към всякакви типове включително и към указатели. Типът **int\*\*** не е нищо повече от указател към указател.
-
-Тогава не можем ли просто да вземем указател към указателя и да го променим по този начин?
-```c++
-#include<iostream>
-
-void redirect(int** ptr, int& dest) {
- *ptr = &dest;
-}
-
-int main() {
- int a = 10;
- int b = 12;
- int* ptr = &a;
-
- redirect(&ptr, b); // &ptr връща адреса на указателя, точно това което е int**, адрес на указател.
- std::cout << *ptr;
-}
-```
-
-Този код също върши работа. Тогава каква е разликата между указател и референция?
-Разликата е, че указателите са по - гъвкави. Не можем да пренасочим референция. Също така не можем да имаме референция която не сочи към обект. При указателите имаме специален тип наречен nullptr, който сочи към "нищото". Често референцията е представяна като указател, който не може да се пренасочва, вика \* вместо теб и винаги сочи към обект.
-
-## const и указателите
-За *const* важи следното правило - *const* винаги модифицира това което е в негово ляво, освен когато няма нищо отляво, тогава модифицира това което е отдясно.
-
-* const int\* -> Указател, който сочи към константен *int*. Можем да пренасочваме, но не можем да променяме стойността.
-* int const\* -> Абсолютно същото.
-* int \* const -> Константен указател, не можем да го пренасочваме.
-* const int\* const -> Константен указател към константен *int*. Нито можем да пренасочваме нито да променяме стойността.
diff --git a/Seminar01/Сложност.pdf b/Seminar01/Сложност.pdf
deleted file mode 100644
index cbc734f..0000000
--- a/Seminar01/Сложност.pdf
+++ /dev/null
Binary files differ
diff --git a/Seminar02/README.md b/Seminar02/README.md
deleted file mode 100644
index d1779b2..0000000
--- a/Seminar02/README.md
+++ /dev/null
@@ -1,92 +0,0 @@
-# Задачи за стекове 12.10.22
-
-## Задача първа
-Имаме низ състоящ се от английски букви и символа \*. Всеки път когато видим \* трябва да премахнем символът отляво както и самата звезда.
-Пример:
-* aa\* -> "a"
-* erase\*\*\*\*\* -> ""
-* thi\*s i\*s exampl\*e -> "ths s exampe"
-
-Задачата да се реализира за линейно време с линейна памет.
-## Задача втора
-* Вход: Низ състоящ се от отварящи и затварящи скоби.
-* Изход: Дали скобите в този низ са балансирани
-
-Примери:
-* ((())) -> true
-* ))() -> false
-* )( -> false
-* ()()(()) -> true
-
-## Задача трета
-Обратен полски запис наричаме запис, в който операторите "следват" (са след) числата. Примерно изразът 3 + 4 в обратна полска нотация е 3 4 +. Или изразът 1−2+3 би изглеждал 1 2 −3+. Обикновено първо са дадени числата а след това операциите които извършваме върху тях.
-
-А как би изглеждал израза 1−(2+3). Тук първо трябва да извършим събирането и след това изваждането. Тоест израза се записва като 123+−. Предимството от тази нотация е, че нямаме нужда от скоби, което ускорява сметките. Нашата задача е да напишем функция, която приема валиден стринг в обратна полска нотация и връща пресметнатия резултат.
-
-
-# Монотонни стекове
-Монотонен стек наричаме стек, чиито елементи са монотонно растящи или намаляващи. Монотонните стекове имат приложения върхо много различни и интересни задачи върху масиви.
-
-```cpp
-void monotonicStackExample(const std::vector<int>& v) {
- // Нека v = {4, 1, 2, 6, 7, 3}
- // В стека можем да пазим стойности или индекси в зависимост от задачата.
- // По името може да познаете какво пазим и какъв е типа на стека.
- std::stack<int> minMonotonicValues;
-
- for(int i = 0; i < v.size(); i++) {
- while(!minMonotonicValues.empty() && minMonotonicValues.top() < v[i]) {
- minMonotonicValues.pop();
- }
- minMonotonicValues.push(v[i]);
- }
-
- /*
- В края на for цикъла при индекс i стека изглежда така:
- (върха на стека е най - десния елемент)
- i = 0 : [4]
- i = 1 : [4, 1]
- i = 2 : [4, 2]
- i = 3 : [6]
- i = 4 : [7]
- i = 5 : [7, 3]
- */
-}
-```
-Какво можем да забележим от този пример? Примерно, вярно е, че при i = k максимума на подмасива [0..k - 1] е на дъното на стека.
-
-## Задача четвърта
-Искаме да създадем статична структура от данни построена върху масив, която за константно време по индекс ни връща стойността на първия елемент намиращ се вляво от този индекс и имащ стойност по - голяма или равна от елемента на дадения индекс.
-
-Пример:
-> [1, 4, 3, 8, 12, 7]
-* getMinLeft(0) -> -1 // няма по - голям елемент от 1 в негово ляво
-* getMinLeft(2) -> 4 // 4 е първия елемент по - голям от arr[2] = 3
-* getMinLeft(5) -> 12 // 12 е първия елемент по - голям от arr[5] = 7
-
-## Обяснение на решението:
-От тази задача можем да си направим извода, че точно преди да вкараме елемента в монотонния стек, върха на стека е първия елемент намиращ се вляво от този индекс и имащ стойност по - голяма или равна от елемента на дадения индекс.
-
-Защо това е вярно?
-Нека
-
-$$arr = [a_1 \dots a_k \dots a_m \dots a_n]$$
-
-и нека в цикъла i = m. Твърдя, че ако $a_k$ е първото по - голямо число от $a_m$ то ще бъде задължително на върха на стека след приключване на while цикъла.
-
-
-Ако има други числа на върха на стека, то по предположение те са по - малки от $a_m$ и ще бъдат премахнати.
-
-Ами ако $a_k$ не е в стека? Ако то не е в стека то някое по - голямо от него число, намиращо се между $a_k$ и $a_m$, го е премахнало. Тоест то не е първото по - голямо число намиращо се вляво.
-
-## Бонус задачи
-1. Да се сортира стек като използвате само един допълнителен стек.
-
-2. Да се направи задачата със скобите, обаче този път функцията ни казва дали е възможно низът да стане балансиран след най - много едно изтриване на скоба.
-
-Пример:
-* )) -> false
-* ()) -> true
-* () -> true
-* (()()() -> true
-* ())) -> false \ No newline at end of file
diff --git a/Seminar02/bonusTask01.cpp b/Seminar02/bonusTask01.cpp
deleted file mode 100644
index 6e41016..0000000
--- a/Seminar02/bonusTask01.cpp
+++ /dev/null
@@ -1,51 +0,0 @@
-#include <iostream>
-#include <stack>
-
-void sortStack(std::stack<int> &first)
-{
- std::stack<int> second;
- int currentElement = 0;
- while (!first.empty())
- {
- currentElement = first.top();
- first.pop();
-
- while (!second.empty() && second.top() > currentElement)
- {
- first.push(second.top());
- second.pop();
- }
- second.push(currentElement);
- }
-
- while (!second.empty())
- {
- first.push(second.top());
- second.pop();
- }
-}
-
-void stackPrint(std::stack<int> st)
-{
- while (!st.empty())
- {
- std::cout << st.top() << " ";
- st.pop();
- }
- std::cout << std::endl;
-}
-
-int main()
-{
- std::stack<int> st;
- st.push(8);
- st.push(2);
- st.push(4);
- st.push(1);
- st.push(5);
- st.push(3);
-
- stackPrint(st);
- sortStack(st);
- stackPrint(st);
-} \ No newline at end of file
diff --git a/Seminar02/recursion.cpp b/Seminar02/recursion.cpp
deleted file mode 100644
index 63f4aa0..0000000
--- a/Seminar02/recursion.cpp
+++ /dev/null
@@ -1,33 +0,0 @@
-#include<iostream>
-#include<stack>
-
-int fib(unsigned x) {
- if(x == 0 || x == 1)
- return 1;
-
- return fib(x - 1) + fib(x - 2);
-}
-
-// Малък пример как можем да симулираме рекурсия чрез стек.
-int fibStack(unsigned x) {
- std::stack<unsigned> s;
- s.push(x);
- int result = 0;
-
- while(!s.empty()) {
- int currArg = s.top();
- s.pop();
-
- if(currArg == 1 || currArg == 0)
- ++result; // Еквивалентно на return 1;
- else{
- s.push(currArg - 1); // Еквивалентно на fib(x - 1);
- s.push(currArg - 2); // Еквивалентно на fib(x - 2);
- }
- }
- return result;
-}
-
-int main() {
- std::cout << fib(10) << " " << fibStack(10);
-}
diff --git a/Seminar02/task01.cpp b/Seminar02/task01.cpp
deleted file mode 100644
index 288b3b5..0000000
--- a/Seminar02/task01.cpp
+++ /dev/null
@@ -1,51 +0,0 @@
-#include<string>
-#include<stack>
-#include<iostream>
-
-std::string removeStars(const std::string& s) {
- std::stack<char> st;
-
- for (int i = 0; i < s.size(); i++) {
- if (s[i] == '*') {
- if (st.empty())
- throw "invalid expr";
- else
- st.pop();
- }
- else
- st.push(s[i]);
- }
-
- std::string res(st.size(), '\0');
- size_t idx = st.size() - 1;
-
- while (!st.empty()) {
- res[idx--] = st.top();
- st.pop();
- }
-
- return res;
-}
-
-std::string removeStarsTwo(const std::string& str) {
- // As we are using only push_back and pop_back here
- // the std::string is equivalent to a stack
- // and we save up some time and memory.
- std::string result;
-
- for(char c : str) {
- if(c == '*') {
- result.pop_back();
- }
- else {
- result.push_back(c);
- }
- }
-
- return result;
-}
-
-
-int main() {
-
-}
diff --git a/Seminar02/task02.cpp b/Seminar02/task02.cpp
deleted file mode 100644
index 108e1f1..0000000
--- a/Seminar02/task02.cpp
+++ /dev/null
@@ -1,24 +0,0 @@
-#include<iostream>
-#include<stack>
-#include<string>
-
-bool isStringBalanced(const std::string& str) {
- std::stack<char> s;
-
- for (size_t i = 0; i < str.size(); i++)
- {
- if(str[i] == ')'){
- if(s.empty())
- return false;
- s.pop();
- }
- else {
- s.push(str[i]);
- }
- }
- return s.empty();
-}
-
-int main() {
- std::cout << isStringBalanced("((()))(((");
-}
diff --git a/Seminar02/task03.cpp b/Seminar02/task03.cpp
deleted file mode 100644
index 1c7a095..0000000
--- a/Seminar02/task03.cpp
+++ /dev/null
@@ -1,59 +0,0 @@
-#include<iostream>
-#include<stack>
-#include<string>
-#include<cassert>
-
-bool isOperation(char c) {
- return (c == '+') || (c == '-') || (c == '*') || (c == '/');
-}
-
-bool isDigit(char c) {
- return c >= '0' && c <= '9';
-}
-
-int eval(int fst, int snd, char op) {
- assert(isOperation(op));
-
- switch (op) {
- case '+':
- return fst + snd;
- case '-':
- return fst - snd;
- case '*':
- return fst * snd;
- case '/':
- return fst / snd;
- }
-}
-
-int RPN(const std::string& str) {
- std::stack<int> numbers;
-
- for (size_t i = 0; i < str.size(); i++) {
- if(isOperation(str[i])) {
- int snd = numbers.top();
- numbers.pop();
-
- int fst = numbers.top();
- numbers.pop();
-
- numbers.push(eval(fst, snd, str[i]));
- }
- else if(str[i] != ' ') {
- int number = 0;
- while(i < str.size() && isDigit(str[i])) {
- number *= 10;
- number += str[i] - '0';
- i++;
- }
- i--;
- numbers.push(number);
- }
- }
-
- return numbers.top();
-}
-
-int main() {
- std::cout << RPN("9 3 4 * - 2 5 * -");
-} \ No newline at end of file
diff --git a/Seminar02/task04.cpp b/Seminar02/task04.cpp
deleted file mode 100644
index 91207a0..0000000
--- a/Seminar02/task04.cpp
+++ /dev/null
@@ -1,47 +0,0 @@
-#include<iostream>
-#include<stack>
-#include<vector>
-
-class firstLeftGreaterElement {
-private:
- std::vector<int> data;
-
- void init(const std::vector<int>& v) {
- std::stack<int> monotonicStack;
-
- data.resize(v.size());
-
- for (size_t i = 0; i < v.size(); i++) {
- while(!monotonicStack.empty() && monotonicStack.top() < v[i]) {
- monotonicStack.pop();
- }
-
- data[i] = monotonicStack.empty() ? -1 : monotonicStack.top();
- monotonicStack.push(v[i]);
- }
- }
-
-public:
- firstLeftGreaterElement(const std::vector<int>& v) {
- init(v);
- }
-
- int getFirstLeftGreaterElement(size_t idx) const {
- return data[idx];
- }
-};
-
-int main() {
- std::vector<int> example {4, 7, 2, 3, 12, 6, 4, 13};
- std::vector<int> example2 {1, 4, 3, 8, 12, 7};
-
- firstLeftGreaterElement f(example);
- firstLeftGreaterElement s(example2);
-
- for (size_t i = 0; i < example.size(); i++)
- std::cout << f.getFirstLeftGreaterElement(i) << " ";
-
- std::cout << std::endl;
-
- std::cout << s.getFirstLeftGreaterElement(0) << " " << s.getFirstLeftGreaterElement(2) << " " << s.getFirstLeftGreaterElement(5);
-} \ No newline at end of file
diff --git a/Seminar02/Стек.pdf b/Seminar02/Стек.pdf
deleted file mode 100644
index fdd03a9..0000000
--- a/Seminar02/Стек.pdf
+++ /dev/null
Binary files differ
diff --git a/Seminar03/Linked-Queue.hpp b/Seminar03/Linked-Queue.hpp
deleted file mode 100644
index 325f4c4..0000000
--- a/Seminar03/Linked-Queue.hpp
+++ /dev/null
@@ -1,162 +0,0 @@
-#ifndef LINKED_QUEUE_IMPL
-#define LINKED_QUEUE_IMPL
-
-#include<cstddef>
-
-template<class T>
-class LinkedQueue {
-private:
- struct LinkedNode {
- T data;
- LinkedNode* next;
-
- LinkedNode(const T& argData, LinkedNode* argNext = nullptr) : data {argData}, next{argNext} {}
- };
-
- LinkedNode* head; // Първия добавен елемент в опашката
- LinkedNode* tail; // Последния добавен елемент в опашката
- size_t queueSize;
-
- void copy(const LinkedQueue<T>&);
- void free();
-
-public:
- LinkedQueue();
-
- LinkedQueue(const LinkedQueue<T>&);
- LinkedQueue& operator=(const LinkedQueue<T>&);
-
- LinkedQueue(LinkedQueue<T>&&) noexcept;
- LinkedQueue& operator=(LinkedQueue<T>&&) noexcept;
-
- void push(const T&);
- void pop();
- const T& front() const;
-
- bool empty() const;
-
- size_t size() const;
-
- ~LinkedQueue();
-};
-
-template<class T>
-LinkedQueue<T>::LinkedQueue() : head {nullptr}, tail{nullptr}, queueSize{0} {}
-
-template<class T>
-LinkedQueue<T>::LinkedQueue(const LinkedQueue<T>& other) {
- copy(other);
-}
-
-template<class T>
-LinkedQueue<T>& LinkedQueue<T>::operator=(const LinkedQueue<T>& other) {
- if(this != &other){
- free();
- copy(other);
- }
-
- return *this;
-}
-
-template<class T>
-LinkedQueue<T>::LinkedQueue(LinkedQueue<T>&& other) noexcept {
- head = other.head;
- tail = other.tail;
- size = other.size;
-
- other.head = nullptr;
- other.tail = nullptr;
-}
-
-template<class T>
-LinkedQueue<T>& LinkedQueue<T>::operator=(LinkedQueue<T>&& other) noexcept {
- if(this != &other) {
- head = other.head;
- tail = other.tail;
- size = other.size;
-
- other.head = nullptr;
- other.tail = nullptr;
- }
- return *this;
-}
-
-template<class T>
-void LinkedQueue<T>::copy(const LinkedQueue<T>& other) {
- LinkedNode* iter = other.head;
-
- while(iter) {
- push(iter->data);
- iter = iter->next;
- }
-}
-
-template<class T>
-void LinkedQueue<T>::free() {
- LinkedNode* iter = head;
- while(iter) {
- LinkedNode* removeMe = iter;
- iter = iter->next;
- delete removeMe;
- }
-}
-
-template<class T>
-bool LinkedQueue<T>::empty() const {
- return head == nullptr;
-}
-
-template<class T>
-size_t LinkedQueue<T>::size() const {
- return queueSize;
-}
-
-template<class T>
-void LinkedQueue<T>::push(const T& elem) {
- LinkedNode* toPush = new LinkedNode(elem);
- if(empty()) {
- tail = toPush;
- head = toPush;
- }
- else {
- tail->next = toPush;
- tail = toPush;
- }
-
- ++queueSize;
-}
-
-template<class T>
-void LinkedQueue<T>::pop() {
- if(empty()) {
- throw "Empty queue";
- }
- else if(head == tail) {
- delete head;
- head = nullptr;
- tail = nullptr;
- }
- else {
- LinkedNode* deleteMe = head;
- head = head->next;
- delete deleteMe;
- }
-
- --queueSize;
-}
-
-template<class T>
-const T& LinkedQueue<T>::front() const {
- if(empty()){
- throw "Empty queue";
- }
-
- return head->data;
-}
-
-template<class T>
-LinkedQueue<T>::~LinkedQueue() {
- free();
-}
-
-#endif
diff --git a/Seminar03/QueueTests.cpp b/Seminar03/QueueTests.cpp
deleted file mode 100644
index 221a09a..0000000
--- a/Seminar03/QueueTests.cpp
+++ /dev/null
@@ -1,28 +0,0 @@
-#include"Linked-Queue.hpp"
-#include<cassert>
-#include<iostream>
-
-void runTest() {
- LinkedQueue<int> q;
-
- for (size_t i = 0; i < 1000; i++)
- q.push(i);
-
- std::cout << "Passed size test" << std::endl;
- assert(q.size() == 1000);
-
- for (size_t i = 0; i < 1000; i++) {
- assert(q.front() == i);
- q.pop();
- }
-
- std::cout << "Push, pop and top working as expected" << std::endl;
-
- assert(q.empty() && q.size() == 0);
-
- std::cout << "Passed empty test" << std::endl;
-}
-
-int main() {
- runTest();
-}
diff --git a/Seminar03/README.md b/Seminar03/README.md
deleted file mode 100644
index dc36329..0000000
--- a/Seminar03/README.md
+++ /dev/null
@@ -1,185 +0,0 @@
-# Опашка
-Опашката е линейна структура от данни, която работи на принципа FIFO (first in first out). Опашката отговаря точно на представата за реална опашка.
-Операции:
-* Enqueue (или push) - добавя елемент в края на опашката
-* Dequeue (или pop) - премахва първия добавен елемент в опашката
-* Front - връща първия елемент в опашката
-
-Опционални операции към интерфейса:
-* empty() - Връща дали опашката е празна или не
-* size() - Връща размера на опашката
-
-В STL имаме готова реализация на опашка. Тя се намира в библиотеката \<queue> и се създава чрез std::queue\<T>.
-Пример:
-```cpp
-#include<iostream>
-#include<queue>
-
-int main() {
- std::queue<int> q;
-
- q.push(1);
- q.push(2);
- q.push(3);
- q.push(4);
-
- std::cout << q.front(); // Извежда 1
- q.pop() // Премахва 1 от опашката
- std::cout << q.front(); // Извежда 2
- q.pop(); // Премахва 2 от опашката
- q.pop(); // Премахва 3 от опашката
-}
-```
-
-## Приложения
-Едно от основните приложения на опашката е използването ѝ в различни алгоритми за обхождане на графи, като най - ясен пример за това би бил алгоритъма BFS. Други алгоритми върху графи също използват опашка (или нейни разновидности) за да обхождат графа и да решават различни задачи върху него.
-Опашките също намират голямо приложение в операционните системи и компютърните мрежи.
-
-## Начини за реализация
-### Свързани компоненти
-
-Представяме елемента на опашката по следния начин:
-```cpp
-template<class T>
-struct QueueNode {
- T data;
- QueueNode<T>* next;
-}
-```
-В класа представящ опашка пазим два указателя, head и tail:
-```cpp
-template<class T>
-class LinkedQueue {
- QueueNode<T>* head; // Представлява първия елемент, който е добавен.
- QueueNode<T>* tail; // Представлява последния елемент, който е добавен.
-}
-```
-![](media/qexample.png)
-При такова представяне как биха изглеждали алгоритмите за добавяне и премахване?
-
-### Чрез масив
-Можем да представим опашката чрез статичен или динамичен масив и два индекса - към първия и последния елемент добавен към опашката.
-![](media/arr-queue.png)
-
-При такова представяне как биха изглеждали алгоритмите за добавяне и премахване? Дали след като запълним последната клетка на масива повече няма да можем да добавим елемент в опашката?
-
-# Декове
-Декът или deque (от double ended queue) е линейна структура от данни, за която можем да си мислим като опашка, позволяваща добавяне и премахване на елементи и от двете страни.
-
-Операции:
-* push_front(x) - Добавя x в началото
-* push_back(x) - Добавя х в края
-* pop_back() - Премахва последния елемент
-* pop_front() - Премахва първия елемент
-
-*A deque ("double ended queue") is a linear list for which all insertions and deletions (and usually all accesses) are made at the ends of the list*.
-
-Стандартната библиотека ни предлага реализация на дек. Тази реализация обаче трябва да се използва внимателно. Примерно, std::deque ни позволява достъп на произволен елемент в колекцията. Това, дори да изглежда като функционалност, която не бихме отказали, често може да доведе до различен тип грешки.
-
-Пример:
-```cpp
-#include<deque>
-
-int main() {
- std::deque<int> dq;
-
- dq.push_front(1);
- dq.push_back(2);
-
- dq[0] = 10;
- // Позволява промяна, но доста често такава промяна е безсмислена.
- // Наложи ли ви се да правите такава промяна
- // вероятно използвате грешната структура от данни.
- dq[3] = 1;
- // Какво става когато такъв елемент няма?
- // Отговорът е зависи - недефинирано поведение (undefined behaviour).
-}
-```
-
-# Неща, които използвам в решението на задачите
-
-## Статични масиви и std::array
-Всички знаем, че статичният масив е бърза и удобна структура от данни. STL ни предлага готова реализация на статичен масив. Тя се намира в библиотеката \<array>.
-Пример:
-```cpp
-#include<array>
-
-int main() {
- std::array<int, 10> arr;
- arr[0] = 42;
-}
-```
-В случая arr се държи като нормален статичен масив, но идва с допълнителни помощни функции и поддържа логика за итератори.
-
-## Нетипови параметри
-Нетиповите параметри често се използват за определяне на някакви максимуми, минимуми или константи свързани с класа. Примерно, нека имаме следния код:
-
-```cpp
-const size_t MAX_SIZE = 100;
-
-template<class T>
-class staticArray {
- T data[MAX_SIZE];
-}
-```
-Това върши работа до момента в който не ни потрябват два различни варианта на staticArray - един с максимум елемента 100 а втория с максимум 50. Този проблем се решава чрез нетипови параметри по следния начин:
-```cpp
-template<class T, size_t maxSize>
-class staticArray {
- T data[maxSize];
-}
-```
-Сега много лесно мога да си направя два статични масива с различна горна граница:
-
-```cpp
-int main() {
- staticArray<int, 50> fst;
- staticArray<int, 100> snd;
-}
-```
-Тук компилаторът няма да ни се скара, понеже maxSize задължително трябва да е константа.
-Едно хубаво свойство на нетиповите параметри е, че `staticArray<T, 50>` и `staticArray<T, 100>` са два различни типа.
-
-# Задачи
-
-## Задача първа
-Да се напише функция, която генерира всички двоични числа от 1 до n, използвайки опашка.
-
-Пример:
-> n = 10 ➡ 1 10 11 100 101 110 111 1000 1001 1010
-
-## Задача втора
-Конче стои върху шахматна дъска NxN. За начална и крайна позиция да се изведе с колко най - малко хода можем да стигнем от началната до крайната.
-
-Пример:
-> {(0, 0), (2, 1)} -> 1
->
-> {(0, 0), (7, 7)} -> 6
-
-## Задача трета - Sliding window maximum
-Даден е масив от цели числа. Представяме си, че имаме прозорец с дължина *k* който се движи отляво надясно. Единственото което можем да видим са числата в прозореца. Да се изведе максимумът на всеки такъв прозорец.
-
-Пример:
-
-> Вход: **[1, 3, -1, -3, 5, 3, 6, 7]**, k = 3
->
-> Output: [3, 3, 5, 5, 6, 7]
-
-Обяснение:
->
-> **[1 3 -1]** -3 5 3 6 7 => 3
->
-> 1 **[3 -1 -3]** 5 3 6 7 => 3
->
-> 1 3 **[-1 -3 5]** 3 6 7 => 5
->
-> 1 3 -1 **[-3 5 3]** 6 7 => 5
->
-> 1 3 -1 -3 **[5 3 6]** 7 => 6
->
-> 1 3 -1 -3 5 **[3 6 7]** => 7
-
-Като бонус можете да направите втора задача да не извежда само минималния път, но и клетките през които сме минали.
-
-Алтернативни решения на задачи 1 и 2 както и още задачи за упражнение можете да намерите на:
-https://github.com/ivanahristova/data-structures-fmi/tree/main/sem04 \ No newline at end of file
diff --git a/Seminar03/media/arr-queue.png b/Seminar03/media/arr-queue.png
deleted file mode 100644
index ba4e1fe..0000000
--- a/Seminar03/media/arr-queue.png
+++ /dev/null
Binary files differ
diff --git a/Seminar03/media/qexample.png b/Seminar03/media/qexample.png
deleted file mode 100644
index b43a02c..0000000
--- a/Seminar03/media/qexample.png
+++ /dev/null
Binary files differ
diff --git a/Seminar03/task01.cpp b/Seminar03/task01.cpp
deleted file mode 100644
index 2a2eff3..0000000
--- a/Seminar03/task01.cpp
+++ /dev/null
@@ -1,27 +0,0 @@
-#include<iostream>
-#include<queue>
-#include<string>
-
-// Сложност по време: ?
-// Сложност по памет: ?
-void printAllBinaryNumbers(size_t n) {
- std::queue<std::string> q;
-
- q.push("1");
-
- while(n) {
- std::string currentNumber = q.front();
- q.pop();
-
- std::cout << currentNumber << " ";
-
- q.push(currentNumber + "0");
- q.push(currentNumber + "1");
-
- n--;
- }
-}
-
-int main() {
- printAllBinaryNumbers(10);
-} \ No newline at end of file
diff --git a/Seminar03/task02.cpp b/Seminar03/task02.cpp
deleted file mode 100644
index ffc6a30..0000000
--- a/Seminar03/task02.cpp
+++ /dev/null
@@ -1,93 +0,0 @@
-#include <iostream>
-#include <array>
-#include <queue>
-
-template<unsigned boardSize = 8>
-class minMoves {
- using position = std::pair<int, int>;
- using positionAndSteps = std::pair<position, int>;
- using board = std::array<std::array<bool, boardSize>, boardSize>;
-
- board playground;
-
- void cleanPlayground() {
- for (auto &row : playground)
- for (auto &pos : row)
- pos = false;
- }
-
- static bool equalPositions(const position &fst, const position &snd) {
- return fst.first == snd.first && fst.second == snd.second;
- }
-
- static bool isValidPos(const position &p) {
- return p.first >= 0 && p.second >= 0 && p.first < boardSize && p.second < boardSize;
- }
-
- void mark(const position &toMark) {
- playground[toMark.first][toMark.second] = true;
- }
-
- bool isMarked(const position &pos) const {
- return playground[pos.first][pos.second];
- }
-
- void pushAndMarkIfValid(std::queue<positionAndSteps> &q, const position &toPush, int steps) {
- if (isValidPos(toPush) && !isMarked(toPush)) {
- q.push({toPush, steps});
- mark(toPush);
- }
- }
-
- int process(const position &startPos, const position &endPos) {
- std::queue<positionAndSteps> q;
-
- q.push({startPos, 0});
-
- while (!q.empty()) {
- positionAndSteps currentPosition = q.front();
-
- q.pop();
-
- if (equalPositions(currentPosition.first, endPos))
- return currentPosition.second;
-
- int x = currentPosition.first.first;
- int y = currentPosition.first.second;
- int moves = currentPosition.second + 1;
-
- pushAndMarkIfValid(q, {x + 1, y + 2}, moves);
- pushAndMarkIfValid(q, {x - 1, y - 2}, moves);
- pushAndMarkIfValid(q, {x + 1, y - 2}, moves);
- pushAndMarkIfValid(q, {x - 1, y + 2}, moves);
- pushAndMarkIfValid(q, {x + 2, y - 1}, moves);
- pushAndMarkIfValid(q, {x + 2, y + 1}, moves);
- pushAndMarkIfValid(q, {x - 2, y + 1}, moves);
- pushAndMarkIfValid(q, {x - 2, y - 1}, moves);
- }
- return -1;
- }
-
-public:
- minMoves() { cleanPlayground(); }
-
- int getMinMoves(const position &start, const position &end) {
- cleanPlayground();
-
- return process(start, end);
- }
-};
-
-int main() {
- minMoves m;
-
- std::cout << m.getMinMoves({0, 0}, {5, 3}) << std::endl;
-
- minMoves<12> ms;
-
- std::cout << ms.getMinMoves({0, 0}, {11, 11}) << std::endl;
-
- minMoves<2> mt;
-
- std::cout << mt.getMinMoves({0, 0}, {12, 212});
-}
diff --git a/Seminar03/task03.cpp b/Seminar03/task03.cpp
deleted file mode 100644
index eef4cf4..0000000
--- a/Seminar03/task03.cpp
+++ /dev/null
@@ -1,41 +0,0 @@
-#include<iostream>
-#include<deque>
-#include<vector>
-
-std::vector<int> maxSlidingWindow(const std::vector<int>& v, size_t k) {
- std::deque<int> window;
- std::vector<int> result;
-
- for (size_t i = 0; i < k; i++) {
- while(!window.empty() && window.back() < v[i]) {
- window.pop_back();
- }
- window.push_back(v[i]);
- }
-
- result.push_back(window.front());
-
- for (size_t i = k; i < v.size(); i++) {
- if(window.front() == v[i - k]) {
- window.pop_front();
- }
-
- while(!window.empty() && window.back() < v[i]) {
- window.pop_back();
- }
-
- window.push_back(v[i]);
- result.push_back(window.front());
- }
-
- return result;
-}
-
-int main() {
- std::vector<int> example = {1, 3, -1, -3, 5, 3, 6, 7};
-
- std::vector<int> result = maxSlidingWindow(example, 3);
-
- for(auto elem : result)
- std::cout << elem << " ";
-} \ No newline at end of file
diff --git a/Seminar04/README.md b/Seminar04/README.md
deleted file mode 100644
index eb35f37..0000000
--- a/Seminar04/README.md
+++ /dev/null
@@ -1,209 +0,0 @@
-# Динамичен масив - преговор с разширение
-
-## Какво беше динамичен масив
-Динамичния масив е линейна структура от данни с произволен достъп до елементите. Различава се от статичния масив по това, че можем да имаме произволен брой елементи в колекцията. Тази структура от данни трябва да ви е добре позната, най - малкото от нейната реализация в STL наречена std::vector\<T>;
-Вектора е изключително популярна структура и да я познаваме ни помага да пишем по - бързи и по - сигурни програми.
-
-Част от интерфейса на std::vector:
-* push_back(const T&) - добавя елемент в края
-* pop_back() - премахва елемент от края
-* operator[](size_t index) - връща елемент на индекс за четене/писане. Не прави проверка дали индекса е валиден или не
-* at(size_t index) - връща елемент на индекс за четене/писане. Хвърля std::out_of_range грешка ако индексът е невалиден.
-
-Нека разгледаме следния код:
-```cpp
-int main() {
- int arr[100];
- int n = 0;
- std::cin >> n;
-
- for(int i = 0; i < n; i++)
- arr[i] = getValue(); // Просто някаква стойност
-}
-```
-Тук главния проблем е какво правим когато n стане по - голямо от 100. Много просто, заделяме 200 елемента вместо 100. Лесно виждаме, как това води до множество проблеми и прави кода неефикасен когато за n не знаем достатъчно. Сега вектора ни идва на помощ:
-
-```cpp
-#include<vector>
-
-int main() {
- std::vector<int> v;
- int n = 0;
- std::cin >> n;
-
- for(int i = 0; i < n; i++)
- v.push_back(getValue());
-}
-```
-Припомняме как работи вектора: Първоначално алокираме някакъв масив. Пазим две променливи *size* и *capacity*. В *size* пишем колко елемента имаме а в *capacity* - колко е размера на алокирания масив. Момента в който *size* стане колкото *capacity* удвояваме масива. Това става чрез просто заделяне на два пъти повече памет, копиране на всичко от старата памет в новата и изтриване на новата памет.
-
-Примерно, за начално *capacity* равно на 1 ще имаме следния сценарий:
-```
- +--+
-Insert 11 |11|
- +--+
- +--+--+
-Insert 12 |11|12|
- +--+--+
- +--+--+--+--+
-Insert 13 |11|12|13| |
- +--+--+--+--+
- +--+--+--+--+
-Insert 14 |11|12|13|14|
- +--+--+--+--+
- +--+--+--+--+--+--+--+--+
-Insert 15 |11|12|13|14|15| | | |
- +--+--+--+--+--+--+--+--+
-```
-
-Тази идея изглежда прекрасно. Можем да си правим колкото искаме *push_back()* и да не мислим за нищо - те хората са го измислили. Е, има още един малък проблем. Алокацията на памет не е евтина операция.
-``` cpp
-class DynArray {
- T* data;
- size_t size = 0;
- size_t capacity = 8;
-};
-```
-Нека в началото *capacity* да е 8. Кога ще имаме алокация? Първо, ще алокираме памет при създаването на масива. След това, когато се опитаме да добавим девети елемент ще алокираме 16 \* sizeof(T) байта. След това когато се опитаме да добавим седемнадесети елемент ще алокираме 32 \* sizeof(T) байта.
-Тоест, когато въртя for цикъла във втория пример, всеки път когато *i = 2^k + 1* ще имам алокация на памет.
-
-Това за наше щастие има как да се оправи. Когато знаем колко елемента ще пазим в динамичния масив можем да извикаме *resize(size_t)*.
-Това ще направи точно една алокация.
-
-```cpp
-#include<vector>
-
-int main() {
- int n = 0;
- std::cin >> n;
- std::vector<int> v;
-
- v.resize(n); // Ресайзва масива за да съдържа точно n елемента.
-
- for(int i = 0; i < n; i++)
- v[i] = getValue();
-}
-```
-Това е удобен трик, но не прекалявайте с него - не е нужно да ресайзваме навсякъде! Просто, ако знаете предварително колко голяма е дължината на вектора, може да направите само една алокация.
-Примерно, в следния случай няма да е добра идея да правим *resize*:
-
-```cpp
-std::vector<int> filter(const std::vector<int>& arr, bool (*pred)(int)) {
- std::vector<int> result;
- // Тук не знаем предварително колко ще е размерът на result.
- for(int i = 0; i < arr.size(); i++)
- if(pred(arr[i]))
- result.push_back(arr[i]);
- return result;
-}
-```
-
-## Сложността на push_back
-До момента разгледахме няколко структури от данни и се стремяхме главно към O(1) сложност. Виждаме, че push_back() е доста използвана операция, каква е нейната сложност? Ами тя доста често е константна, но когато ни се наложи да направим алокация е линейна. Тоест, в най - лошия случай тя е O(n). Но това не е достатъчно добра оценка.
-
-В случая worst case сложността е твърде песимистична. Интересува ни по - скоро колко време ще отнеме цялото изпълнение на алгоритъма използващ push_back() а не колко време ще отнеме на 17 стъпка, примерно. Приемаме по - оптимистичен подход - нека не се интересуваме от това колко е най - лошия случай на операцията а да разгледаме колко време ни отнема да направим всички операции.
-Това неформално е целта на така наречения амортизиран анализ на сложност. С него няма да се занимаваме особено много, но е добре да го знаем от обща култура.
-![](media/AmortizedAnalysis.png)
-
-## Сложност на вмъкване на елемент на произволен индекс
-Вмъкването в края на вектора се оказа практически ефикасна операция. Но дали това остава така ако примерно искаме да вмъкнем елемент по средата? Отговорът е не - това вече си е линейна операция. В най - лошия случай ако искаме да вмъкнем елемент на първа позиция ще трябва да изместим надясно всички елементи на масива. Какво става обаче ако такъв тип вмъквания станат нужни? Има ли начин да ги направим бързи?
-
-# Свързани списъци
-Свързания списък е линейна структура от данни в която елементите не се пазят в последователна памет. Всеки елемент пази указател към следващия а ако няма следващ пазим nullptr.
-
-```cpp
-template<class T>
-struct LinkedListNode {
- T data;
- LinkedListNode<T>* next;
-
- // Удобен конструктор!
- LinkedListNode(const T& elem, LinkedListNode<T>* n = nullptr) : data{elem}, next {n} {}
-}
-```
-Тук е добро място да си поговорим какво наричаме пряк и последователен достъп (или Random/direct access и Sequential access).
-* При прекия достъп можем да достъпим всеки елемент от колекцията за равно време
-* При последователния достъп не можем да достъпим елемент преди да сме обходили елементите преди него в наредбата.
-
-Свързания списък е добър пример за структура с последователен достъп. Пряк достъп имат масивите.
-Има различни видове свързани списъци с които ще се занимаваме с течение на курса.
-Едносвързания списък поддържа следните операции:
-* push_front(const T& elem) - Добавя елемент в началото O(1)
-* push_at(size_t idx, const T& elem) - Добавя елемент на индекс. O(n)
-* pop_front() - Премахва елемента в началото - O(1)
-* pop_at(size_t index) - Премахва елемента на позиция index O(n)
-
-Свързания списък стандартно се представя чрез указател към първия му елемент. Доста често обаче се пази и указател към последния. Това ни помага да имаме бързо добавяне в края на списъка. Наистина, представяме списъка като два указателя - към първия и последния елемент и искаме да обединим два такива списъка това би станало за O(1) време.
-
-```cpp
-template<class T>
-class LinkedList {
-private:
- struct LinkedListNode {
- T data;
- LinkedListNode<T>* next;
- };
-
- LinkedListNode* head; // Началото на списъка
- LinkedListNode* tail; // Края на списъка
-
-public:
- void merge(const LinkedList<T>& second) {
- // O(1) сливане на два списъка без значение от размерите им
- tail->next = second.head;
- tail = second.tail;
- }
-};
-
-```
-Също така, ако имаме указател към дадена позиция в списъка, можем да добавяме колкото си искаме елементи на тази позиция. Всичко става чрез пренасочване на пойнтъри.
-Засега ще представяме свързания списък просто като структура с информация и указател. В следващите семинари ще разгледаме алтернативни представяния и ще видим колко точно ефикасни са спрямо дадени операции!
-
-# Задачи
-
-## Задача първа
-Да се напише функция, която добавя елемент в началото на едносвързан списък
-
-Пример:
-
-LL = 2 -> 3 -> 4
-
-insert(LL, 1)
-
-LL = 1 -> 2 -> 3 -> 4
-
-## Задача втора
-Да се напише функция, която обръща едносвързан списък.
-
-Пример:
-
-LL = 1 -> 2 -> 3 -> 4 -> 5
-
-reverse(LL);
-
-LL = 5 -> 4 -> 3 -> 2 -> 1
-
-## Задача трета
-Да се напише функция, която открива средата на свързан списък.
-Пример:
-
-```
-1 -> 2 -> 3 -> 4 -> 5 => 3
-
-1 -> 2 -> 3 -> 4 => 3
-```
-
-## Задача четвърта
-да се напише функция която пренарежда свързания списък по следния начин:
-
-LL = 1 -> 2 -> 3 -> 4 -> 5
-
-reorder(LL);
-
-LL = 1 -> 5 -> 2 -> 4 -> 3
-
-Когато пишете задачи за свързан списък винаги пробвайте случая когато:
-* Имате празен списък
-* Имате списък с един елемент
-* Имате списък и четни елементи
-* Имате списък с нечетни елементи
diff --git a/Seminar04/find-middle.cpp b/Seminar04/find-middle.cpp
deleted file mode 100644
index dc587ba..0000000
--- a/Seminar04/find-middle.cpp
+++ /dev/null
@@ -1,28 +0,0 @@
-#include"linked-list-utils.h"
-
-template<class T>
-LinkedListNode<T>* findMiddle(LinkedListNode<T>* ll) {
- LinkedListNode<T>* fast = ll;
- LinkedListNode<T>* slow = ll;
-
-
- while(fast && fast->next) {
- fast = fast->next->next;
- slow = slow->next;
- }
-
- return slow;
-}
-
-void example() {
- LinkedListNode<int>* ll = new LinkedListNode(1, new LinkedListNode(2, new LinkedListNode(3, new LinkedListNode(4))));
- LinkedListNode<int>* lls = new LinkedListNode(1, new LinkedListNode(2, new LinkedListNode(3, new LinkedListNode(4, new LinkedListNode(5)))));
-
- LinkedListNode<int>* firstMiddle = findMiddle(ll);
- LinkedListNode<int>* secondMiddle = findMiddle(lls);
-
- std::cout << firstMiddle->data << " " << secondMiddle->data;
-
- freeList(ll);
- freeList(lls);
-} \ No newline at end of file
diff --git a/Seminar04/insert-at-beg.cpp b/Seminar04/insert-at-beg.cpp
deleted file mode 100644
index 88c3d74..0000000
--- a/Seminar04/insert-at-beg.cpp
+++ /dev/null
@@ -1,20 +0,0 @@
-#include"linked-list-utils.h"
-
-template<class T>
-void insertAtBegin(LinkedListNode<T>*& ll, const T& elem) {
- LinkedListNode<T>* toInsert = new LinkedListNode(elem, ll);
- ll = toInsert;
-}
-
-void example() {
- LinkedListNode<int>* ll = new LinkedListNode(1, new LinkedListNode(2, new LinkedListNode(3)));
- printLinkedList(ll);
- insertAtBegin(ll, 0);
- printLinkedList(ll);
- freeList(ll);
-}
-
-int main() {
-
-
-} \ No newline at end of file
diff --git a/Seminar04/linked-list-utils.h b/Seminar04/linked-list-utils.h
deleted file mode 100644
index bf093ba..0000000
--- a/Seminar04/linked-list-utils.h
+++ /dev/null
@@ -1,74 +0,0 @@
-#include<iostream>
-#include<initializer_list>
-
-template<class T>
-struct LinkedListNode {
- T data;
- LinkedListNode<T>* next;
-
- LinkedListNode(const T& elem, LinkedListNode<T>* n = nullptr) : data{elem}, next {n} {}
-};
-
-template<class T>
-void printLinkedList(const LinkedListNode<T>* ll) {
- const LinkedListNode<T>* iterate = ll;
-
- while(iterate) {
- std::cout << iterate->data << " ";
- iterate = iterate->next;
- }
-
- std::cout << std::endl;
-}
-
-template<class T>
-void printLinkedList(const LinkedListNode<T>* ll, void (*print)(T)) {
- const LinkedListNode<T>* iterate = ll;
-
- while(iterate) {
- print(iterate->data);
- iterate = iterate->next;
- }
-
- std::cout << std::endl;
-}
-
-template<class T>
-void printLinkedList(const LinkedListNode<T>* ll, void (*print)(const T&)) {
- const LinkedListNode<T>* iterate = ll;
-
- while(iterate) {
- print(iterate->data);
- iterate = iterate->next;
- }
-
- std::cout << std::endl;
-}
-
-template<class T>
-LinkedListNode<T>* fromList(const std::initializer_list<T>& l) {
- LinkedListNode<T>* toReturn = nullptr;
- LinkedListNode<T>* iter = nullptr;
-
- for(const auto& elem : l) {
- LinkedListNode<T>* toInsert = new LinkedListNode<T>(elem);
- if(iter == nullptr) {
- toReturn = toInsert;
- iter = toInsert;
- }
- else {
- iter->next = toInsert;
- iter = iter->next;
- }
- }
- return toReturn;
-}
-
-template<class T>
-void freeList(LinkedListNode<T>* ll) {
- while(ll) {
- LinkedListNode<T>* toDelete = ll;
- ll = ll->next;
- delete toDelete;
- }
-} \ No newline at end of file
diff --git a/Seminar04/media/AmortizedAnalysis.png b/Seminar04/media/AmortizedAnalysis.png
deleted file mode 100644
index 77f570a..0000000
--- a/Seminar04/media/AmortizedAnalysis.png
+++ /dev/null
Binary files differ
diff --git a/Seminar04/reorder-linked-list.cpp b/Seminar04/reorder-linked-list.cpp
deleted file mode 100644
index 6259a36..0000000
--- a/Seminar04/reorder-linked-list.cpp
+++ /dev/null
@@ -1,160 +0,0 @@
-#include"linked-list-utils.h"
-#include<deque>
-
-// O(n) time
-// O(n) complexity
-void reorderWithDeque(LinkedListNode<int>* head) {
- if(!head || !head->next)
- return;
-
- std::deque<LinkedListNode<int>*> dq;
-
- LinkedListNode<int>* it = head;
-
- while(it) {
- dq.push_back(it);
- it = it->next;
- }
-
- // Винаги пазим края на вече готовия списък
- // Ако не е ясно как го използвам прочети обяснението над втория метод
- // идеята е същата.
- LinkedListNode<int>* backOfNewList = nullptr;
-
- while(!dq.empty()) {
- // Ако размерът е 1 то имаме нечетен брой елементи и просто добавяме последния в края
- if(dq.size() == 1) {
- backOfNewList->next = dq.front();
- backOfNewList = backOfNewList->next;
- break;
- }
-
- // Първия елемент останал в дека започва да сочи към последния.
- // Генерираме коректна двойка.
- dq.front()->next = dq.back();
-
- // Ако края на списъка не е nullptr следващите два елемента
- // в списъка са dq.front()->dq.front()->next (което е dq.back())
- if(backOfNewList)
- backOfNewList->next = dq.front(); // Сложи следващите два елемента накрая
-
- backOfNewList = dq.front()->next; // Вече края на списъка е друг. Преместваме се там.
-
- dq.pop_back();
- dq.pop_front();
- }
-
- // next на последния елемент от списъка е nullptr, този ред е важен.
- backOfNewList->next = nullptr;
-}
-
-// Това ще ни помогне за второто решение
-template<class T>
-void reverseLinkedList(LinkedListNode<T>*& ll) {
- LinkedListNode<T>* previous = nullptr;
- LinkedListNode<T>* next = nullptr;
- LinkedListNode<T>* iterate = ll;
-
- while(iterate) {
- next = iterate->next;
- iterate->next = previous;
- previous = iterate;
- iterate = next;
- }
-
- ll = previous;
-}
-
-// Това също
-template<class T>
-LinkedListNode<T>* findMiddle(LinkedListNode<T>* ll) {
- LinkedListNode<T>* fast = ll;
- LinkedListNode<T>* slow = ll;
-
- while(fast && fast->next) {
- fast = fast->next->next;
- slow = slow->next;
- }
-
- return slow;
-}
-
-/*
-Тук идеята е да намерим средата и да я обърнем. Две неща, които вече знаем как да правим. Как ще протече алгоритъма:
-
-Вход: 1 -> 2 -> 3 -> 4 -> 5
-Среда: 3 -> 4 -> 5
-
-Обърната среда: 5 -> 4 -> 3 -> nullptr
-Как изглежда първоначалния масив: 1 -> 2 -> 3 -> nullptr
-
-Дали е бъг, че и в двата списъка имаме еднакъв последен елемент? Малко неточно е, но за да го оправя трябва да променя функциите.
-С цел да са разбираеми нещата го оставям така.
-
-В случая става нещо подобно:
-1-> 2 -> 3 -> nullptr
- ^
-5 -> 4 /
-
-Виждаме, че последователно трябва да вземаме двойки (L_0 -> L_n) -> (L_1 -> L_{n-1}) -> (L_2 -> L_{n - 2}) -> ... и да ги поставяме една след друга.
-
-* firstHalf -> първата половина от списъка
-* mid -> Втората половина от списъка
-* currentPair -> текущата двойка (L_i -> L_{n - i})
-* backOfList -> Края на коректния списък от двойки
-
-Сега имаме този сценарий:
-[някакъв коректен списък] [коректна двойка]
-* Насочи края на този коректен списък да сочи към коректната двойка. Това става лесно понеже му пазя края!
-[някакъв вече готов списък] -> [коректна двойка]
-* Сега насочи указателя който пази края на коректния списък да сочи към края на този списък, понеже този списък е корекрен.
-[стария коректен списък -> коректната двойка] - готов за още коректни двойки!
-
-Така добавямe коректни двойки докато не стигна края на списъка съдържащ обърнатата дясна част.
-*/
-void reorderWithTwoPointers(LinkedListNode<int>* ll) {
- if(!ll || !ll->next)
- return;
-
- LinkedListNode<int>* mid = findMiddle(ll);
- reverseLinkedList(mid);
-
- LinkedListNode<int>* firstHalf = ll;
- LinkedListNode<int>* currentPair = nullptr;
- LinkedListNode<int>* backOfList = nullptr;
-
- while(mid) {
- currentPair = firstHalf;
- firstHalf = firstHalf->next;
-
- // Случая в който имаме нечетен брой елементи
- if(!firstHalf) {
- backOfList->next = currentPair;
- backOfList = backOfList->next;
- break;
- }
-
- currentPair->next = mid;
- mid = mid->next;
-
- if(backOfList)
- backOfList->next = currentPair; // Пренасочи края към коректната двойка. Ако е nullptr нямаме какво да пренасочваме.
-
- backOfList = currentPair->next; // И един бърз ъпдейт на края - вече края на коректния лист е стария лист + новата двойка
- }
-
- backOfList->next = nullptr;
-}
-
-int main() {
- LinkedListNode<int>* ll = new LinkedListNode<int>
- (1, new LinkedListNode<int>
- (2, new LinkedListNode<int>
- (3, new LinkedListNode<int>
- (4, new LinkedListNode<int>
- (5)))));
-
- reorderWithTwoPointers(ll);
- printLinkedList(ll);
- freeList(ll);
-} \ No newline at end of file
diff --git a/Seminar04/reverse-linked-list.cpp b/Seminar04/reverse-linked-list.cpp
deleted file mode 100644
index 486b41e..0000000
--- a/Seminar04/reverse-linked-list.cpp
+++ /dev/null
@@ -1,25 +0,0 @@
-#include "linked-list-utils.h"
-
-template<class T>
-void reverseLinkedList(LinkedListNode<T>*& ll) {
- LinkedListNode<T>* previous = nullptr;
- LinkedListNode<T>* next = nullptr;
- LinkedListNode<T>* iterate = ll;
-
- while(iterate) {
- next = iterate->next;
- iterate->next = previous;
- previous = iterate;
- iterate = next;
- }
-
- ll = previous;
-}
-
-void example() {
- LinkedListNode<int>* ll = new LinkedListNode(1, new LinkedListNode(2, new LinkedListNode(3, new LinkedListNode(4))));
- printLinkedList(ll);
- reverseLinkedList(ll);
- printLinkedList(ll);
- freeList(ll);
-} \ No newline at end of file
diff --git a/Seminar05/LinkedList.hpp b/Seminar05/LinkedList.hpp
deleted file mode 100644
index 610d999..0000000
--- a/Seminar05/LinkedList.hpp
+++ /dev/null
@@ -1,326 +0,0 @@
-#ifndef _SINGLY_LINKED_LIST_IMPL
-#define _SINGLY_LINKED_LIST_IMPL
-
-#include<stdexcept>
-
-template<class T>
-class LinkedList {
-private:
- struct LinkedListNode {
- T data;
- LinkedListNode* next;
-
- LinkedListNode(const T& elem, LinkedListNode* n = nullptr) : data{ elem }, next { n } {}
- };
-
- void free();
- void copy(const LinkedList<T>&);
-public:
- class Iterator {
- private:
- // Текущия възел в обхождането
- LinkedListNode* currentNode;
-
- Iterator(LinkedListNode* arg) : currentNode { arg } {}
- public:
-
- Iterator& operator++() {
- if(currentNode == nullptr)
- return *this;
- currentNode = currentNode->next;
- return *this;
- }
-
- Iterator operator++(int) {
- Iterator temp = *this;
- ++(*this);
- return temp;
- }
-
- T& operator*() {
- return currentNode->data;
- }
-
- bool operator==(const Iterator& other) const {
- return other.currentNode == currentNode;
- }
-
- bool operator!=(const Iterator& other) const {
- return !(*this == other);
- }
-
- friend class LinkedList;
- };
-
- class ConstIterator {
- private:
- const LinkedListNode* currentNode; // Това вече е указател към константна памет!
-
- ConstIterator(LinkedListNode* arg) : currentNode { arg } {}
- public:
-
- ConstIterator& operator++() {
- if(currentNode == nullptr)
- return *this;
-
- currentNode = currentNode->next;
- return *this;
- }
-
- ConstIterator operator++(int) {
- ConstIterator temp = *this;
- ++(*this);
- return temp;
- }
-
- const T& operator*() const {
- return currentNode->data;
- }
-
- bool operator==(const ConstIterator& other) const {
- return other.currentNode == currentNode;
- }
-
- bool operator!=(const ConstIterator& other) const {
- return !(*this == other);
- }
-
- friend class LinkedList;
- };
-
- LinkedList();
-
- LinkedList(const LinkedList<T>&);
- LinkedList(LinkedList<T>&&);
-
- LinkedList& operator=(const LinkedList<T>&);
- LinkedList& operator=(LinkedList<T>&&);
-
- Iterator begin() {
- return Iterator(head);
- }
-
- Iterator end() {
- return Iterator(nullptr);
- }
-
- ConstIterator begin() const {
- return ConstIterator(head);
- }
-
- ConstIterator end() const {
- return ConstIterator(nullptr);
- }
-
- ConstIterator cbegin() const {
- return ConstIterator(head);
- }
-
- ConstIterator cend() const {
- return ConstIterator(nullptr);
- }
-
- void pushBack(const T&);
- void popBack();
-
- void pushFront(const T&);
- void popFront();
-
- const T& front() const;
- const T& back() const;
-
- T& front();
- T& back();
-
- bool empty() const;
- size_t size() const;
-
- ~LinkedList();
-
-private:
- LinkedListNode* head;
- LinkedListNode* tail;
- size_t sizeOfList;
-};
-
-template<class T>
-LinkedList<T>::LinkedList() : head {nullptr}, tail {nullptr}, sizeOfList { 0 } {}
-
-template<class T>
-void LinkedList<T>::free() {
- while(head) {
- LinkedListNode* toDelete = head;
- head = head->next;
- delete toDelete;
- }
- sizeOfList = 0;
-}
-
-template<class T>
-void LinkedList<T>::copy(const LinkedList<T>& other) {
- LinkedListNode* iter = other.head;
-
- while(iter) {
- pushBack(iter->data);
- iter = iter->next;
- }
-
- sizeOfList = other.sizeOfList;
-}
-
-template<class T>
-LinkedList<T>::LinkedList(const LinkedList<T>& other) : head {nullptr}, tail{ nullptr } {
- copy(other);
-}
-
-template<class T>
-LinkedList<T>::LinkedList(LinkedList<T>&& other) {
- head = other.head;
- tail = other.tail;
- sizeOfList = other.sizeOfList;
-
- other.head = other.tail = nullptr;
- other.sizeOfList = 0;
-}
-
-template<class T>
-LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& other) {
- if(this != & other) {
- free();
- copy(other);
- }
- return *this;
-}
-
-template<class T>
-LinkedList<T>& LinkedList<T>::operator=(LinkedList<T>&& other) {
- if(this != &other) {
- free();
-
- head = other.head;
- tail = other.tail;
- sizeOfList = other.sizeOfList;
-
- other.head = other.tail = nullptr;
- other.sizeOfList = 0;
- }
- return *this;
-}
-
-template<class T>
-void LinkedList<T>::pushBack(const T& elem) {
- LinkedListNode* toInsert = new LinkedListNode(elem);
- ++sizeOfList;
-
- if(empty()) {
- head = tail = toInsert;
- }
- else {
- tail->next = toInsert;
- tail = toInsert;
- }
-}
-
-template<class T>
-void LinkedList<T>::popBack() {
- if(empty()) {
- throw std::runtime_error("Tried to pop back on empty list!");
- }
- --sizeOfList;
-
- if(head == tail) {
- delete tail;
- head = tail = nullptr;
- }
- else {
- LinkedListNode* newTail = head;
-
- // O(n) за n дължината на свързания списък
- while (newTail->next != tail) {
- newTail = newTail->next;
- }
-
- delete tail;
- tail = newTail;
- tail->next = nullptr;
- }
-}
-
-template<class T>
-void LinkedList<T>::pushFront(const T& elem) {
- LinkedListNode* toInsert = new LinkedListNode(elem, head);
-
- if(empty())
- tail = toInsert;
-
- head = toInsert;
-
- ++sizeOfList;
-}
-
-template<class T>
-void LinkedList<T>::popFront() {
- if(empty())
- throw std::runtime_error("Cannot pop front from empty list!");
-
- if(head == tail) {
- delete tail;
- head = tail = nullptr;
- }
- else {
- LinkedListNode* toDelete = head;
- head = head->next;
- delete toDelete;
- }
-
- --sizeOfList;
-}
-
-template<class T>
-bool LinkedList<T>::empty() const {
- return head == nullptr;
-}
-
-template<class T>
-size_t LinkedList<T>::size() const {
- return sizeOfList;
-}
-
-template<class T>
-const T& LinkedList<T>::front() const {
- if(empty())
- throw std::runtime_error("Empty list!");
-
- return head->data;
-}
-
-template<class T>
-T& LinkedList<T>::front() {
- if(empty())
- throw std::runtime_error("Empty list!");
-
- return head->data;
-}
-
-template<class T>
-const T& LinkedList<T>::back() const {
- if(empty())
- throw std::runtime_error("Empty list!");
-
- return tail->data;
-}
-
-template<class T>
-T& LinkedList<T>::back() {
- if(empty())
- throw std::runtime_error("Empty list!");
-
- return tail->data;
-}
-
-template<class T>
-LinkedList<T>::~LinkedList() {
- free();
-}
-
-#endif
diff --git a/Seminar05/README.md b/Seminar05/README.md
deleted file mode 100644
index 1a493aa..0000000
--- a/Seminar05/README.md
+++ /dev/null
@@ -1,342 +0,0 @@
-# Свързани списъци втора част
-
-## Малко за представянията
-Миналия семинар работихме с един класически начин за представяне на свързан списък, а именно просто чрез указател към първия му елемент. Днес ще разгледаме представянето на свързания списък като клас.
-Разбира се, какво може да е толкова трудното на това да представим свързания списък като клас? Правим подходящи конструктори, вместо функция *freeLinkedList* ще имаме деструктор, всички нужни функции ще ги направим като член-функции на новосъздадения ни клас и готово.
-
-Проблемът тук е, че доста често ни се налага да обхождаме списъка. Когато го представяхме чрез указател към първия му елемент нещата бяха лесни:
-```cpp
-void map(LinkedListNode<int>* ll, void (*func)(int&)) {
- while(ll) {
- func(ll->data);
- ll = ll->next;
- }
-}
-```
-Можем да направим нещо подобно:
-```cpp
-LinkedListNode* getHead();
-```
-Да вземем началото и да обхождаме отново с while цикъл. Когато представяме свързания списък като клас е желателно да държим логиката по представянето на елемента private. Потребителя работи с интерфейса на свързания списък. Това, че елементът на свързания списък е структура LinkedListNode която има указател към следващ елемент и тн остава скрито.
-
-## Итератори
-Тук на помощ идват итераторите. Итераторите са обекти, които са отговорни за обхождане на контейнери (динамичен масив, свързан списък и тн). В *C++* голяма част от STL използва итератори за постигане на целите си.
-Примерната реализация, с която ще работим, се намира във файла LinkedList.hpp. Представяме свързания списък с два указателя, където
-* head сочи към първия (най-левия) елемент
-
-* tail сочи към последния (най-десния) елемент
-
-
-* Също така пазим още една допълнителна променлива от тип size_t за дължината на списъка.
-
-Разгледайте реализацията, особено алгоритмите за добавяне и премахване в началото и в края. Забележете, че всеки път разглеждаме три случая:
-* Дали листа е празен
-* Дали листа има един елемент
-* Дали листа има повече от един елемент
-
-Вече имаме някаква примерна реализация на свързан списък. Хайде да си направим итератор и да видим колко точно сложно ще е.
-Ще направим итератора **вътрешен и публичен клас за класа LinkedList**.
-```cpp
-// ...
-public:
-class Iterator {
- private:
-
- public:
-
-};
-// ...
-```
-Сега, какво трябва да имаме в този клас? Той е отговорен за предвижване по възлите на свързания списък. Когато се придвижваме във всеки момент имаме някой текущ елемент. Следователно ще ни трябва текущ елемент. Също така, ще ни трябва начин да създадем итератор към някой елемент.
-След курса по ООП това е лесна задача:
-```cpp
-class Iterator {
- private:
- // Текущия възел в обхождането
- LinkedListNode* currentNode;
-
- Iterator(LinkedListNode* arg) : currentNode { arg } {}
- public:
-};
-```
-Искаме да обхождаме, значи ни трябва някакъв начин да се придвижим напред. Конвенцията е тази задача да се изпълнява от operator++.
-Това става по следния начин:
-```cpp
-// Забележете, че връщаме итератор!
-Iterator& operator++() {
- // Ако сме стигнали края не правим нищо
- if(currentNode == nullptr)
- return *this;
-
- // Преместваме се една позиция надясно
- currentNode = currentNode->next;
-
- return *this;
-}
-```
-Супер, вече имаме ++it. Но ще е добре и да си направим it++, не знаем за какво ще ни потрябва.
-
-```cpp
-// Защо този път връщаме Iterator а не Iterator&?
-// Защото този път връщаме temporary object наречен temp. Той е заделен статично и ще се унищожи когато стигнем края на скоупа
-
-Iterator operator++(int) {
- Iterator temp = *this;
- ++(*this);
- return temp;
-}
-```
-Напомняме, че разликата между префиксния и постфиксния operator++ е просто един "служебен" int като аргумент на постфиксния.
-
-Супер, вече можем да се движим, но това движение става безполезно ако нямаме начин да видим каква информация имаме в currentNode. Тази задача по конвенция се изпълнява от operator\*. Супер, нека го предефинираме:
-```cpp
-T& operator*() {
- return currentNode->data;
-}
-```
-Също ни трябва начин да разберем дали два итератора са равни или не. Тази задача се изпълнява от *operator==* и *operator!=*
-
-```cpp
-bool operator==(const Iterator& other) const {
- // Сравняваме ги по адреси!
- return other.currentNode == currentNode;
-}
-
-bool operator!=(const Iterator& other) const {
- return !(*this == other);
-}
-```
-Повечето контейнери в STL имате методи begin() и end(), които връщат итератори към началото и края. Нека последваме примера им:
-```cpp
-Iterator begin() {
- return Iterator(head);
-}
-
-Iterator end() {
- return Iterator(nullptr);
-}
-```
-Ние направихме конструктора на итератора private. За да извикаме Iterator(head) обаче трябва някак да имаме достъп до private конструктора на Iterator.
-Това ще направим като декларираме класа LinkedList като приятелски за Iterator!
-```cpp
-/// ...
-bool operator!=(const Iterator& other) const {
- return !(*this == other);
-}
- friend class LinkedList;
-/// ...
-```
-Вече сме готови. Нека да проверим дали нашия метод работи:
-```cpp
-int main() {
- LinkedList<int> ll;
-
- for (size_t i = 0; i < 10; i++)
- ll.pushBack(i);
- // Тук има значение дали викаме ++it или it++!
- for(LinkedList<int>::Iterator it = ll.begin(); it != ll.end(); ++it)
- std::cout << *it << " ";
-}
-```
-
-## Const и итераторите
-Нека разгледаме следния код:
-```cpp
-int main() {
- const LinkedList<int> ll;
- LinkedList<int>::Iterator beg = ll.begin();
-}
-```
-В случая имаме грешка, понеже нямаме декларирана константна функция begin(). Нека си напишем константни begin() и end():
-```cpp
-const Iterator begin() const {
- return Iterator(head);
-}
-const Iterator end() const {
- return Iterator(nullptr);
-}
-```
-Горния фрагмент код се компилира, но вече имаме друг проблем:
-```cpp
-void hack(const LinkedList<int>& ll) {
- LinkedList<int>::Iterator beg = ll.begin();
- *beg = 10;
-}
-
-int main() {
- LinkedList<int> ll;
- ll.pushBack(1);
- hack(ll);
- std::cout << ll.back();
-}
-```
-В случая, въпреки че ll е const, отново променяме стойността му. Но защо?
-
-В случая **beg е константен**. Той е съставен от един пойнтър, който обаче **не е константен**. В някакъв смисъл **това, че стойността на паметта към която сочи пойнтъра се променя не чупи константността на итератора**. За това ще се наложи да дефинираме още един клас, ConstIterator!
-```cpp
-class ConstIterator {
- private:
- // Тук вече е указател към константна памет
- const LinkedListNode* currentNode;
-
- ConstIterator(LinkedListNode* arg) : currentNode { arg } {}
- public:
-
- ConstIterator& operator++() {
- if(currentNode == nullptr)
- return *this;
- currentNode = currentNode->next;
- return *this;
- }
-
- ConstIterator operator++(int) {
- Iterator temp = *this;
- ++(*this);
- return temp;
- }
-
- const T& operator*() const {
- return currentNode->data;
- }
-
- bool operator==(const ConstIterator& other) const {
- return other.currentNode == currentNode;
- }
-
- bool operator!=(const ConstIterator& other) const {
- return !(*this == other);
- }
-
- friend class LinkedList;
-};
-```
-
-Нещата са доста подобни, единствената разлика тук е, че имаме константен указател като тип на текущия елемент.
-
-Реализираме следните:
-```cpp
-// Връща константен итератор към началото
-ConstIterator cbegin() const {
- return ConstIterator(head);
-}
-
-// Връща константен итератор към края
-ConstIterator cend() const {
- return ConstIterator(nullptr);
-}
-```
-Сега, ако искам да имам итератор за константен списък, просто ще създавам ConstIterator. Примерно, искаме да итерираме константен свързан списък:
-
-```cpp
-void iterate(const LinkedList<int>& ll){
- for(LinkedList<int>::ConstIterator it = ll.cbegin(); it != ll.cend(); ++it) {
- std::cout << *it << " ";
- }
-}
-```
-
-## auto
-Най - вероятно вече сте чували за ключовата дума *auto*. Чрез нея карате компилатора сам да прецени какъв тип да използва за променливата. Тя е удобна когато имате дълги типове. Прави кодът по-четим и разбираем. Като всяко хубаво нещо обаче **с auto не е добре да се прекалява.**
-
-```cpp
-// Автоматично разбирам типа на it
-for(auto it = ll.begin(); it != ll.end(); ++it) {
- //...
-}
-
-auto x = 5; // х е променлива от тип int
-const auto y = 10u; // y e променлива от тип const unsigned
-auto f = 10.0f; // f е променлива от тип float
-const auto& r = f; // r е променлива от тип const float&
-
-std::list<int> ll;
-
-auto it = ll.begin(); // it e променлива от тип std::list<int>::iterator
-const auto its = ll.end(); // it е променлива от тип ?
-auto itss = ll.cend(); // it е променлива от тип ?
-```
-
-## range based for loops
-От c++11 езикът ни предлага начин, чрез който да пишем подобни for цикли още по - бързо.
-```cpp
-int main() {
- LinkedList<int> ll;
-
- for(const int& elem : ll) {
- std::cout << elem << " ";
- }
-}
-```
-Този цикъл е еквивалентен на горния, просто е синтактична захар.
-
-За по - любопитните компилатора развива този приятен for цикъл до следното:
-
-```cpp
-{
- LinkedList<int> & __range1 = ll;
-
- LinkedList<int>::Iterator __begin1 = __range1.begin();
-
- LinkedList<int>::Iterator __end1 = __range1.end();
-
- for(; __begin1.operator!=(__end1); __begin1.operator++()) {
- const int & elem = __begin1.operator*();
- std::operator<<(std::cout.operator<<(elem), " ");
- }
-}
-```
-
-## Задача първа:
-
-Даден е списък `l` с `n` елемента.
-
-Да се дефинира функция shuffle(), която получава **адреса на първия елемент на списъка**.
-
-Функцията да пренарежда възлите на списъка така, че елементите от втората половина на списъка да се преместят в началото на списъка, но в обратен ред (при списъци с нечетен брой елементи считаме средния елемент за принадлежащ към първата половина на списъка).
-Пример:
-
-Вход: L1 → L2 → L3 → L4 → L5
-
-Изход: L5 → L4 → L1 → L2 → L3
-
-## Задача втора:
-
-Даден е списък l с елементи стекове.
-
-Да се дефинира функция equalize(l), която размества елементите на стековете така, че да няма два стека в l с разлика в броя на елементите, по-голяма от 1.
-
-```
-Вход Изход
-
-5 -> 4 -> 3 -> 2 -> 1 5 -> 4 -> 3
-| |
-v v
-7 -> 6 7 -> 6 -> 1
-| |
-v v
-11 -> 10 -> 9 -> 8 11 -> 10 -> 9
-| |
-v v
-12 12 -> 2 -> 8
-```
-
-## Задача трета - Linked List Partition
-Да се създаде функция
-```cpp
-LinkedListNode<int>* partition(LinkedListNode<int>* head, int x);
-```
-която пренарежда списъка така, че всички възли със стойност по-малка от **х** са преди всички възли със стойност по-голяма или равна от **х**.
-
-Пример:
-
-Вход: head -> 1 -> 4 -> 3 -> 2 -> 5 -> 2, x = 3
-
-Изход: 1 -> 2 -> 2 -> 4 -> 3 -> 5
-
-Вход: head -> 2 -> 1, x = 2
-
-Изход: 1 -> 2
-
-**HINT:**
-
-Можете да си направите два указателя, чрез които да строите някакви полезни помощни списъци. После, след като построите тези полезни помощни списъци, можете да пренасочите правилните указатели и да получите коректен отговор.
diff --git a/Seminar05/list-cheat-sheet.cpp b/Seminar05/list-cheat-sheet.cpp
deleted file mode 100644
index fd68300..0000000
--- a/Seminar05/list-cheat-sheet.cpp
+++ /dev/null
@@ -1,122 +0,0 @@
-#include<list>
-#include<iostream>
-#include"../Seminar04/linked-list-utils.h"
-
-// Пример как да напишем една и съща функция
-// Чрез итератори и чрез пойнтър представянето
-
-// Функцията map приема свързан списък и функция която приема int
-// и прилага функцията върху всеки елемент от списъка
-void mapOnSTLList(std::list<int>& ll, void (*f)(int&)) {
- for(int& elem : ll)
- f(elem);
-}
-
-void mapOnListRepresentedAsPointer(LinkedListNode<int>* ll, void (*f)(int&)) {
- while(ll) {
- f(ll->data);
- ll = ll->next;
- }
-}
-
-//.....
-
-void printList(const std::list<int>& myList, const char* msg) {
- if(msg != "")
- std::cout << msg << std::endl;
-
- // range based for loop който извежда всички елементи на списъка
- for(const int& elementInList : myList)
- std::cout << elementInList << " ";
- std::cout << std::endl;
-}
-
-int main() {
- std::list<int> myList;
-
- const auto f = myList.begin();
-
- // Добави елемент в края на листа
- for (int i = 0; i < 10; i++)
- myList.push_back(i);
-
- // Добави елемент в началото на листа
- for(int i = 10; i < 20; i++)
- myList.push_front(i);
-
- printList(myList, "Added the elements from [0..9] to the back and [10..19] to the front");
-
- // Можем да изтриваме елементи на позиция
- myList.erase(myList.begin());
- printList(myList, "Erased the first element");
-
- // Удобен начин да обърнем списък
- myList.reverse();
- printList(myList, "Reversed the linked list");
-
- // Можем да премахнем елемент
- myList.remove(10);
- printList(myList, "After removing 10 from the list");
-
- // Можем да премахнем всички елементи, които отговарят на някакъв предикат
- // Аргумента на remove_if е булева функция. Ще останат само тези за които условието е лъжа.
- myList.remove_if([](const int& currentElement) -> bool { return currentElement % 2; });
- printList(myList, "Filter all odd elements");
-
- // myList.begin(); begin iterator
- // myList.end(); end iterator
-
- // myList.cbegin(); constang begin iterator
- // myList.cend(); constant end iterator
-
- // Мога да създавам списъци така
- std::list<int> second{1, 2, 3, 4, 5};
- printList(second, "Create second list with initializer list");
-
- // Премества елементи от един лист в друг
- myList.splice(myList.begin(), second);
- printList(myList, "First list after splice");
- printList(second, "second list after splice");
-
- // Да си върнем малко елементи във втория списък
- second.assign({1, 2, 3, 4, 5});
- printList(second, "Second list after .assign({1, 2, 3, 4, 5})");
-
- // Можем да сортираме листа
- myList.sort();
- printList(myList, "First list after beigg sorted");
-
- // Можем и да го сортираме наобратно
- myList.sort([](const int& fst, const int& snd) -> bool { return fst > snd; });
- printList(myList, "First list after being sorted with >");
-
- LinkedListNode<int>* pointreLinkedlist =
- new LinkedListNode<int>(1,
- new LinkedListNode<int>(2,
- new LinkedListNode<int>(3,
- new LinkedListNode<int>(4,
- new LinkedListNode<int>(5)))));
-
- mapOnListRepresentedAsPointer(pointreLinkedlist, [](int& x) -> void {x = 2*x; });
- mapOnSTLList(second, [](int& x) -> void { x = 2*x; });
-
- printList(second, "Second list after mappint 2*");
- std::cout << "Pointer linked list after mappint 2* " << std::endl;
- printLinkedList(pointreLinkedlist);
- std::cout << std::endl;
-
- // Как да добавяме елементи на произволна позиция?
-
- // Итератор към началото
- std::list<int>::iterator it = myList.begin();
-
- // Отиваме на позицията
- for (size_t i = 0; i < 2; i++) {
- ++it;
- }
-
- // Добавяме
- myList.insert(it, 10000);
- // insert може да вмъква и цели рейнджове
- printList(myList, "My list after adding 10000 in third pos");
-} \ No newline at end of file
diff --git a/Seminar06/DLLSkeleton.cpp b/Seminar06/DLLSkeleton.cpp
deleted file mode 100644
index 77811b8..0000000
--- a/Seminar06/DLLSkeleton.cpp
+++ /dev/null
@@ -1,70 +0,0 @@
-#ifndef DOUBLY_LINKED_LIST_IMPL_
-#define DOUBLY_LINKED_LIST_IMPL_
-
-#include<exception>
-
-template<class T>
-class DoublyLinkedList {
-private:
- struct DLListNode {};
-
- using Node = DLListNode;
-
- Node* head;
- Node* tail;
-
- void copy(const DoublyLinkedList<T>& other);
- void free();
-
- class Iterator {
- private:
- Node* current;
- Iterator(Node* c) {}
-
- public:
- Iterator& operator++() {}
-
- Iterator operator++(int) {}
-
- Iterator& operator--() {}
-
- Iterator operator--(int) {}
-
- const T& operator*() {}
-
- bool operator==(const Iterator& other) const {}
-
- bool operator!=(const Iterator& other) const {}
-
- friend class DoublyLinkedList<T>;
- };
-
-public:
- DoublyLinkedList();
-
- DoublyLinkedList(const DoublyLinkedList<T>&);
- DoublyLinkedList& operator=(const DoublyLinkedList<T>&);
-
- DoublyLinkedList(DoublyLinkedList<T>&&);
- DoublyLinkedList& operator=(DoublyLinkedList<T>&&);
-
- void pushBack(const T&);
- void popBack();
-
- void pushFront(const T&);
- void popFront();
-
- bool empty() const;
-
- const T& back() const;
- const T& front() const;
-
- Iterator begin();
- Iterator end();
-
- void insert(Iterator at, const T& elem);
-
- ~DoublyLinkedList();
-};
-
-#endif \ No newline at end of file
diff --git a/Seminar06/DoublyLinkedList.hpp b/Seminar06/DoublyLinkedList.hpp
deleted file mode 100644
index f1bb01e..0000000
--- a/Seminar06/DoublyLinkedList.hpp
+++ /dev/null
@@ -1,294 +0,0 @@
-#ifndef DOUBLY_LINKED_LIST_IMPL_
-#define DOUBLY_LINKED_LIST_IMPL_
-
-#include<exception>
-
-template<class T>
-class DoublyLinkedList {
-private:
- struct DLListNode {
- T data;
- DLListNode* next;
- DLListNode* prev;
-
- DLListNode(const T& d, DLListNode* n = nullptr, DLListNode* p = nullptr) :
- data {d},
- next {n},
- prev {p} {}
- };
-
- using Node = DLListNode;
-
- Node* head;
- Node* tail;
-
- void copy(const DoublyLinkedList<T>& other);
- void free();
-
- class Iterator {
- private:
- Node* current;
- Iterator(Node* c = nullptr) : current { c } {}
-
- public:
- Iterator& operator++() {
- if(current == nullptr)
- return *this;
- current = current->next;
- return *this;
- }
-
- Iterator operator++(int) {
- if(current == nullptr)
- return *this;
-
- Iterator tmp = *this;
- current = current->next;
- return tmp;
- }
-
- Iterator& operator--() {
- if(current == nullptr)
- return *this;
-
- current = current->prev;
- return *this;
- }
-
- Iterator operator--(int) {
- if(current == nullptr)
- return *this;
-
- Iterator tmp = *this;
- current = current->prev;
- return tmp;
- }
-
- const T& operator*() {
- if(current == nullptr)
- throw std::exception();
-
- return current->data;
- }
-
- bool operator==(const Iterator& other) const {
- return current == other.current;
- }
-
- bool operator!=(const Iterator& other) const {
- return !(*this == other);
- }
-
- friend class DoublyLinkedList<T>;
- };
-
-public:
- DoublyLinkedList();
-
- DoublyLinkedList(const DoublyLinkedList<T>&);
- DoublyLinkedList& operator=(const DoublyLinkedList<T>&);
-
- DoublyLinkedList(DoublyLinkedList<T>&&);
- DoublyLinkedList& operator=(DoublyLinkedList<T>&&);
-
- void pushBack(const T&);
- void popBack();
-
- void pushFront(const T&);
- void popFront();
-
- bool empty() const;
-
- const T& back() const;
- const T& front() const;
-
- Iterator begin();
- Iterator end();
-
- void insert(Iterator at, const T& elem);
-
- ~DoublyLinkedList();
-};
-
-template<class T>
-DoublyLinkedList<T>::DoublyLinkedList() : head { nullptr }, tail { nullptr } {}
-
-template<class T>
-DoublyLinkedList<T>::DoublyLinkedList(const DoublyLinkedList<T>& other) : head {nullptr}, tail {nullptr} {
- copy(other);
-}
-
-template<class T>
-DoublyLinkedList<T>& DoublyLinkedList<T>::operator=(const DoublyLinkedList<T>& other) {
- if(this != &other) {
- free();
- copy(other);
- }
- return *this;
-}
-
-template<class T>
-DoublyLinkedList<T>::DoublyLinkedList(DoublyLinkedList<T>&& other) {
- head = other.head;
- tail = other.tail;
-
- other.head = other.tail = nullptr;
-}
-
-template<class T>
-DoublyLinkedList<T>& DoublyLinkedList<T>::operator=(DoublyLinkedList<T>&& other) {
- if(this != &other) {
- free();
-
- head = other.head;
- tail = other.tail;
-
- other.head = other.tail = nullptr;
- }
- return *this;
-}
-
-template<class T>
-void DoublyLinkedList<T>::copy(const DoublyLinkedList<T>& other) {
- Node* iter = other.head;
-
- while(iter) {
- pushBack(iter->data);
- iter = iter->next;
- }
-}
-
-template<class T>
-void DoublyLinkedList<T>::free() {
- while(head) {
- Node* toDelete = head;
- head = head->next;
- delete toDelete;
- }
-}
-
-template<class T>
-bool DoublyLinkedList<T>::empty() const {
- return head == nullptr;
-}
-
-template<class T>
-void DoublyLinkedList<T>::pushBack(const T& elem) {
- Node* toInsert = new Node(elem);
-
- if(empty()) {
- head = tail = toInsert;
- }
- else {
- toInsert->prev = tail;
- tail->next = toInsert;
- tail = toInsert;
- }
-}
-
-template<class T>
-void DoublyLinkedList<T>::pushFront(const T& elem) {
- Node* toInsert = new Node(elem);
-
- if(empty()) {
- head = tail = toInsert;
- }
- else {
- toInsert->next = head;
- head->prev = toInsert;
- head = toInsert;
- }
-}
-
-template<class T>
-void DoublyLinkedList<T>::popBack() {
- if(empty())
- throw std::exception();
-
- if(tail == head) {
- delete head;
- tail = head = nullptr;
- return;
- }
-
- tail->prev->next = nullptr;
-
- Node* toDelete = tail;
- tail = tail->prev;
- delete toDelete;
-}
-
-
-template<class T>
-void DoublyLinkedList<T>::popFront() {
- if(empty())
- throw std::exception();
-
- Node* toDelete = head;
-
- if(head == tail) {
- delete toDelete;
- head = tail = nullptr;
- return;
- }
-
- head->next->prev = nullptr;
- head = head->next;
- delete toDelete;
-}
-
-template<class T>
-typename DoublyLinkedList<T>::Iterator DoublyLinkedList<T>::begin() {
- return Iterator(head);
-}
-
-template<class T>
-typename DoublyLinkedList<T>::Iterator DoublyLinkedList<T>::end() {
- return Iterator(nullptr);
-}
-
-template<class T>
-void DoublyLinkedList<T>::insert(Iterator at, const T& elem) {
- // Ако е nullptr предполагам, че са подали .end() и добавям в края
- if(at.current == nullptr) {
- tail->next = new Node(elem, nullptr, tail);
- tail = tail->next;
- return;
- }
-
- Node* toInsert = new Node(elem, at.current, at.current->prev);
-
- if(at.current->prev != nullptr)
- at.current->prev->next = toInsert;
-
- at.current->prev = toInsert;
-
- if(at.current == head)
- head = toInsert;
-
- if(at.current == tail)
- tail = toInsert;
-
- at.current = toInsert;
-}
-
-template<class T>
-const T& DoublyLinkedList<T>::back() const {
- if(empty())
- throw std::exception();
-
- return tail->data;
-}
-
-template<class T>
-const T& DoublyLinkedList<T>::front() const {
- if(empty())
- throw std::exception();
-
- return head->data;
-}
-
-template<class T>
-DoublyLinkedList<T>::~DoublyLinkedList(){ free(); }
-
-#endif \ No newline at end of file
diff --git a/Seminar06/Linked-List-Palindrome.cpp b/Seminar06/Linked-List-Palindrome.cpp
deleted file mode 100644
index 256246a..0000000
--- a/Seminar06/Linked-List-Palindrome.cpp
+++ /dev/null
@@ -1,29 +0,0 @@
-#include"../Seminar04/linked-list-utils.h"
-
-template<class T>
-bool isLinkedListPalRec(const LinkedListNode<T>*& begin, const LinkedListNode<T>* end) {
- if(end == nullptr)
- return true;
-
- bool res = isLinkedListPalRec(begin, end->next) && (begin->data == end->data);
-
- begin = begin->next;
- return res;
-}
-
-template<class T>
-bool isLinkedListPal(const LinkedListNode<T>* ll) {
- if(ll == nullptr)
- return true;
-
- const LinkedListNode<T>* begin = ll;
- const LinkedListNode<T>* end = ll;
-
- return isLinkedListPalRec(begin, end);
-}
-
-int main() {
- LinkedListNode<int>* ll = new LinkedListNode(0, new LinkedListNode(1, new LinkedListNode(1)));
-
- std::cout << isLinkedListPal(ll);
-}
diff --git a/Seminar06/README.md b/Seminar06/README.md
deleted file mode 100644
index e333dc2..0000000
--- a/Seminar06/README.md
+++ /dev/null
@@ -1,73 +0,0 @@
-# Двойно свързани списъци. Допълнителни задачи върху списъци.
-
-При едносвързания списък свързаните компоненти пазеха указател към следващия елемент. Ситуацията при двойно свързаните списъци е подобна - отново имаме указател към следващия елемент, но вече имаме и един допълнителен указател към предишния.
-
-![](media/dll.png)
-
-Когато представяме двусвързания списък като указател към началото и указател към края сложност на операциите му са:
-* Добавяне на елемент на произволна позиция: O(n)
-* Добавяне на елемент в началото/края O(1)
-* Премахване на елемент от произволна позиция: O(n)
-* Премахване на елемент от началото / **края**: O(1)
-* Обхождане: O(n)
-Тук вече премахването на елемент от края на списъка е O(1) (Защо?)
-
-Елемента на двойно свързания списък би изглеждал по следния начин:
-```cpp
-template<class T>
-struct DLListElement {
- T data;
- DLListElement<T>* prev;
- DLListElement<T>* next;
-}
-```
-
-## Задача първа
-Да се напише функция
-```cpp
-template<class T>
-void insertSorted(std::list<T>& ll, const T& elem);
-```
-която приема сортиран свързан списък и добавя *elem* на правилното място.
-
-## Задача втора
-Нека имаме двусвързан списък от опашки и символи. Във всяка опашка от началото към края е записан валиден израз в обратна полска нотация. Операторите са [+, -, \*, /] а операндите за улеснение са **едноцифрени числа**.
-
-Да се напише функция, която приема такъв списък, изчислява стойността на всички опашки, и връща дали списъка от резултатите е симетричен спрямо средата.
-
-Пример:
-
-```
- * * +
- | | |
- 7 * 3
- | | |
-+ + 7 *
-| | | |
-5 6 7 3
-| | | |
-4 1 8 1 2
-| | | | |
-* <-> * <-> * <-> * <-> *
-```
-Изход: 1
-
-Примера ще се оцени до 9 <-> 49 <-> 8 <-> 49 <-> 9, който е симетричен списък.
-
-## Задача трета - Linked List Cycyle
-Да се напише функция, която проверява дали в едносвързан списък има цикъл.
-
-## Задача четвърта
-Да се провери дали едносвързан списък е палиндром.
-
-Пример:
-
-Вход:
-``` 1 -> 2 -> 3 -> 2 -> 1 ```
-
-Изход: true
-
-Вход:
-``` 1 -> 2 -> 3 ```
-
-Изход: false
diff --git a/Seminar06/insertSorted.cpp b/Seminar06/insertSorted.cpp
deleted file mode 100644
index c8563fb..0000000
--- a/Seminar06/insertSorted.cpp
+++ /dev/null
@@ -1,63 +0,0 @@
-#include<iostream>
-#include<list>
-#include"../Seminar04/linked-list-utils.h"
-#include<algorithm>
-
-template<class T>
-void insertSorted(LinkedListNode<T>*& ll, const T& elem) {
- LinkedListNode<T>* toInsert = new LinkedListNode<T>(elem);
-
- if (ll == nullptr) { // Празен списък
- ll = toInsert;
- }
- else if (ll->data > elem) { // Елементът е по - малък от всички
- toInsert->next = ll;
- ll = toInsert;
- }
- else if (ll->next == nullptr) { // Списъкът е от един елемент и елементът не стои в началото (ако стоеше щяхме да сме в сл2)
- ll->next = toInsert;
- }
- else { // Елементът може да е в средата или в края
- LinkedListNode<T>* it = ll;
-
- while (it->next != nullptr) {
- if (it->next->data > elem) { // Намерена е позицията на елемента
- LinkedListNode<T>* nNext = it->next;
- it->next = toInsert;
- toInsert->next = nNext;
- return;
- }
-
- it = it->next;
- }
-
- it->next = toInsert; // Ако сме стигнали до тук то мястото на елемента е в края на списъка
- }
-}
-
-template<class T>
-void insertSorted(std::list<T>& ll, const T& elem) {
- auto iter = ll.begin();
-
- while(iter != ll.end()) {
- if(*iter > elem) {
- ll.insert(iter, elem);
- break;
- }
- ++iter;
- }
-
- if(iter == ll.end())
- ll.push_back(elem);
-}
-
-int main() {
- std::list<int> ll;
-
- srand(time(NULL));
-
- for (size_t i = 0; i < 55555; i++)
- insertSorted(ll, rand());
-
- std::cout << std::is_sorted(ll.begin(), ll.end());
-} \ No newline at end of file
diff --git a/Seminar06/linkedListCycle.cpp b/Seminar06/linkedListCycle.cpp
deleted file mode 100644
index 4aa33c6..0000000
--- a/Seminar06/linkedListCycle.cpp
+++ /dev/null
@@ -1,33 +0,0 @@
-#include"../Seminar04/linked-list-utils.h"
-
-bool hasCycle(LinkedListNode<int>* head) {
- LinkedListNode<int> *fast = head;
- LinkedListNode<int> *slow = head;
-
- while (fast && fast->next && slow) {
- fast = (fast->next)->next;
- slow = slow->next;
-
- if (fast == slow)
- return true;
- }
-
- return false;
-}
-
-int main() {
- using Node = LinkedListNode<int>;
-
- Node* last = new Node(6);
-
- Node* list = new Node(1,
- new Node(2,
- new Node(3,
- new Node(4,
- new Node(5,
- last)))));
-
- last->next = list->next->next;
-
- hasCycle(list);
-} \ No newline at end of file
diff --git a/Seminar06/media/dll.png b/Seminar06/media/dll.png
deleted file mode 100644
index 03b98d7..0000000
--- a/Seminar06/media/dll.png
+++ /dev/null
Binary files differ
diff --git a/Seminar06/task02.cpp b/Seminar06/task02.cpp
deleted file mode 100644
index 5f8bf92..0000000
--- a/Seminar06/task02.cpp
+++ /dev/null
@@ -1,110 +0,0 @@
-#include<list>
-#include<iostream>
-#include<queue>
-#include<stack>
-
-bool isSymethric(const std::list<int>& ll) {
- auto start = ll.begin();
- auto end = --(ll.end());
-
- while(start != end) {
- if(*start != *end)
- return false;
-
- ++start;
- if(start == end)
- break;
- --end;
- }
-
- return true;
-}
-
-int evaluateExpr(char op, int fst, int snd) {
- // assert(isOperator(op));
-
- switch (op) {
- case '+':
- return (fst + snd);
- break;
- case '-':
- return (fst - snd);
- break;
- case '*':
- return (fst * snd);
- break;
- case '/':
- return (snd / fst);
- break;
- }
-}
-
-size_t evaluateQueue(std::queue<char> q) {
- std::stack<int> nums;
-
- while(!q.empty()) {
- if(isdigit(q.front())) {
- int cDigit = q.front() - '0';
- q.pop();
- nums.push(cDigit);
- }
- else {
- int fst = nums.top();
- nums.pop();
- int snd = nums.top();
- nums.pop();
- char op = q.front();
- q.pop();
-
- nums.push(evaluateExpr(op, fst, snd));
- }
- }
- return nums.top();
-}
-
-bool solution(const std::list<std::queue<char>>& ll) {
- std::list<int> l;
-
- for(auto elem : ll)
- l.push_back(evaluateQueue(elem));
-
- return isSymethric(l);
-}
-
-int main() {
- std::list<std::queue<char>> test(5);
-
- auto it = test.begin();
- (*it).push('4');
- (*it).push('5');
- (*it).push('+');
-
- ++it;
-
- (*it).push('1');
- (*it).push('6');
- (*it).push('+');
- (*it).push('7');
- (*it).push('*');
- ++it;
-
- (*it).push('8');
- ++it;
-
- (*it).push('1');
- (*it).push('7');
- (*it).push('7');
- (*it).push('*');
- (*it).push('*');
-
- ++it;
-
- (*it).push('2');
- (*it).push('3');
- (*it).push('*');
- (*it).push('3');
- (*it).push('+');
-
-
- std::cout << solution(test);
-} \ No newline at end of file
diff --git a/Seminar07/README.md b/Seminar07/README.md
deleted file mode 100644
index eef8bee..0000000
--- a/Seminar07/README.md
+++ /dev/null
@@ -1,2 +0,0 @@
-## Сортиращи алгоритми
-Прикачвам ви мои стари записки за сортиращи алгоритми. \ No newline at end of file
diff --git a/Seminar07/counting-sort.cpp b/Seminar07/counting-sort.cpp
deleted file mode 100644
index be662f2..0000000
--- a/Seminar07/counting-sort.cpp
+++ /dev/null
@@ -1,40 +0,0 @@
-#include<iostream>
-#include<vector>
-#include<algorithm>
-#include<cassert>
-
-void countingSort(std::vector<unsigned>& v) {
- unsigned elementRange = *std::max_element(v.begin(), v.end()) + 1;
-
- std::vector<unsigned> count(elementRange, 0);
- std::vector<unsigned> result(v.size());
-
- for (size_t i = 0; i < v.size(); i++)
- count[v[i]]++;
-
- for (size_t i = 1; i < elementRange; i++)
- count[i] += count[i - 1];
-
- for (int i = v.size() - 1; i >= 0; i--) {
- result[count[v[i]] - 1] = v[i];
- count[v[i]]--;
- }
-
- v = std::move(result);
-}
-
-int main() {
- std::vector<unsigned> v;
- const int length = 10000;
-
- for (size_t i = 0; i < length; i++)
- v.push_back(rand() * rand());
-
- countingSort(v);
-
- assert(std::is_sorted(v.begin(), v.end()));
-
- // for (int x : v) {
- // std::cout << x << " ";
- // }
-} \ No newline at end of file
diff --git a/Seminar07/Сортиращи алгоритми.pdf b/Seminar07/Сортиращи алгоритми.pdf
deleted file mode 100644
index 4cee79a..0000000
--- a/Seminar07/Сортиращи алгоритми.pdf
+++ /dev/null
Binary files differ
diff --git a/Seminar08/README.md b/Seminar08/README.md
deleted file mode 100644
index a61b2bd..0000000
--- a/Seminar08/README.md
+++ /dev/null
@@ -1,193 +0,0 @@
-# Дървета - част 1
-Свързан граф, който не съдържа цикли наричаме дърво. Дървета се използват от далечната 1875 година когато английски математик на име Arthur Cayley ги използва за да брои видове химични съединения.
-
-## Примери за дървета
-Вероятно всеки вече в един или друг момент се е сблъсквал с дървета. Това е дърво:
-
-![](media/tree-first-example.png)
-
-Това също е дърво:
-
-![](media/tree-second-example.png)
-
-Дърветата са практически използваеми в компютърните науки, много алгоритми и системи ги използват за множество различни цели.
-
-## Малко дефиниции
-| Понятие | Дефиниция
-| :--- | :----:
-| Дърво | Свързан ацикличен граф.
-| Кореново дърво | Дърво, в което точно един връх е избран за корен. Най - често в курса когато пишем дърво разбираме кореново дърво.
-| Листо | Връх без наследници.
-| Вътрешен връх | Връх, който не е листо или корен.
-| Разклоненост | Максималния брой деца на кой да е връх.
-| Височина на връх *u* | Максималното разстояние между *u* и кое да е листо.
-| Дълбочина на връх *u* | Разстоянието между корена и *u*.
-| Височина на дърво | Височината на корена.
-| Ниво *k* | Множеството от всички върхове с дълбочина *к*.
-| Предшественик на връх *u* | За връх *v* казваме, че е предшественик на *u* ако *v* се съдържа в пътя между корена и *u*.
-| Наследник на връх *u* | За връх *v* казваме, че е наследник на *u* ако *u* е предшественик на *v*.
-
-В дефиницията ва предшественик, казваме "пътя между корена и *u*". Важно свойство на дърветата е, че между всеки два върха има **точно един път**. Това свойство е необходимо и достатъчно условие граф да е дърво, ако в един граф имаме точно един път между всеки два върха то той е дърво. Какво би се объркало ако съществуват два върха без път между тях? Какво би станало ако имаме два пътя между два върха?
-
-## Височина на дърво
-С височини на дървета ще се занимаваме много. Неформално, доста често е полезно да държим дървото ниско, това в някакъв смисъл минимизира възможните "слизания надолу".
-
-Колко е максималната височина на дърво с *n* върха? Най - много тя може да стане *n*. Това се случва когато дървото е изродено.
-Пример за изродено дърво с 4 върха:
-
-![](media/stick.png)
-
-Има ли долна граница за височината на дърво? Ако нищо не знаем за дървото, то височината му най - малко може да е 1. Това се случва когато всички възли, различни от корена, са негови наследници (т.е. когато нямаме вътрешни върхове).
-Доста често обаче, когато работим с дървета, знаем тяхната разклоненост.
-Нека имаме дърво с *n* върха и разклоненост *k*. Тогава то не може да стане по - ниско от $\lfloor \log_k n \rfloor$.
-
-Опитайте се да начертаете дърво с разклоненост 2 и 8 върха. Възможно ли е височината му да е по - малка от 3?
-
-## Поддървета
-Неформално, поддърво вкоренено във връх *u* е върхът *u* и всичко под него. Формалната дефиниция ще оставим за друг курс, но това е пример за поддърво, вкоренено във връх 2:
-
-![](media/subtree.png)
-
-## Двоични дървета.
-Двоичното дърво е дърво с максимална разклоненост 2. Това означава, че всеки възел има най - много две деца. В общия случай различаваме децата като ляво и дясно дете (или ляв и десен наследник).
-За двоичните дървета можем също да си мислим като рекурсивно дефинирана структура от данни:
-* Празното дърво е двоично дърво
-* Дърво с един връх и без ребра е двоично дърво
-* Възел с ляв наследник двоично дърво и десен наследник двоично дърво е двоично дърво.
-
-Голяма част от алгоритмите върху двоичните дървета са рекурсивни точно поради този удобен начин да дефинираме двоично дърво.
-
-Дървото в пример 1 е двоично дърво. Дървото в пример 2 не е двоично дърво, понеже има възел от степен 4.
-
-Двоичните дървета поддържат операции по добавяне на елемент и премахване на елемент. Проблемът е, че нищо не знаем за елементите. Нищо не знаем за височината. Единственото което знаем е, че това е дърво с разклоненост 2.
-
-## Двоични наредени дървета
-Двоичното наредено дърво е двоично дърво за което е вярно следното **свойство:**
-
-- Нека *u* е възел в двоично наредено дърво. Стойността на всеки възел от лявото поддърво на *u* е по - малка от стойността на *u*. Стойността на всеки възел от дясното поддърво на *u* е по - голяма от стойността на *u*.
-
-Можем да имаме повтарящи се елементи, това не е проблем. Можем да ги слагаме само отляво или само отдясно, важното е да се поддържа една конвенция.
-
-Едно важно нещо, без което не можем да имаме двоично наредено дърво, е свойството на стойностите на възлите да са сравними. не можем да строим двоично наредено дърво от несравними стойности. Двоичните наредени дървета са сравнително лесни за разбиране и ползване и притежават интересни свойства, с който ще се занимаваме тепърва!
-
-## Представяне на дървета
-
-### Свързано представяне - Двоични дървета
-Свързаното представяне е ужасно удобно когато поддържаме операции като добавяне или изтриване. То ще се ползва най - често в курса, представяме двоично дърво като:
-
-```cpp
-template<class T>
-struct Tree {
- T data;
- Tree* left;
- Tree* right;
-
- Tree(T data, Tree<T>* l = nullptr, Tree<T>* r = nullptr) : data {data}, left {l}, right {r} {}
-}
-```
-
-От тук всеки указател от типа *Tree\<T>\** е валидно дърво. Ако то е празно стойността му би била nullptr. Ако е непразно, данните записани във възела му достъпваме чрез data полето, а лявото и дясното поддърво достъпваме съответно чрез left и right.
-
-Дървото от пример 1, представено по този начин, би изглеждало така:
-
-```cpp
-Tree<int>* createExampleOne() {
- return new Tree<int>(
- 0, // Корена
- new Tree<int>(1), // Лявото поддърво
- new Tree<int>( // Дясното поддърво
- 2,
- new Tree<int>(3, new Tree<int>(5), new Tree<int>(6)),
- new Tree<int>(4, nullptr, new Tree<int>(7))
- )
- );
-}
-```
-
-Или пък примерно, как можем да проверим дали възел е листо? Спомняме си дефиницията на листо и пишем:
-```cpp
-template<class T>
-bool isLeaf(const Tree<T>* t) {
- return t != nullptr && t->left == nullptr && t->right == nullptr;
-}
-```
-
-### Списък на бащите
-Очевидно, чрез свързаното представяне в някакъв смисъл слизаме от корена към листата. Какво правим обаче ако искаме да се качваме от листата към корена?
-
-Нека имаме дърво с *n* върха. Върховете са номерирани с числа от 0 до *n-1*. Едно валидно номериране можем да видим в пример едно. Корена е 0 левия наследник 1, десния 2 и така, по нива, от ляво надясно им даваме индекси от 0 до *n* - 1. Разбира се, това номериране не е единствено, но някак е най - удобно.
-
-Разглеждаме масив tArray с *n* елемента за който е вярно: **В tArray[i] е записан номера на бащата на връх с номер i. Ако върхът с номер i е корен (а корена няма баща) просто пишем -1**.
-Дървото от пример 1 може да се представи чрез списък на бащите по следния начин:
-
-* [-1, 0, 0, 2, 2, 3, 3, 4]
-
-Едно от предимствата на това представяне е, че можем да представим дърво с произволна разклоненост. Все пак няма значение разклонеността, ако можем да номерираме възлите с числа от 0 до *n-1* можем да го представим по този начин.
-
-Но с какво ни помага това? Тук движението става от листата към корена. Вярно е, че за всеки връх, за константно време знаейки номера му, мога да намеря баща му. Е баща му също е възел, тоест мога да намеря и неговия баща.
-
-Така движението в някакъв смисъл не става (корен -> листа) а става (връх -> корен). Това представяне се използва в задачи за намиране на предшественици (и не само).
-
-Недостатъците на това представяне са, че добавянето, проверката дали възел е листо, премахването и други операции върху дървета стават сложни.
-
-Представянето на дървета с масиви е използвано в някои алгоритми и може много скоро нещо подобно да се появи.
-
-### Ляв син десен брат
-Представянето чрез масив на бащите ни позволи да представим дърво с произволна разклоненост. Има поне още два начина да се представи такова дърво. За всеки възел пазим указател към най - левия му син и най - десния му брат:
-
-```cpp
-template<class T>
-struct Tree{
- T data;
- Tree<T>* leftChild;
- Tree<T>* rightSibling;
-};
-```
-
-Така от корена можем да достъпим кой да е връх на произволно разклоненото дърво.
-![](media/left-child-right-sibling.png)
-
-Тук в leftChild указателя на 2 ще е записан адреса на 4. В rightSibling указателя на 2 ще е записан 3. Ако някой възел няма ляво дете или десен брат, то указателя просто е nullptr.
-Предимството е, че за същата памет, с която представихме двоично дърво, можем да представим дърво с произволна разклоненост. Недостатъка е, че имаме последователен достъп до децата. Тоест ако искам да взема третото дете на връх *u* първо ще трябва да сляза до най - лявото му дете и да се предвижа две позиции надясно. Ако често имаме нужда да четем дете на позиция k това може би не би било най - подходящото представяне.
-
-### Чрез вектор от децата
-Тук идеята е супер интуитивна:
-```cpp
-template<class T>
-struct Tree {
- T data;
- std::vector<Tree<T>*> children;
-};
-```
-Ако искаме да вземем третото дете на връх *u* просто правим u->children[2]. Предимството е очевидно - нямаме последователен достъп до децата. Недостатъкът е, че възлите започват да заемат повече памет. Размера на вектора (в x64) е 32 байта. Ако възлите ни са от тип int то размера на структурата би бил 40 байта.
-Вектора ще направи алокации, което също в някакъв смисъл забавя програмата. Но пък веднъж като построим дървото имаме бърз достъп до децата.
-
-### Чрез допълнителен parent указател
-Представянето чрез масив на бащите беше хубаво, но проблемът е, че трудно добавяме и изваждаме елемент от колекцията. Ако искаме да имаме дърво което поддържа добавяне и изтриване и също така може да намира родителя си, то просто добавяме още един указател.
-```cpp
-template<class T>
-struct Tree {
- T data;
- Tree* parent;
- Tree* left;
- Tree* right;
-
- Tree(T data, Tree<T>* p = nullptr, Tree<T>* l = nullptr, Tree<T>* r = nullptr) : data {data}, parent {p}, left {l}, right {r} {}
-}
-```
-Тук проблемът е, че отново плащаме цената от 4 (или 8) байта за допълнителен указател. Но пък ако ни трябва добавяне, премахване и движение както от корен към листа така и листа корен плащаме малко памет и имаме всичко това!
-
-## Задача първа
-Да се реализира функция, която добавя елемент в двоично наредено дърво.
-
-## Задача втора
-Да се напише функция *contains(Tree\<T>\* tree, const T& elem)* която връща дали елемента се съдържа в двоично дърво. Да се реализира същата функция за двоично наредено дърво.
-
-## Задача трета
-Да се напише функция *max((Tree\<T>\* tree)* която връща най - големия елемент в двоично дърво. Да се реализира същата функция за двоично наредено дърво. Да се реализира функция намираща най - малкия елемент.
-
-## Задача четвърта
-Да се реализира функция, която връща височината на двоично дърво.
-
-## Задача пета
-Да се напише функция, която обхожда елементите на двоично дърво по схемата ляво-корен-дясно. (още позната като inorder traversal). Извикайте функцията върху двоично наредено дърво. Какво забелязвате?
diff --git a/Seminar08/height.cpp b/Seminar08/height.cpp
deleted file mode 100644
index c115228..0000000
--- a/Seminar08/height.cpp
+++ /dev/null
@@ -1,14 +0,0 @@
-#include"tree-utils.h"
-#include<iostream>
-
-template<typename T>
-size_t height(const Tree<T>* tree) {
- if (!tree)
- return 0;
-
- return 1 + std::max(height(tree->left), height(tree->right));
-}
-
-int main(){
-
-}
diff --git a/Seminar08/inorder-traversal.cpp b/Seminar08/inorder-traversal.cpp
deleted file mode 100644
index c9a9bd6..0000000
--- a/Seminar08/inorder-traversal.cpp
+++ /dev/null
@@ -1,23 +0,0 @@
-#include "tree-utils.h"
-
-template <typename T>
-void inorderTraversal(const Tree<T> *tree) {
- if (tree == nullptr) {
- return;
- }
-
- inorderTraversal(tree->left);
- std::cout << tree->data << ' ';
- inorderTraversal(tree->right);
-}
-
-int main() {
- Tree<int> *root = new Tree<int>(8, new Tree<int>(3, new Tree<int>(1), new Tree<int>(6, new Tree<int>(4), new Tree<int>(7))), new Tree<int>(10, nullptr, new Tree<int>(14, new Tree<int>(13))));
-
- inorderTraversal(root); //изпечатва елементите на дървото сортирано
- std::cout << '\n';
- printTree(root);
-
- freeTree(root);
- return 0;
-} \ No newline at end of file
diff --git a/Seminar08/insert-in-bst.cpp b/Seminar08/insert-in-bst.cpp
deleted file mode 100644
index ac4c9f4..0000000
--- a/Seminar08/insert-in-bst.cpp
+++ /dev/null
@@ -1,36 +0,0 @@
-#include<iostream>
-#include"tree-utils.h"
-
-// Тук допускаме да има повторения. Ако искаме да няма повторения втория else ще стане else if(t->data > elem)
-template<class T>
-void insertInBST(Tree<T>*& t, const T& elem) {
- if(t == nullptr) {
- t = new Tree<T>(elem);
- return;
- }
- else if(t->data < elem) {
- insertInBST(t->right, elem);
- }
- else {
- insertInBST(t->left, elem);
- }
-}
-
-int main() {
- Tree<int>* example = new Tree<int>(4, new Tree<int>(2), new Tree<int>(6));
-
- insertInBST(example, 1);
- printTree(example);
-
- // За любопитните: колко ли ще е височината на дърво от 50 случайни числа?
- Tree<int>* secondExample = nullptr;
- srand(time(NULL));
- for (int i = 0; i < 50; i++)
- insertInBST<int>(secondExample, rand() % 100);
-
- exportToTex(secondExample, "file.txt");
- //-------------------------------------------------
-
- freeTree(example);
- freeTree(secondExample);
-} \ No newline at end of file
diff --git a/Seminar08/media/left-child-right-sibling.png b/Seminar08/media/left-child-right-sibling.png
deleted file mode 100644
index 180f782..0000000
--- a/Seminar08/media/left-child-right-sibling.png
+++ /dev/null
Binary files differ
diff --git a/Seminar08/media/stick.png b/Seminar08/media/stick.png
deleted file mode 100644
index 9fcc5ad..0000000
--- a/Seminar08/media/stick.png
+++ /dev/null
Binary files differ
diff --git a/Seminar08/media/subtree.png b/Seminar08/media/subtree.png
deleted file mode 100644
index 5875be2..0000000
--- a/Seminar08/media/subtree.png
+++ /dev/null
Binary files differ
diff --git a/Seminar08/media/tree-first-example.png b/Seminar08/media/tree-first-example.png
deleted file mode 100644
index 4fe94bf..0000000
--- a/Seminar08/media/tree-first-example.png
+++ /dev/null
Binary files differ
diff --git a/Seminar08/media/tree-second-example.png b/Seminar08/media/tree-second-example.png
deleted file mode 100644
index bf57c99..0000000
--- a/Seminar08/media/tree-second-example.png
+++ /dev/null
Binary files differ
diff --git a/Seminar08/min-max-elem.cpp b/Seminar08/min-max-elem.cpp
deleted file mode 100644
index cbd8560..0000000
--- a/Seminar08/min-max-elem.cpp
+++ /dev/null
@@ -1,64 +0,0 @@
-#include "tree-utils.h"
-#include <cmath>
-
-// for regular binary trees
-template <typename T>
-T max_elem(Tree<T> *tree) {
- T res = tree->data;
-
- if (tree->left != nullptr) {
- res = std::max(res, max_elem(tree->left));
- }
- if (tree->right != nullptr) {
- res = std::max(res, max_elem(tree->right));
- }
-
- return res;
-}
-
-template <typename T>
-T min_elem(Tree<T> *tree) {
- T res = tree->data;
-
- if (tree->left != nullptr) {
- res = std::min(res, min_elem(tree->left));
- }
- if (tree->right != nullptr) {
- res = std::min(res, min_elem(tree->right));
- }
-
- return res;
-}
-
-// for binary search trees
-template <typename T>
-T max_elem_bst(Tree<T> *tree) {
- while (tree->right != nullptr)
- tree = tree->right;
-
- return tree->data;
-}
-
-template <typename T>
-T min_elem_bst(Tree<T> *tree) {
- while (tree->left != nullptr)
- tree = tree->left;
-
- return tree->data;
-}
-
-int main() {
- Tree<int> *regularTree = new Tree<int>(2, new Tree<int>(3, new Tree<int>(4), new Tree<int>(5)), new Tree<int>(13, new Tree<int>(7), new Tree<int>(8)));
- printTree(regularTree);
- std::cout << "Maximum element in regular binary tree: " << max_elem(regularTree) << '\n';
- std::cout << "Minimum element in regular binary tree: " << min_elem(regularTree) << '\n';
-
- Tree<int> *binarySearchTree = new Tree<int>(8, new Tree<int>(3, new Tree<int>(1), new Tree<int>(6, new Tree<int>(4), new Tree<int>(7))), new Tree<int>(10, nullptr, new Tree<int>(14, new Tree<int>(13))));
- printTree(binarySearchTree);
- std::cout << "Maximum element in bs tree: " << max_elem_bst(binarySearchTree) << '\n';
- std::cout << "Minimum element in bs tree: " << min_elem_bst(binarySearchTree) << '\n';
-
- freeTree(regularTree);
- freeTree(binarySearchTree);
- return 0;
-} \ No newline at end of file
diff --git a/Seminar08/tree-utils.h b/Seminar08/tree-utils.h
deleted file mode 100644
index 3ce0d93..0000000
--- a/Seminar08/tree-utils.h
+++ /dev/null
@@ -1,230 +0,0 @@
-#ifndef TREE_UTIL_IMPL
-#define TREE_UTIL_IMPL
-
-#include<iostream>
-#include<string>
-#include<fstream>
-#include<assert.h>
-
-// Важни неща:
-template<class T>
-struct Tree {
- T data;
- Tree* left;
- Tree* right;
-
- Tree(T data, Tree<T>* l = nullptr, Tree<T>* r = nullptr) : data{ data }, left{ l }, right{ r } {}
-};
-
-template<class T>
-void freeTree(Tree<T>* t) {
- if (t == nullptr)
- return;
- freeTree(t->left);
- freeTree(t->right);
- delete t;
-}
-
-template<class T>
-void insertInBST(Tree<T>*& t, const T& elem, bool hasDuplicates = true) {
- if (t == nullptr) {
- t = new Tree<T>(elem);
- return;
- }
- else if (t->data < elem) {
- insertInBST(t->right, elem, hasDuplicates);
- }
- else if ((t->data > elem) || hasDuplicates) {
- insertInBST(t->left, elem, hasDuplicates);
- }
-}
-
-template<class T>
-const Tree<T>* getMinNode(const Tree<T>* t) {
- assert(t != nullptr);
-
- const Tree<T>* iter = t;
-
- while (iter->left) {
- iter = iter->left;
- }
- return iter;
-}
-
-template<class T>
-bool removeElement(Tree<T>*& t, const T& elem) {
- if (t == nullptr)
- return false;
-
- if (t->data > elem) {
- return removeElement(t->left, elem);
- }
- else if (t->data < elem) {
- return removeElement(t->right, elem);
- }
-
- // Намерили сме елемента
- if (!t->left && !t->right) { // Листо
- delete t;
- t = nullptr; // !!
- }
- else if (!t->left && t->right) { // Има само дясно поддърво
- Tree<T>* toDelete = t;
- t = t->right;
- delete toDelete;
- }
- else if (t->left && !t->right) { // Има само ляво поддърво
- Tree<T>* toDelete = t;
- t = t->left;
- delete toDelete;
- }
- else { // Вътрешен връх.
- T newData = getMinNode(t->right)->data;
- t->data = newData;
- removeElement(t->right, newData);
- }
- return true;
-}
-
-template<class T>
-bool containsBST(const Tree<T>* t, const T& elem) {
- if (t == nullptr)
- return false;
-
- if (t->data == elem)
- return true;
-
- if (t->data < elem)
- return containsBST(t->right, elem);
-
- return containsBST(t->left, elem);
-}
-
-
-// За по - любопитните премахване на възел
-// само с пренасочване на указатели и без копие на T
-template<class T>
-void innerVertexRemoveCase(Tree<T>*& inVertex) {
- assert(inVertex && inVertex->left && inVertex->right);
-
- Tree<T>** minNode = &inVertex->right;
- Tree<T>** minNodeParent = &inVertex;
-
- bool firstGoingDown = true;
-
- while ((*minNode)->left) {
- minNode = &(*minNode)->left;
-
- minNodeParent = firstGoingDown ? &(*minNodeParent)->right : &(*minNodeParent)->left;
-
- firstGoingDown = false;
- }
-
- Tree<T>* originalRight = (*minNode)->right;
-
- (*minNode)->left = inVertex->left;
-
- if (!firstGoingDown)
- (*minNode)->right = inVertex->right;
-
- Tree<T>* toDelete = inVertex;
-
- inVertex = (*minNode);
-
- if (!firstGoingDown)
- (*minNodeParent)->left = originalRight;
-
- delete toDelete;
-}
-
-template<class T>
-bool removeElementPointerSwap(Tree<T>*& t, const T& elem) {
- if (t == nullptr)
- return false;
-
- if (t->data > elem) {
- return removeElementPointerSwap(t->left, elem);
- }
- else if (t->data < elem) {
- return removeElementPointerSwap(t->right, elem);
- }
-
- // Намерили сме елемента
- if (!t->left && !t->right) { // Листо
- delete t;
- t = nullptr;
- }
- else if (!t->left && t->right) { // Има само дясно поддърво
- Tree<T>* toDelete = t;
- t = t->right;
- delete toDelete;
- }
- else if (t->left && !t->right) { // Има само ляво поддърво
- Tree<T>* toDelete = t;
- t = t->left;
- delete toDelete;
- }
- else { // Вътрешен връх.
- innerVertexRemoveCase(t);
- }
- return true;
-}
-
-// Неща за мое удобство, не е нужно да ги четете:
-
-// Взето от:
-// https://stackoverflow.com/questions/36802354/print-binary-tree-in-a-pretty-way-using-c
-template<class T>
-void printBT(const std::string& prefix, const Tree<T>* node, bool isLeft) {
- if (node != nullptr) {
- std::cout << prefix;
-
- std::cout << (isLeft ? "|--" : "`--");
-
- std::cout << node->data << std::endl;
-
- printBT(prefix + (isLeft ? "| " : " "), node->left, true);
- printBT(prefix + (isLeft ? "| " : " "), node->right, false);
- }
-}
-
-template<class T>
-void printTree(const Tree<T>* node) {
- printBT("", node, false);
-}
-
-// Следващите две функции са малко по - красив начин да изпринтим дърво, но го конвертира къмм LaTeX документ
-// Когато извикате exportToTex("file.txt") ще ви създаде фейл с код.
-// Пейстнете кода в overleaf.com и ще ви излезе дървото.
-
-// Не е перфектно но пък е по - удобно от конзолата. Това е за демонстрации, не е нужно да го учите или разбирате.
-template<class T>
-void recFillFileStream(std::ofstream& outFile, const Tree<T>* r) {
- if (r == nullptr)
- return;
-
- outFile << "[" << r->data << " ";
- recFillFileStream(outFile, r->left);
- recFillFileStream(outFile, r->right);
-
- outFile << "]";
-}
-
-template<class T>
-void exportToTex(const Tree<T>* root, const char* filePath) {
- std::ofstream outFile(filePath, std::ios::trunc);
-
- outFile << "\\documentclass[tikz,border=10pt]{standalone}" << std::endl;
- outFile << "\\usepackage[linguistics]{forest}" << std::endl;
- outFile << "\\begin{document}" << std::endl;
- outFile << "\\begin{forest}" << std::endl;
-
- recFillFileStream(outFile, root);
-
- outFile << "\\end{forest}";
- outFile << "\\end{document}";
-
- outFile.close();
-}
-
-#endif \ No newline at end of file
diff --git a/Seminar09/README.md b/Seminar09/README.md
deleted file mode 100644
index 3bc2307..0000000
--- a/Seminar09/README.md
+++ /dev/null
@@ -1,119 +0,0 @@
-# Дървета - част 2. Балансирани дървета, ротации и задачи върху дървета.
-
-## Минимум и максимум в дърво
-Последния семинар разглеждахме задачата за намиране на минимален или максимален елемент в дърво. Тази задача е сравнително лесна, но нека разгледаме следния случай:
-
-```cpp
-template<class T>
-T maxElem(const Tree<T>* t) {
- T result = t->data;
-
- if(t->left != nullptr)
- result = std::max(result, maxElem(t->left));
-
- if(t->right != nullptr)
- result = std::max(result, maxElem(t->right));
-
- return result;
-}
-```
-Това решение работи почти винаги. Какво става ако t e nullptr?
-
-Ако знаехме, че дървото е от тип int, лесно можехме да връщаме INT_MAX, но в случая не знаем какъв тип е скрит зад Т.
-Един от начините да се справим с този проблем е да връщаме T\* вместо Т. Така, ако дървото е nullptr ние също ще връщаме nullptr. Това е валиден начин, и може би стандартния начин по който бихме подходили в С или във версиите на С++ преди С++17.
-
-## std::optional\<T>
-std::optional\<T> е клас който в някакъв смисъл "обвива" елемент от тип Т. Както името подсказва той или има стойност.. или няма.
-Този тип се поддържа от с++17, та ако искате да го използвате бъдете сигурни, че компилирате с правилната версия на с++.
-
-Примерно, кодът използвайки std::optional би изглеждал по следния начин:
-
-```cpp
-#include<optional>
-#include"tree-utils.h"
-
-template<class T>
-std::optional<T> max(const Tree<T>* t) {
- if (t == nullptr)
- return {}; // Това означава, че std::optional<T> няма стойност
-
- std::optional<T> left = max(t->left); // Вземи макса на левия
- std::optional<T> right = max(t->left); // Вземи макса на десния
-
- T res = t->data;
- // Ако левия има value тоест дървото не е празно...
- if (left.has_value() && left.value() > res)
- res = left.value();
-
- // Аналогично за десния
- if (right.has_value() && right.value() > res)
- res = right.value();
-
- return res;
-}
-
-int main() {
- Tree<int>* t = nullptr;
- std::optional<int> result = max(t);
-
- if(result.has_value())
- std::cout << "Max element is: " << result.value() << std::endl;
- else
- std::cout << "Empty tree!!";
-}
-```
-Логиката зад std::optional далеч не идва от с++. Езици като Haskell, Rust и други поддържат подобни структури.
-
-## Балансирани дървета
-Последния семинар дефинирахме височина на дърво и се разбрахме, че това ще бъде важно понятие за нас. Намекнахме, че е желателно да държим дърветата си ниски. Едно свойство на дърветата, което ги държи сравнително ниски е **балансираността.**
-
-Двоично дърво наричаме **балансирано** ако за всеки негов възел височините на лявото поддърво и на дясното поддърво се различават **най - много с единица**.
-
-Също така дърво ще наричаме **идеално балансирано** ако за всеки негов възел броя на възлите в лявото поддърво и броя на възлите в дясното поддърво се различават най - много с единица.
-
-В балансираните и идеално балансираните дървета сложността на операциите добавяне, търсене, изтриване стават $\mathcal{O} (\log_2 n)$.
-
-С балансирани дървета ще се занимаваме много подробно следващия път. Засега само дефинираме неща, които ще ни бъдат от голяма полза при реализацията на едно такова дърво.
-
-## Ротации и запазване на балансираността
-Ротацията е операция върху балансирани двоични дървета, която запазва балансираността им.
-
-![](media/rotations.png)
-
-Ротациите обаче променят височината на лявото и дясното поддърво на корена.
-
-Нека разгледаме 1, където правим ротация около х. Височината на дясното поддърво е 1 + max(h(beta), h(gamma)).
-
-След ротацията височината на дясното поддърво е h(gamma). Следователно височината е **намаляла поне с единица**.
-
-По същата логика височината на лявото поддърво расте отново поне с единица.
-
-Разбрахме се, че ще се стараем да си държим дърветата ниски. Тези операции ще ни бъдат полезни в тази ни задача.
-## Задача първа
-Да се напише функция, която проверява дали дадено дърво е двоично наредено дърво.
-
-## Задача втора
-Да се напише функция, която от сортиран вектор построява двоично наредено дърво.
-
-## Задача трета
-Да се напише функция, която премахва възел от двоично наредено дърво.
-
-## Задача четвърта
-Да се напише функция, която проверява дали две дървета са еднакви.
-
-## Задача пета
-Да се реализират ляво и дясна ротация за произволно дърво.
-
-## Задача шеста (За домашно)
-Нека имаме двоично наредено дърво T от цели числа.
-
-```
-pred(x) = max{y | y е ключ на възел в Т и y < x} // Предшественик
-succ(x) = min{y | y е ключ на възел в T и y > x} // Наследник
-```
-
-Да се реализира pred(t, x) и succ(t, x).
-Бележка: Не е нужно х да се съдържа в дървото.
-
-## Задача седма (Контролно)
-Да се напише функция, която намира сумата на всички елементи на двоично наредено дърво от цели числа, които имат нечетен брой наследници в интервала [x, y] (т.е. сумата на броя елементи в лявото поддърво и броя елементи в дясното поддърво в интервала [x, y] е нечетно число). Нека x и y са параметри на функцията.
diff --git a/Seminar09/exam1.cpp b/Seminar09/exam1.cpp
deleted file mode 100644
index 26eb3cb..0000000
--- a/Seminar09/exam1.cpp
+++ /dev/null
@@ -1,35 +0,0 @@
-#include"../Seminar08/tree-utils.h"
-
-// pair.first -> Сумата до момента
-// pair.second - Броя на наследниците, които изпълняват условието ключовете им да влизат в интервала в поддървото
-std::pair<int, int> findSumHelper(const Tree<int>* t, int x, int y) {
- if(t == nullptr)
- return std::make_pair(0, 0);
-
- std::pair<int, int> l = std::make_pair(0, 0);
- std::pair<int, int> r = std::make_pair(0, 0);
-
- if(t->data >= x)
- l = findSumHelper(t->left, x, y);
-
- if(t->data <= y)
- r = findSumHelper(t->right, x, y);
-
- bool oddChildren = ((l.second + r.second) % 2);
-
- int sum = l.first + r.first;
- int count = l.second + r.second + (t->data >= x && t->data <= y);
-
- if(oddChildren)
- sum += t->data;
-
- return std::make_pair(sum, count);
-}
-
-int findSum(const Tree<int>* t, int x, int y) {
- return findSumHelper(t, x, y).first;
-}
-
-int main() {
-
-} \ No newline at end of file
diff --git a/Seminar09/media/rotations.png b/Seminar09/media/rotations.png
deleted file mode 100644
index 0312e29..0000000
--- a/Seminar09/media/rotations.png
+++ /dev/null
Binary files differ
diff --git a/Seminar09/solutions.cpp b/Seminar09/solutions.cpp
deleted file mode 100644
index 94958e5..0000000
--- a/Seminar09/solutions.cpp
+++ /dev/null
@@ -1,140 +0,0 @@
-#include"../Seminar08/tree-utils.h"
-#include<optional>
-#include<vector>
-#include<assert.h>
-#include<algorithm>
-
-template<class T>
-std::optional<T> getMax(const Tree<T>* t) {
- if (t == nullptr)
- return {}; // Няма стойност
-
- T res = t->data;
-
- std::optional<T> left = getMax(t->left);
- std::optional<T> right = getMax(t->right);
-
- if (left.has_value())
- res = std::max(res, left.value());
-
- if (right.has_value())
- res = std::max(res, right.value());
-
- return res;
-}
-
-bool isBSTRec(const Tree<int>* t, int min, int max) {
- if (t == nullptr)
- return true;
-
- if (t->data < min || t->data > max)
- return false;
-
- return isBSTRec(t->left, min, t->data) && isBSTRec(t->right, t->data, max);
-}
-
-bool isBST(const Tree<int>* t) {
- return isBSTRec(t, INT_MIN, INT_MAX);
-}
-
-template<class T>
-Tree<T>* buildFromRec(const std::vector<T>& v, int start, int end) {
- if (end < start)
- return nullptr;
-
- int mid = (end - start) / 2 + start;
-
- return new Tree<T>(v[mid], buildFromRec(v, start, mid - 1), buildFromRec(v, mid + 1, end));
-}
-
-template<class T>
-Tree<T>* buildFrom(const std::vector<T>& v) {
- return buildFromRec(v, 0, v.size() - 1);
-}
-
-template<class T>
-bool isSameTree(const Tree<T>* fst, const Tree<T>* snd) {
- if (!fst && !snd)
- return true;
-
- if ((fst && !snd) || (!fst && snd) || fst->data != snd->data)
- return false;
-
- return isSameTree(fst->left, snd->left) && isSameTree(fst->right, snd->right);
-}
-
-template<class T>
-Tree<T>* clone(const Tree<T>* t) {
- if (!t)
- return nullptr;
-
- return new Tree<T>(t->data, clone(t->left), clone(t->right));
-}
-
-template<class T>
-void rotateLeft(Tree<T>*& root) {
- assert(root->right != nullptr);
-
- Tree<T>* originalRight = root->right;
- root->right = originalRight->left;
- originalRight->left = root;
- root = originalRight;
-}
-
-template<class T>
-void rotateRight(Tree<T>*& root) {
- assert(root->left != nullptr);
-
- Tree<T>* originalLeft = root->left;
- root->left = originalLeft->right;
- originalLeft->right = root;
- root = originalLeft;
-}
-
-void rotationsTests() {
- std::vector<int> v;
- for (size_t i = 0; i < 100; i++)
- v.push_back(rand() % 100);
-
- std::sort(v.begin(), v.end());
-
- Tree<int>* example = buildFrom(v);
- Tree<int>* exampleClone = clone(example);
-
- // Тестваме лява ротация:
- // Тука не правя проверки за nullptr понеже не е това целта на този пример
- Tree<int>* alpha = clone(example->left);
- Tree<int>* beta = clone(example->right->left);
- Tree<int>* gamma = clone(example->right->right);
-
- rotateLeft(example);
-
- assert(isSameTree(alpha, example->left->left));
- assert(isSameTree(beta, example->left->right));
- assert(isSameTree(gamma, example->right));
-
- freeTree(alpha); freeTree(beta); freeTree(gamma);
-
- // Тествам дясна ротация
- alpha = clone(example->left->left);
- beta = clone(example->left->right);
- gamma = clone(example->right);
-
- rotateRight(example);
-
- assert(isSameTree(alpha, example->left));
- assert(isSameTree(beta, example->right->left));
- assert(isSameTree(gamma, example->right->right));
-
- freeTree(alpha); freeTree(beta); freeTree(gamma);
-
- // Лявата ротация е симетрична на дясната следователно като направим лява + дясна трябва да остане същото дърво
- assert(isSameTree(example, exampleClone));
-
- freeTree(example);
- freeTree(exampleClone);
-}
-
-int main() {
- rotationsTests();
-} \ No newline at end of file
diff --git a/Seminar10/AVLTree.hpp b/Seminar10/AVLTree.hpp
deleted file mode 100644
index 355d1c5..0000000
--- a/Seminar10/AVLTree.hpp
+++ /dev/null
@@ -1,203 +0,0 @@
-#ifndef AVL_TREE_IMPL
-#define AVL_TREE_IMPL
-
-#include<algorithm>
-#include<cassert>
-#include<cstddef>
-
-template<class T>
-class AVLTree {
-private:
-
- struct Node {
- T data;
- Node* left;
- Node* right;
- int height;
-
- static int getHeight(const Node* r) {
- if (r == nullptr)
- return 0;
-
- return r->height;
- }
-
- static void rotateLeft(Node*& r) {
- assert(r->right != nullptr);
-
- Node* originalRight = r->right;
- r->right = originalRight->left;
- originalRight->left = r;
- r = originalRight;
- }
-
- static void rotateRight(Node*& r) {
- assert(r->left != nullptr);
-
- Node* originalLeft = r->left;
- r->left = originalLeft->right;
- originalLeft->right = r;
- r = originalLeft;
- }
-
- static void balanceLeft(Node*& r) {
- assert(r);
-
- int rootBalance = getBalanceFactor(r);
- int leftBalance = getBalanceFactor(r->left);
-
- if (rootBalance == -2) {
- if (leftBalance == 1) {
- rotateLeft(r->left);
- updateHeight(r->left->left);
- updateHeight(r->left);
- }
-
- rotateRight(r);
- updateHeight(r->right);
- updateHeight(r);
- }
- }
-
- static void balanceRight(Node*& r) {
- assert(r);
-
- int rootBalance = getBalanceFactor(r);
- int rightBalance = getBalanceFactor(r->right);
-
- if (rootBalance == 2) {
- if (rightBalance == -1) {
- rotateRight(r->right);
- updateHeight(r->right->right);
- updateHeight(r->right);
- }
-
- rotateLeft(r);
- updateHeight(r->left);
- updateHeight(r);
- }
- }
-
- static void updateHeight(Node* r) {
- if (r == nullptr)
- return;
- r->height = std::max(getHeight(r->left), getHeight(r->right)) + 1;
- }
-
- static int getBalanceFactor(const Node* r) {
- if (r == nullptr)
- return 0;
-
- return getHeight(r->right) - getHeight(r->left);
- }
-
- Node(const T& d, Node* l, Node* r, int h) : data{ d }, left{ l }, right{ r }, height{ h } {}
- };
-
- Node* findMinNode(Node* r) {
- if (r->left == nullptr)
- return r;
-
- return findMinNode(r->left);
- }
-
- void insertRec(Node*& r, const T& elem) {
- if (r == nullptr) {
- r = new Node(elem, nullptr, nullptr, 1);
- size++;
- return;
- }
-
- if (r->data < elem) {
- insertRec(r->right, elem);
-
- Node::updateHeight(r->right);
- Node::balanceRight(r);
- }
- else if (r->data > elem) {
- insertRec(r->left, elem);
-
- Node::updateHeight(r->left);
- Node::balanceLeft(r);
- }
- }
-
- bool removeRec(Node*& r, const T& elem) {
- if (r == nullptr) {
- return false;
- }
-
- if (r->data < elem) {
- removeRec(r->right, elem);
-
- Node::updateHeight(r);
- Node::balanceLeft(r);
- }
- else if (r->data > elem) {
- removeRec(r->left, elem);
-
- Node::updateHeight(r);
- Node::balanceRight(r);
- }
- else {
- if (!r->left && !r->right) {
- delete r;
- r = nullptr;
- return true;
- }
- else if (r->left && !r->right) {
- Node* toDelete = r;
- r = r->left;
- delete toDelete;
- }
- else if (!r->left && r->right) {
- Node* toDelete = r;
- r = r->right;
- delete toDelete;
- }
- else {
- root->data = findMinNode(root->right)->data;
- removeRec(r->right, r->data);
- Node::updateHeight(r);
- Node::balanceRight(r);
- }
- }
- return true;
- }
-
- void freeRec(Node* r) {
- if (r == nullptr)
- return;
-
- freeRec(r->left);
- freeRec(r->right);
- delete r;
- }
-
-public:
- AVLTree() : root{ nullptr }, size{ 0 } {}
-
- // TBI
- AVLTree(const AVLTree<T>& other) = delete;
- AVLTree& operator=(const AVLTree<T>& other) = delete;
- bool contains(const T& elem);
-
- void insert(const T& elem) {
- insertRec(root, elem);
- }
-
- bool remove(const T& elem) {
- return removeRec(root, elem);
- }
-
- ~AVLTree() {
- freeRec(root);
- }
-
-private:
-
- Node* root;
- size_t size;
-};
-
-#endif
diff --git a/Seminar10/README.md b/Seminar10/README.md
deleted file mode 100644
index a483bb4..0000000
--- a/Seminar10/README.md
+++ /dev/null
@@ -1,456 +0,0 @@
-# AVL дървета.
-
-## Целта за днес
-| Операции | build(x) | find(x) | insert/delete | min/max | prev/next |
-| ----------- | ----------- |----------- | ----------- | ---------- | --------- |
-| Binary tree | O(nlog(n)) | O(h) | O(h) | O(h) | O(h) |
-| AVL tree | O(nlog(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |
-
-## Балансирани дървета
-Двоично дърво, което поддържа log(n) височина при динамични операции се нарича **балансирано дърво**.
-
-Има много схеми за балансиране на дървета което влезе и съществуването на различни видове балансирани дървета (Red-Black tree, 2-3 Tree...)
-
-Първата схема за балансиране на дървета е предложена през 1962 година от Andelson-Velsky и Landis от където идва и името на AVL дървото.
-
-```
-Баланс фактор на възел k определяме като: bf(k) = h(k->right) - h(k->left).
-```
-
-```
-Целта ни е за всеки възел k bf(k) да е в множеството {-1, 0, 1}.
-```
-
-Трябва да поддържаме това свойство при всяко добавяне или премахване на възел. Тук на помощ идват ротациите!
-
-Тяхната реализация както и тестове за тяхната коректност можете да намерите [тук](https://github.com/stoychoX/Data-structures-and-algorithms/blob/main/Seminar09/solutions.cpp#L75).
-
-## Как разбираме, че сме нарушили балансираността на възел?
-Ако bf(k) не е в {-1, 0, 1} то тогава сме нарушили балансираността. Трябва ни начин да пресмятаме баланс фактора на всеки възел колкото се може по - бързо. Както в много неща в този курс, за да пресмятаме бързо баланс фактора на възел ще жертваме малко памет и ще записваме височината на поддървото във всеки възел. Структурата би изглеждала така:
-
-```cpp
-template<class T>
-struct Node {
- T data;
- Node<T>* left;
- Node<T>* right;
- int height;
-
- Node(const T& d, Node<T>* l, Node<T>* r, int h) : data {d}, left {l}, right {r}, height{h} {}
-};
-```
-Сега, за константно време можем да смятаме баланс фактора:
-```cpp
-template<class T>
-int getHeight(const Node<T>* r) {
- if(r == nullptr)
- return 0;
- return r->height;
-}
-
-template<class T>
-int getBalanceFactor(const Node<T>* r) {
- if(r == nullptr)
- return 0;
-
- return getHeight(r->right) - getHeight(r->left);
-}
-```
-Разбира се, тази сметка е вярна тогава и само тогава когато височините на лявото и дясното поддърво са коректни.
-
-## insert
-Искаме да напишем операция, която за логаритмично време добавя елемент в дървото и запазва неговата балансираност.
-
-В началото започваме по стандартния начин - рекурсивно намираме къде да добавим елемента и го добавяме като листо. След това обаче става интересно - какво става ако този елемент разбалансира дървото? Той увеличава височината на (логаритмичен) брой поддървета и е напълно възможно да направи някой баланс фактор на 2 или -2.
-
-Използваме факта, че рекурсивно сме слезли до някое листо и когато излизаме от рекурсията чрез ротации поправяме балансираността на дървото.
-
-При добавяне на елемент ни се налага да направим **най - много две ротации**
-
-Също така при добавяне на елемент трябва да променяме височината. Разбрахме се, че я пазим, а това, че добавяме елемент я променя. За щастие това може да стане за константно време:
-
-```cpp
-template<class T>
-void updateHeight(Node<T>*& r) {
- if(r == nullptr)
- return;
-
- r->height = std::max(getHeight(r->left), getHeight(r->right)) + 1;
-}
-```
-
-Алгоритъмът за добавяне би изглеждал по следния начин:
-
-```cpp
-template<class T>
-void addElement(Node<T>*& root, const T& elem) {
- // Стигнали сме до дъното на рекурсията
- if(root == nullptr) {
- root = new Node<T>(elem, nullptr, nullptr, 1);
- return;
- }
- else if(root->data < elem) {
- addElement(root->right, elem); // добавяме елемента, но работата ни не е приключила
-
- balanceRight(root); // balance проверява дали има дисбаланс в дървото което променихме
- // и ако има го коригира!
-
- updateHeight(root); // Добавихме възел, все пак трябва да си оправим височината!
- }
- else if(root->data > elem) { // Аналогично на горния случай.
- addElement(root->left, elem);
-
- balanceLeft(root);
-
- updateHeight(root);
- }
-}
-```
-Как можем да оптимизираме този алгоритъм като знаем, че винаги при вмъкване се правят най - много две ротации?
-
-Логиката по добавянето е почти същата като при стандартното двоично наредено дърво, но този път имаме функциии поддържащи баланса на r.
-
-Да разгледаме какви случаи имаме при дисбалансираността. Нега разгледаме случая в който дясното поддърво е дисбалансирано. Нещата за лявото са абсолютно симетрични!
-
-## Имаме три случая за баланс фактора на дясното поддърво.
-
-
-## bf(root.right) = 1
-![](media/avl-disbalance.png)
-
-Тук виждаме, че просто лява ротация около корена ни свърши работа, супер.
-
-## bf(root.right) = 0
-![](media/avl-disbalance-0.png)
-
-Тук също просто лява ротация ни свърши работа.
-
-## bf(root.right) = -1
-![](media/avl-disbalance-1.png)
-
-Е, какво направихме с тази лява ротация? Само направихме нещата по - лоши. Лявата ротация не ни върши работа тук и трябва на намерим друг начин да се справим.
-
-В предните два случая нещата с лява ротация работиха. Дали има начин да отида в някой от тях?
-
-<span style="color:red">
-<b>Забелязвам, че ако направя дясна ротация около корена на дясното поддърво (с височина k + 1) вече баланс фактора на дясното поддърво ще бъде 1.</b>
-</span>
-
-
-<span style="color:red">
-<b>Това обаче е случай 1, който знаем, че с лява ротация работи.
-</b>
-</span>
-
-<span style="color:red">
-Тоест просто правя дясна ротация около корена на дясното поддърво (за да отида в сл. 1) и после правим лява ротация около корена.
-</span>
-
-Нарисувайте си по подобен на примерите начин как ще изглежда това.
-
-Хайде да го напишем на код:
-
-```cpp
-template<class T>
-void balanceRight(Node<T>*& root) {
- // Това не трябва да се случва!
- assert(root != nullptr);
-
- int rootBalance = getBalanceFactor(root);
- int rightSubTreeBalance = getBalanceFactor(root->right);
-
- // Както видяхме в картинката десния дисбаланс е със стойност 2 :)
- if(balance == 2) {
- // Това е гадния случай в който ми трябва още една ротация.
- if(rightSubTreeBalance == -1) {
- rotateRight(root->right);
-
- // Променям височините на двете поддървета, които са засегнати от ротацията
- updateHeight(root->right->right);
- updateHeight(root->right);
- }
-
- // Сега вече или съм в случай 1 или в случай 2 и просто си правя лява ротация
- rotateLeft(root);
-
- // Отново актуализирам височините на възлите засегнати от ротацията
- updateHeight(root->left);
- updateHeight(root);
- }
-}
-```
-
-Проверката за ляв дисбаланс ще изглежда по симетричен начин.
-При левия дисбаланс баланс факторът при който трябва да оправим нещата няма да е 2 а ще е -2. Също така случая, в който ни трябват две ротации няма да е -1 а ще е 1.
-
-## Премахване на елемент
-При стандартните дървета имахме следния алгоритъм:
-1. Намери елемента. Ако го няма върни false.
-2. Ако елемента е листо просто го изтрий
-3. Ако елемента има само ляво или само дясно поддърво просто лявото (или дясното) поддърво заемат неговото място а той бива изтрит.
-4. В противен случай намери най малкия елемент в дясното му поддърво. Този елемент става корен а ние изтриваме елемента, който ни беше зададено да изтрием.
-
-В този алгоритъм обаче винаги се премахва едно листо. Това значи, че височината на логаритмичен брой поддървета ще се промени, а на нас това не ни харесва.
-
-Това което трябва да добавим в алгоритъма е балансиране на пътя, по който сме преминали. Също така трябва динамично да променяме височините така, че те да са коректни.
-
-```cpp
-
-template<class T>
-bool removeElement(Node<T>*& root, const T& elem) {
- if(root == nullptr)
- return false;
-
- if(root->data < elem) {
- bool res = removeElement(root->right, elem);
-
- // Не е възможно да има десен дисбаланс, понеже променяме дясното поддърво
- updateHeight(root);
- balanceLeft(root);
- return res;
- }
- else if(root->data > elem) {
- bool res = removeElement(root->left, elem);
- updateHeight(root);
- balanceRight(root);
- return res;
- }
-
- if(!root->left && !root->right) {
- delete root;
- root = nullptr;
- }
- else if(root->left && !root->right) {
- Node<T>* toDelete = root;
- root = root->left;
- delete toDelete;
-
- updateHeight(root);
- }
- else if(!root->left && root->right) {
- Node<T>* toDelete = root;
- root = root->right;
- delete toDelete;
-
- updateHeight(root);
- }
- else {
- // Това е неефикасно.
- root->data = findMinElement(root->right)->data;
- removeElement(root->right, root->data);
-
- updateHeight(root);
- balanceLeft(root);
- }
-
- return true;
-}
-```
-Коментара "това е неефикасно" има за цел да намекне, че тази реализация на алгоритъма за премахване може да бъде подобрена. Проблемът е, че T може да е всякакъв тип, вкючително и доста тежък за копиране тип. Също така слизаме да намерим минималния възел един път и след това слизаме още един път за да го премахнем. Това са две разходки, което може да се подобри.
-
-Решението може да стане само с разместване на указатели. Причината да не го реализираме така тук е за да може да се концентрирате не толкова върху техническата реализация а върху самия алгоритъм.
-
-[Тук](https://github.com/stoychoX/AVL-vs-SkipList/blob/main/AVL/AVLTree.hpp#L409) можете да погледнете примерен начин възел да се премахне само чрез разместване на указатели. Това не е единствения начин, можете да се опитате да го направите сами и да pull-request-нете кода за да го обсъдим.
-
-## Дърветата и stl
-В стандартната библиотека на c++ няма нещо като std::tree\<T>. Въпреки това stl ни предоставя обекти, които в реализацията си използват балансирани дървета.
-
-### std::set
-Сет (или множество) е асоциативен контейнер който съдържа сортирана последователност от обекти от тип Т. Търсене, премахване и добавяне имат логаритмична сложност. В стл сетовете се имплементират чрез червено черни дървета, които също като AVL дървото поддържат логаритмична височина (използвайки друга схема за балансиране).
-
-Както в множествата, обектите в сета **са уникални**. За него можете също да си мислите като за дърво, което при insert не допуска повторения на ключове.
-
-Да видим бърз пример:
-```cpp
-#include<iostream>
-#include<set>
-
-int main() {
- std::set<int> s;
-
- for (size_t i = 0; i < 10; i++)
- s.insert(i);
-
- // find метода връща итератор към елемента
- std::set<int>::iterator elem = s.find(4);
-
- // Това извежда 4
- std::cout << *elem << " ";
-
- // Отиваме на следващия елемент... Но колекцията е сортирана!
- ++elem;
-
- // Това извежда 5
- std::cout << *elem;
-}
-```
-
-Супер, но какво връща find когато елемента го няма? Как изобщо да премахвам елемент? Следващия пример отговаря на тези въпроси.
-
-```cpp
-#include<iostream>
-#include<set>
-
-int main() {
- std::set<int> s;
-
- // Вкарваме 10 пъти 5, но елементите нямат повторения!
- for (size_t i = 0; i < 10; i++)
- s.insert(5);
-
- // Премахваме 5
- s.erase(5);
-
- std::set<int>::iterator it = s.find(5);
-
- // Когато елемента го няма в множеството просто връща end() итератора (както е с много други обекти в stl)
- if (it == s.end())
- std::cout << "Element not found!";
-}
-```
-
-Та обекта го няма - връща end итератора. Лесна работа. Супер сега обаче наредбата не ми харесва. Искам колекцията ми да е сортирана в обратен ред. Сортировката зависеше единствено от компаратор функцията (rли релацията по която сортирам, която в първия пример по подразбиране е <). Дали не мога да накарам моя сет да сортира по >?
-Това би станало по следния начин:
-
-```cpp
-#include<iostream>
-#include<set>
-
-int main() {
- // std::greater<T> е структура с оператор()
- // Дали ще можем ние да си напишем наша структура с operator()
- // И да я пуснем като comparator? Опитайте!
- std::set<int, std::greater<int>> s;
-
- for (size_t i = 0; i < 10; i++)
- s.insert(i);
-
- for (auto x : s)
- std::cout << x << " ";
-}
-```
-
-Често ни се налага да държим в множество обекти които не са числа а примерно някакви структури или класове. Да разгледаме следния код:
-
-```cpp
-#include<set>
-
-struct Entity {
- int x;
- int y;
-};
-
-int main() {
- std::set<Entity> s;
-
- s.insert({1, 1});
-}
-```
-Тази програма ще ни върне грешка. Все пак std::set държи последователността сортирана. Тук по какво да сортира? Компилатора ни се оплаква, че нямаме operator<. Нека си напишем и да видим какво ще се случи:
-
-```cpp
-#include<set>
-
-struct Entity {
- int x;
- int y;
-
- bool operator<(const Entity& e) const {
- return x < e.x;
- }
-};
-
-int main() {
- std::set<Entity> s;
-
- s.insert({1, 1});
-}
-```
-Сега вече всичко работи. Ами ако ни трябват повторения?
-
-## std::multiset
-std::multiset е мултимножество. Освен стандартните функции multiset може да ни каже колко обекта от този тип имаме чрез метода count. Тук метода erase премахва **всички** елементи с подадена стойност! Ако искаме да премахнем един елемент използваме метода extract. extract връща елемент от тип node handle който държи в себе си стойността на извадения елемент.
-
-```cpp
-#include<set>
-#include<iostream>
-
-int main() {
- std::multiset<int> s;
- s.insert(10);
- s.insert(10);
- s.insert(10);
- auto k = s.extract(10);
-
- // 10 2
- std::cout << k.value() << " " << s.count(10);
-}
-```
-
-## std::map
-std::map е сортиран контейнер, който реализира Key-Value двойки. Какво ще рече това? Примерно, даден ми е някакъв текст и искам да си направя хистограма (за всяка негова буква пазя по колко пъти се среща). Също така, на стандартния изход искам да изведа за всеки символ, колко пъти се среща, но буквите трябва да са в сортиран ред.
-
-Следния код ще свърши работа:
-```cpp
-#include<iostream>
-#include<map>
-#include<string>
-
-int main() {
- std::string str;
- std::getline(std::cin, str, '\n');
-
- std::map<char, int> hist;
-
- for (const char& c : str) {
- hist[c]++;
- }
-
- // Всеки елемент от hist e наредена двойка <Key, Value>
- for (const auto& elem : hist) {
- std::cout << elem.first << "x" << elem.second << std::endl;
- }
- /*
- zbbzaaz
- ax2
- bx2
- zx3
- */
-}
-```
-В случай ключовете са елементи от тип char е стойностите са колко пъти се среща този char с текста. std::map отново се реализира чрез червено черно дърво. Ключовете са елементите по които строим това дърво (логично, понеже по тях търсим). Забележете, че не е нужно да правим insert. Самото индексиране създава възел за нас.
-
-```
-T& std::map<K, V>::operator[](const Key&):
-
-Returns a reference to the value that is mapped to a key equivalent to key, performing an insertion if such key does not already exist.
-```
-
-Какво е важно за ключовете? Отново, както при std::set, трябва да имаме operator<() дефиниран за типа, представляващ ключ.
-
-## std::multimap
-std::multimap също реализира Key-Value двойка, но този път можем да имаме повторение на ключовете.
-Този път вече нямаме operator[], понеже ключът не е единствен.
-
-```
-Multimap is an associative container that contains a sorted list of key-value pairs, while permitting multiple entries with the same key.
-```
-
-## Wordle
-Играта е следната. В началото си намисляме някаква дума, след това потребителя се опитва да я познае. Потребителя въвежда някаква дума, като знае дължината на намислената от нас дума, и за всяка буква от думата му трябва да му кажем дали я има и ако я има дали е на правилното място или не.
-
-Нека извеждаме 2 ако е на правилното място, 1 ако се съдържа но не е на правилното място и 0 ако я няма.
-
-Примерно:
-```
-Дума: access
-Опит: arrest
-Изход:
-a 2
-r 0
-r 0
-e 2
-s 2
-t 0
-```
-Как това ще стане с multimap? Примера е качен в wordle.cpp. \ No newline at end of file
diff --git a/Seminar10/media/avl-disbalance-0.png b/Seminar10/media/avl-disbalance-0.png
deleted file mode 100644
index acf5cb8..0000000
--- a/Seminar10/media/avl-disbalance-0.png
+++ /dev/null
Binary files differ
diff --git a/Seminar10/media/avl-disbalance-1.png b/Seminar10/media/avl-disbalance-1.png
deleted file mode 100644
index 6d94cd6..0000000
--- a/Seminar10/media/avl-disbalance-1.png
+++ /dev/null
Binary files differ
diff --git a/Seminar10/media/avl-disbalance.png b/Seminar10/media/avl-disbalance.png
deleted file mode 100644
index a583f2b..0000000
--- a/Seminar10/media/avl-disbalance.png
+++ /dev/null
Binary files differ
diff --git a/Seminar10/wordle.cpp b/Seminar10/wordle.cpp
deleted file mode 100644
index 967e807..0000000
--- a/Seminar10/wordle.cpp
+++ /dev/null
@@ -1,55 +0,0 @@
-#include<iostream>
-#include<map>
-#include<string>
-
-int determineChar(const std::multimap<char, int>& mp, size_t idx, char currChar) {
- // find връща end ако не го намери
- auto currentIterator = mp.find(currChar);
-
- if (currentIterator == mp.end())
- return 0;
-
- // Докато не стигнем края, което е възможно,
- // и докато все още сме на този символ
- while (currentIterator != mp.end() && currentIterator->first == currChar) {
- if (currentIterator->second == idx)
- return 2;
- ++currentIterator;
- }
-
- return 1;
-}
-
-int main() {
- std::string word;
- std::cout << "Enter word to guess: " << std::endl;
-
- std::getline(std::cin, word, '\n');
- std::multimap<char, int> wordle;
-
- for (size_t i = 0; i < word.size(); i++)
- wordle.insert({ word[i], i });
-
- bool guessed = false;
-
- while (!guessed) {
- std::cout << "Enter guess with length: " << wordle.size() << std::endl;
- std::getline(std::cin, word, '\n');
-
- if (word.length() != wordle.size()) {
- std::cout << "Invalid length" << std::endl;
- continue;
- }
-
- guessed = true;
-
- for (size_t i = 0; i < word.size(); i++) {
- int result = determineChar(wordle, i, word[i]);
-
- std::cout << word[i] << " " << result << std::endl;
-
- if (result != 2)
- guessed = false;
- }
- }
-} \ No newline at end of file
diff --git a/Seminar11/DFS-Additional.cpp b/Seminar11/DFS-Additional.cpp
deleted file mode 100644
index a5022e3..0000000
--- a/Seminar11/DFS-Additional.cpp
+++ /dev/null
@@ -1,200 +0,0 @@
-// Малко допълнителни неща покрай дфс ако ви е интересно.
-#include<iostream>
-#include"Graph-Impl/AdjacencyListGraph/AdjListGraph.h"
-#include"Graph-Impl/MatrixGraph/MatrixGraph.h"
-#include<vector>
-#include<algorithm>
-
-using std::vector;
-using vertex_t = AdjListGraph::vertex_t; // Типа представящ връх в графа
-
-class DFSExamples {
-private:
- vector<size_t> in;
- vector<size_t> out;
- vector<vertex_t> parent;
-
-public:
-
-void DFS_Visit(const AdjListGraph& g, size_t& time, vertex_t s) {
- in[s] = time;
- time++;
-
- const auto& adj = g.adjacent(s);
-
- for(const auto& v : adj) {
- if(in[v.to] == -1) {
- parent[v.to] = s;
- DFS_Visit(g, time, v.to);
- }
- }
-
- time++;
- out[s] = time;
-}
-
-void DFS(const AdjListGraph& g, bool showDetails) {
- // Нека си представим, че имаме време. Всяка стъпка на алгоритъма отнема една единица време.
- size_t time = 0;
-
- // Всеки връх бива открит в някакво време. Нека в този масив записваме кога е бил открит всеки връх.
- in = vector(g.vertexCount(), (size_t)(-1));
-
- // С всеки връх приключваме по някое време. Той няма повече непосетени съседи и спираме да се интересуваме от него.
- // Нека в този масив записваме кога се случва това.
- out = vector(g.vertexCount(), (size_t)(-1));
-
- // std::vector<bool> visited(g.vertexCount(), false);
- // - от този масив вече нямаме нужда. Връх v e посетен когато in[v] != -1.
-
- // Също така в примера видяхме, че DFS прави дърво. Нека си запазим това дърво.
- // Тук стандартното представяне на дърво е неудобно, затова ще представяме дървото като масив от бащите.
- // Примомняне: Ако v e връх parent[v] е бащата на v или -1 ако v e корен.
- parent = vector(g.vertexCount(), (vertex_t)(-1));
-
- // За всеки връх
- for (vertex_t i = 0; i < g.vertexCount(); i++)
- if(in[i] == -1) // Ако не е посетен
- DFS_Visit(g, time, i); // Посети го и посети всички върхове достижими от него
-
- // Да видим какво имаме
- if(showDetails) {
- for (vertex_t i = 0; i < g.vertexCount(); i++) {
- std::cout << "Vertex " << i << std::endl;
- std::cout
- << "Discovered at: " << in[i] << std::endl
- << "Finished at: " << out[i] << std::endl
- << "Parent: " << parent[i] << std::endl << std::endl;
- }
- }
-}
-
-void DFS_Visit_Tsort(const MatrixGraph g, size_t& time, vertex_t s) {
- in[s] = time;
- time++;
-
- const auto& adj = g.adjacent(s);
-
- for(const auto& v : adj) {
- if(in[v] == -1) {
- parent[v] = s;
- DFS_Visit_Tsort(g, time, v);
- }
- }
-
- time++;
- out[s] = time;
-}
-
-// Топологически сортировки, Job scheduling
-// Защо са ни тези масиви in и out? Те ни дават информация, която можем да използваме за други интересни алгоритми.
-// Ще оставим подробното им разглеждане на други курсове, тук само ще разгледаме един бърз пример.
-
-// Нека си представим, че имаме някакви задачи за вършене. Абсолютно вероятно е някои от тези задачи да зависят от други.
-// Примерно, не мога да кандидатствам за университет ако преди това нямам диплома за завършен 12 клас
-// (въпреки, че май е възможно в някои нови български университети).
-//
-// Можем да си представим задачите като върхове, а това, че задача А трябва да се изпълни преди задача Б да
-// бележим чрез ориентирано ребро А -> Б.
-//
-// Искам така да си подредя задачите, че да ги изпълня без да нарушавам зависимостите.
-//
-// Твърдя, че ако пусна DFS, и сортирам върховете по out стойности в намаляващ ред това решава задачата ми.
-//
-// Накратко, защо това е вярно?
-// Нека имам V -> U. Има два случая, или да открия V преди U или да открия U преди V.
-//
-// 1. Откривам V преди U. Да де, но имам ребро от V към U, Следователно ще открия и финализирам U преди да финализирам V.
-// Сега out[U] > out[V] и не нарушавам зависимостите.
-// 2. Ако открия U преди V, ще финализирам U преди да стигна до V. В графа няма цикли и ако имаше път от U -> V това би затворило цикъл.
-// Тоест ще финализирам U преди да открия V. От тук следва, че out[U] > in[V] > out[V], което отново влече наредба, която не нарушава зависимостите.
-// Няма други случаи.
-
-void DFS_Tsort(const MatrixGraph& g) {
- size_t time = 0;
-
- in = vector(g.vertexCount(), (size_t)(-1));
- out = vector(g.vertexCount(), (size_t)(-1));
- parent = vector(g.vertexCount(), (vertex_t)(-1));
-
- for (vertex_t i = 0; i < g.vertexCount(); i++)
- if(in[i] == -1)
- DFS_Visit_Tsort(g, time, i);
-
- std::vector<std::pair<vertex_t, size_t>> result(g.vertexCount());
-
- for (vertex_t i = 0; i < g.vertexCount(); i++)
- result[i] = {i, out[i]};
-
- auto comp = [](std::pair<vertex_t, size_t>& fst, std::pair<vertex_t, size_t>& snd) -> bool {
- return fst.second > snd.second;
- };
-
- std::sort(result.begin(), result.end(), comp);
-
- for(const auto& vertexOutPair : result)
- std::cout << vertexOutPair.first << " ";
-}
-
-// Използвам матричния, понеже той е ориентиран.
-void tsort(const MatrixGraph& g) {
- size_t time = 0;
-
- // Нулираме масивите
- in = vector(g.vertexCount(), (size_t)(-1));
- out = vector(g.vertexCount(), (size_t)(-1));
- parent = vector(g.vertexCount(), (vertex_t)(-1));
-
- DFS_Tsort(g);
-}
-};
-
-int main() {
- DFSExamples d;
-
- // Нека си вземем графа от примера
- // Там върховете са номерирани от 1 до 12
- // Тук от 0 до 11
- AdjListGraph g(12);
-
- g.addEdge(0, 2, 1);
- g.addEdge(0, 4, 1);
- g.addEdge(0, 5, 1);
- g.addEdge(0, 8, 1);
-
- g.addEdge(1, 7, 1);
- g.addEdge(1, 3, 1);
-
- g.addEdge(2, 4, 1);
- g.addEdge(2, 5, 1);
- g.addEdge(2, 6, 1);
- g.addEdge(2, 7, 1);
-
- g.addEdge(3, 9, 1);
-
- g.addEdge(4, 6, 1);
-
- g.addEdge(8, 11, 1);
- g.addEdge(8, 10, 1);
-
- g.addEdge(10, 11, 1);
-
- d.DFS(g, true);
-
- // Пример за топосортировка
- MatrixGraph tsort(9);
-
-
- // https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/resources/mit6_006f11_lec14_orig/
- // Този граф е взет от линка и е на страница 5.
- tsort.addDirectedEdge(5, 3, 1);
- tsort.addDirectedEdge(4, 3, 1);
- tsort.addDirectedEdge(4, 2, 1);
- tsort.addDirectedEdge(2, 1, 1);
- tsort.addDirectedEdge(1, 0, 1);
- tsort.addDirectedEdge(7, 2, 1);
- tsort.addDirectedEdge(7, 6, 1);
- tsort.addDirectedEdge(6, 1, 1);
-
- d.DFS_Tsort(tsort);
-} \ No newline at end of file
diff --git a/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.cpp b/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.cpp
deleted file mode 100644
index 3cbbdd0..0000000
--- a/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.cpp
+++ /dev/null
@@ -1,82 +0,0 @@
-#include"AdjListGraph.h"
-
-using vertex_t = AdjListGraph::vertex_t;
-using weight_t = AdjListGraph::weight_t;
-
-AdjListGraph::AdjListGraph(size_t vertexCount) {
- data = std::vector<std::list<Edge>>(vertexCount, std::list<Edge>());
-}
-
-void AdjListGraph::addVertex() {
- data.push_back(std::list<Edge>());
-}
-
-void AdjListGraph::removeVertex(vertex_t v) {
- if(!validVertex(v))
- throw "Invalid vertex";
-
- // Премахва самия връх
- data.erase(data.begin() + v);
-
- // За всеки от останалите върхове ако
- // има елемент, който сочи към него трябва да се изтрие
- // ако има елемент, който е по - голям от него трябва да се намали с 1
-
- for(auto& vertexList : data) {
- vertexList.remove_if([&](Edge e) -> bool { return e.to == v; });
-
- for(Edge& e : vertexList)
- if(e.to > v)
- e.to--;
- }
-}
-
-bool AdjListGraph::validVertex(vertex_t v) const {
- return v < data.size();
-}
-
-void AdjListGraph::addEdge(vertex_t from, vertex_t to, weight_t w) {
- if(!validVertex(from) || !validVertex(to))
- throw "Invalid vertex";
-
- data[from].push_back( {to, w} );
- data[to].push_back( {from, w} );
-}
-
-void AdjListGraph::removeEdge(vertex_t from, vertex_t to) {
- if(!validVertex(from) || !validVertex(to))
- throw "Invalid vertex";
-
- data[from].remove_if([&](Edge e) -> bool {return e.to == to; });
- data[to].remove_if([&](Edge e) -> bool {return e.to == from; });
-}
-
-bool AdjListGraph::hasEdge(vertex_t from, vertex_t to) const {
- if(!validVertex(from) || !validVertex(to))
- throw "Invalid vertex";
-
- for(const Edge& e : data[from])
- if(e.to == to)
- return true;
-
- return false;
-}
-
-weight_t AdjListGraph::getWeight(vertex_t from, vertex_t to) const {
- if(!validVertex(from) || !validVertex(to))
- throw "Invalid vertex";
-
- for(const Edge& e : data[from])
- if(e.to == to)
- return e.weight;
-
- return 0;
-}
-
-std::vector<AdjListGraph::Edge> AdjListGraph::adjacent(vertex_t v) const {
- return std::vector<Edge>(data[v].begin(), data[v].end());
-}
-
-size_t AdjListGraph::vertexCount() const {
- return data.size();
-} \ No newline at end of file
diff --git a/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.h b/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.h
deleted file mode 100644
index 40446fd..0000000
--- a/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.h
+++ /dev/null
@@ -1,50 +0,0 @@
-/*
-Тегловен неориентиран граф представен чрез списъци на съседство.
-
-Предимства:
-* Паметта която използваме е вече O(|V| + |E|)
-* Вземането на всички съседи е по - бързо
-
-Недостатъци:
-* Да проверим дали има ребро между два върха вече не е O(1)
-
-*/
-#ifndef ADJ_LIST_GRAPH_IMPL
-#define ADJ_LIST_GRAPH_IMPL
-
-#include<vector>
-#include<list>
-#include<algorithm>
-
-class AdjListGraph {
- public:
- using vertex_t = unsigned int;
- using weight_t = unsigned int;
-
- private:
- struct Edge {
- vertex_t to;
- weight_t weight;
- };
-
- std::vector<std::list<Edge>> data;
-
- public:
- AdjListGraph(size_t n);
-
- void addVertex();
- void removeVertex(vertex_t);
- bool validVertex(vertex_t) const;
-
- void addEdge(vertex_t, vertex_t, weight_t);
- void removeEdge(vertex_t, vertex_t);
-
- weight_t getWeight(vertex_t, vertex_t) const;
- bool hasEdge(vertex_t, vertex_t) const;
-
- size_t vertexCount() const;
-
- std::vector<Edge> adjacent(vertex_t) const;
-};
-
-#endif \ No newline at end of file
diff --git a/Seminar11/Graph-Impl/AdjacencyListGraph/src.cpp b/Seminar11/Graph-Impl/AdjacencyListGraph/src.cpp
deleted file mode 100644
index b0484e0..0000000
--- a/Seminar11/Graph-Impl/AdjacencyListGraph/src.cpp
+++ /dev/null
@@ -1,19 +0,0 @@
-#include<iostream>
-#include<list>
-#include<algorithm>
-#include"AdjListGraph.h"
-
-int main() {
- AdjListGraph g(10);
-
- g.addEdge(0, 1, 1);
- g.addEdge(0, 2, 1);
- g.addEdge(0, 3, 1);
- g.addEdge(0, 4, 1);
-
- auto res = g.adjacent(1);
-
- for(auto i : res) {
- std::cout << i.to << " ";
- }
-} \ No newline at end of file
diff --git a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp b/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp
deleted file mode 100644
index b5835f8..0000000
--- a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp
+++ /dev/null
@@ -1,97 +0,0 @@
-#include"MatrixGraph.h"
-
-using vertex_t = MatrixGraph::vertex_t;
-using weight_t = MatrixGraph::weight_t;
-
-MatrixGraph::MatrixGraph(size_t v) {
- data = std::vector<std::vector<weight_t>>(v, std::vector<weight_t>(v, 0));
-}
-
-bool MatrixGraph::validVertex(vertex_t v) const {
- return v < data.size();
-}
-
-bool MatrixGraph::adjacent(vertex_t from, vertex_t to) const {
- if(!validVertex(from) || !validVertex(to))
- throw "Invalid vertex";
-
- return data[from][to] > 0;
-}
-
-void MatrixGraph::addDirectedEdge(vertex_t from, vertex_t to, weight_t w) {
- if(!validVertex(from) || !validVertex(to))
- throw "Invalid vertex";
-
- data[from][to] = w;
-}
-
-void MatrixGraph::addEdge(vertex_t from, vertex_t to, weight_t w) {
- addDirectedEdge(from, to, w);
- addDirectedEdge(to, from, w);
-}
-
-void MatrixGraph::addVertex() {
- for(auto& v : data)
- v.push_back(0);
-
- data.push_back(std::vector<weight_t>());
-}
-
-void MatrixGraph::removeEdge(vertex_t from, vertex_t to) {
- if(!validVertex(from) || !validVertex(to))
- throw "Invalid vertex";
-
- data[from][to] = 0;
-}
-
-void MatrixGraph::removeVertex(vertex_t v) {
- if(!validVertex(v))
- throw "Invalid vertex";
-
- data.erase(data.begin() + v);
-
- for(auto& vertex : data)
- vertex.erase(vertex.begin() + v);
-}
-
-weight_t MatrixGraph::getWeight(vertex_t from, vertex_t to) const {
- if(!validVertex(from) || !validVertex(to))
- throw "Invalid vertex";
-
- return data[from][to];
-}
-
-std::vector<vertex_t> MatrixGraph::getSuccessors(vertex_t from) const {
- if(!validVertex(from))
- throw "Invalid vertex";
-
- std::vector<vertex_t> result;
-
- for (size_t i = 0; i < data.size(); i++)
- if(data[from][i] > 0)
- result.push_back(i);
-
- return result;
-}
-
-std::vector<vertex_t> MatrixGraph::getPredecessors(vertex_t from) const {
- if(!validVertex(from))
- throw "Invalid vertex";
-
- std::vector<vertex_t> result;
-
- for (size_t i = 0; i < data.size(); i++)
- if(data[i][from] > 0)
- result.push_back(i);
-
- return result;
-}
-
-std::vector<vertex_t> MatrixGraph::adjacent(vertex_t from) const {
- return getSuccessors(from);
-}
-
-
-size_t MatrixGraph::vertexCount() const {
- return data.size();
-} \ No newline at end of file
diff --git a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h b/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h
deleted file mode 100644
index aade1a1..0000000
--- a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h
+++ /dev/null
@@ -1,52 +0,0 @@
-/*
-Ориентиран тегловен граф представен чрез матрица на съседство.
-
-Плюсове:
-* Лесна имплементация
-* Проверка за ребро, премахване на ребро, добавяне на ребро са O(1)
-
-Минуси:
-* Паметта винаги е O(|V|^2)
-* Намирането на предшественици (наследници) или в неориентирания случай на съседи отнема O(|V|) време.
-
-weight_t => тип, чрез който представяме тежест
-vertex_t => тип, чрез който представяме връх
-*/
-
-#ifndef GRAPH_IMPL_H
-#define GRAPH_IMPL_H
-
-#include<vector>
-#include<cstddef>
-
-class MatrixGraph {
- public:
- using vertex_t = unsigned int;
- using weight_t = unsigned int;
-
- private:
- std::vector<std::vector<weight_t>> data;
-
- public:
- MatrixGraph(size_t);
-
- void addVertex();
- void removeVertex(vertex_t);
-
- void addDirectedEdge(vertex_t from, vertex_t to, weight_t w);
- void addEdge(vertex_t from, vertex_t to, weight_t w);
- void removeEdge(vertex_t from, vertex_t to);
-
- bool validVertex(vertex_t) const;
- weight_t getWeight(vertex_t, vertex_t) const;
-
- size_t vertexCount() const;
- bool adjacent(vertex_t from, vertex_t to) const;
-
- std::vector<vertex_t> getSuccessors(vertex_t) const;
- std::vector<vertex_t> getPredecessors(vertex_t) const;
- // Same as getSuccessors, here for interface purposes.
- std::vector<vertex_t> adjacent(vertex_t) const;
-};
-
-#endif \ No newline at end of file
diff --git a/Seminar11/README.md b/Seminar11/README.md
deleted file mode 100644
index eac0759..0000000
--- a/Seminar11/README.md
+++ /dev/null
@@ -1,187 +0,0 @@
-# Графи
-
-## Определение
-```
-Граф е наредена двойка G = (V, E), където V e непразно множество, чиито елементи се наричат върхове. Множеството E е крайно множество от ребра. Ребро наричаме двуелементно множество {v1, v2}, където v1 и v2 са елементи на V.
-```
-Графите, както подсказва името, могат да бъдат изобразени "графично". Важно е да не се бърка рисунката на граф със самия граф. Един граф може да има безброй много рисунки.
-
-Примерно, нека V = {v1, v2, v3}, E = {{v1, v2}, {v2, v3}, {v3, v1}}. Този граф може да се нарисува като:
-
-![](media/graph.png)
-
-## Видове графи
-
-### Ориентирани и неориентирани графи
-Графът, който видяхте на първия пример е неориентиран. Когато говорим за граф, и не поясним дали е ориентиран или не, става въпрос за неориентиран граф. Понякога е удобно да различаваме дали реброто e от v към u или от u към v. За ребрата на ориентирания граф вече може да си мислим не като за двуелементни множества от върхове а за **наредени двойки от върхове**.
-
-```
-Припомняне:
-Когато имаме двуелементно множество {v1, v2} е вярно, че {v1, v2} = {v2, v1}. При наредените двойки това не е вярно. За v1 != v2 имаме (v1, v2) != (v2, v1).
-Наредената двойка (a, b) e множеството {{a}, {a, b}}. Да твърдим, че (a, b) = (b, a) e същото като да твърдим, че {{a}, {a, b}} = {{b}, {a, b}}. Това става единствено когато a = b.
-```
-
-Сега, разглеждаме ребрата на графа като наредени двойки.
-Нека V = {v1, v2, v3} и E = {(v1, v2), (v2, v3), (v2, v1)}.
-Този граф би изглеждал така:
-
-
-![](media/dir-graph.png)
-
-
-### Тегловен граф
-Често е полезно да "закачим" някакви тегла на ребрата. Примерно, ако върховете на графа представляват някакви забележителности, а ребрата са пътища между тях, теглата могат да представляват времето в минути, което отнема да стигнем от v1 до v2.
-
-Примерно, това е **рисунка** на тегловен граф:
-
-
-![](media/weighted-graph.png)
-
-Можем да имаме и тегловни ориентирани графи.
-
-
-![](media/weighted-dirscted-graph%20(1).png)
-
-### Мултиграфи
-Неформално, в мултиграфа позволяваме да има много ребра с краища едни и същи два върха. Отново може да имаме тегловни и нетегловни мултиграфи. Може да имаме ориентирани и неориентирани мулти графи, нищо не ни спира.
-
-## Дефиниции
-| Понятие | Дефиниция
-| :--- | :----:
-| Примка в граф | Ребро от типа {v, v}
-| Път в граф | Редица от върхове (v_1, v_2, ..., v_n) за които е в сила {v_i, v_{i+1}} е елемент на E.
-| Цикъл в граф | Път **p** за който v_1 = v_n се нарича цикъл.
-| Прост път | Път **p** e прост ако всички елементи в редицата са уникални.
-| Дължина на път | Дължината на пътя е **броя на ребрата в него**.
-| Ацикличен граф | Граф, в който няма цикъл. Ако в графът има цикъл то той се нарича цикличен.
-| Свързан граф | Граф е свързан ако за всеки два върха u, v има път между u и v.
-| Силно свързани върхове | В **ориентиран граф** казваме, че върхове u, v са силно свързани ако съществува път от u до v и от v до u
-| Силно свързан граф | Силно свързан граф е **ориентиран** граф, за който всеки два върха са силно свързани.
-
-# Основни операции върху графи:
-Графите (като абстрактен тип данни) трябва да поддържат (част) от следните операции:
-
-- **addVertex** - добавяне на нов връх
-- **removeVertex** - премахване на връх
-- **addEdge** - добавяне на ново ребро
-- **removeEdge** - премахване на ребро
-- **getSuccessors** - взимане на наследниците на връх (при ориентирани графи)
-- **getPredecessors** - взимане на предшествениците на връх (при ориентирани графи)
-- **adjacent** - взимане на съседните върхове на даден връх (при неориентирани графи)
-
-# Представяне на графи
-Графите намират огромно приложение в програмирането. Ако обаче започнем да представяме граф като множество от върхове и второ множество от двуелементни множества, това представяне би било бавно.
-
-Ние искаме да решаваме задачи върху графи с компютър. Представете си, че върховете на графа са именувани с етикети от 0 до |V| - 1.
-
-Наистина, няма значение как именуваме върховете, дали ще е {0, 1..., |V| - 1} дали ще е {v1, v2...} просто имаме нужда от начин, по който да се обръщаме към тях.
-
-## Матрици на съседство
-Нека си представим булева матрица |V|x|V|. Разбрахме, се че имената на върховете са между 0 и |V| - 1. Ако има ребро между v и u то в нашата матрица това ще отбелязваме с true. Ако няма ребро го отбелязваме с false.
-
-Нека разгледаме матрицата:
-```
-{
- {0, 1, 1},
- {1, 0, 1},
- {1, 1, 0}
-}
-```
-Това е точно матрицата, която представя графът от пример 1, ако си мислим за v1 = 0, v2 = 1, v3 = 2.
-
-Ако матрицата представя неориентиран граф, то тя е симетрична спрямо главния диагонал.
-
-Ако матрицата представя ориентиран граф и примерно имаме ребро от 5 към 7, но не и от 7 към 5, ще е вярно, че
-
-```
-matrix[5][7] = true
-matrix[7][5] = false
-```
-
-Можем да представяме тегловни графи чрез матрица на съседство. Тази матрица вече няма да е булева понеже ще искаме да записваме някъде теглата на ребрата.
-
-Може да направим матрица от тип int, в която ако matrix[i][j] = 0 нямаме ребро между i и j а в противен случай стойността на matrix[i][j] e теглото на реброто започващо от i и завършващо в j.
-
-Но какво става ако искаме да имаме ребра с тежест 0? Тогава трябва да изберем друга стойност, която да ни представя липсата на ребро, примерно INT_MIN или INT_MAX.
-
-Предимствата на това представяне са, че можем да проверим, дали има ребро от който и да е връх до който и да е връх за константно време. Също така за линейно време за някой възел можем да вземем всички негови съседни ребра.
-
-Проблемът е, че често това представяне заема твърде много памет (O(|V|^2)). Ако графът има твърде много върхове а твърде малко ребра, матрицата ще има много нули (така наречената разредена матрица). Така ще ни се наложи да представяме малко информация с много памет.
-
-|Операция|Сложност||
-|--|--|--|
-|addVertex|O(n)||
-|removeVertex|O(n)||
-|addEdge|O(1)|
-|removeEdge|O(1)|
-|getSuccessors|O(n)||
-|getPredecessors|O(n)||
-
-![](media/matrix.png)
-
-* Тук може да си мислите за A = 0, B = 1 и тн.
-
-## Списък от списъци
-Друг начин е да държим някакъв списък (или масив) от |V| списъка. Вярно е, че списъкът на позиция i съдържа всички наследници на връх i.
-
-Примерно, графът от пример 1 ще се представи по следния начин:
-
-```
-0: 1 -> 2
-1: 0 -> 2
-2: 1 -> 2
-```
-
-Сега, ако искам да видя дали има ребро между връх i и връх j това е еквивалентно на lists[i].contains(j);
-
-Тегловни графи можем да представим, като вече списъците не са от числа а от двойки (Връх, Тегло).
-
-![](media/weighted-list.png)
-
-* Отново, тук индексацията започва от 1. Без никакъв проблем можем да я направим да започва от 0.
-
-Предимството на тази реализация е, че бързо можем да добавяме върхове и ребра. Също така паметта ни вече не е O(|V|^2) а O(|V| + |E|).
-
-Част от материалите са взаимствани от [тук](https://github.com/MariaGrozdeva/Data_structures_and_algorithms_FMI/tree/main/Sem_10)
-
-## BFS
-Breadth-first search е сравнително прост алгоритъм за търсене в граф, но върху идеята, която той носи се базират други алгоритми върху графи. Примерно, алгоритъмът на Прим за минимално покриващо дърво, алгоритъмът на Dijkstra за най - къси пътища се базират на идеи подобни на тази на BFS.
-
-Като вход получаваме граф G = (V, E) и връх s BFS систематично открива всички върхове, които са достижими от s. Чрез него можем да изчислим разстоянието (най - малкия брой ребра) от s до всеки друг връх. Алгоритъма работи за ориентирани и неориентирани графи.
-
-BFS използва структурата от данни опашка за да работи коректно. Самата идея е следната. Имаме начален връх, той ще бъде първия посетен. Добри кандидати да бъдат посетени след това са неговите съседи. Имаме функция adjacent (за ориентирани графи successors), та знаем кои са те. Добавяме ги в опашката, където чакат да бъдат посетени. След това последователно ги изваждаме от нея, и отново слагаме всички техни непосетени съседи в опашката, където чакат да бъдат посетени.
-
-Трябва ни обаче някакъв начин чрез който да разбираме дали даден връх е бил посетен. Ако нямаме тази информация зацикляме. С този проблем лесно се справяме правейки масив в който записваме дали даден връх е посетен или не.
-
-```
-BFS(G = (V, E), s начален връх)
- Създай опашка q и добави s вътре.
- Създай булев масив visited[0..|V| - 1] със стойности false.
-
- q.push(s).
-
- while(!q.empty())
- Нека cVertex е q.top().
- q.pop().
- Посети cVertex.
- Добави в q всеки съсед на cVertex, който не е посетен.
-```
-
-Ако графът не е тегловен BFS може да се използва за намирането на най - къс път между два върха. Припомнете си задача втора от трети семинар и решението ѝ. Задача първа също използва идея, подобна на бфс.
-
-## DFS
-BFS обхожда графа ниво по ниво. DFS използва различна стратегия, наподобяваща обхождането на лабиринт. Вървим по път докато не "стигнем до края на този път" (нямаме накъде да отидем повече). След това се връщаме назад, докато не стигнем връх, който има непосетен съсед. Рекурсивно повтаряме тази стратегия върху непосетения съсед и внимаваме да не повторим връх два пъти.
-
-![](media/dfs-example.gif)
-
-DFS използва структурата от данни stack за да работи коректно. Важно е да се отбележи, че замяната на опашката със стек в DFS алгоритъма **не влече** кректен DFS. За наше улеснение ще направим функцията рекурсивна и ще използваме системния стек.
-
-На примера виждаме едно DFS обхождане на граф.
-
-Може да видите, че след като обхождането приключи, ребрата, които използваме да посетим връх за пръв път образуват дърво. Това до някаква степен е очаквано, DFS не повтаря върхове и открива всички върхове достижими от началния, тоест графа, който ще е обходен ще е свързан.
-
-DFS посещава всеки връх и всяко ребро точно един път, което води до сложност O(|V| + |E|).
-
-DFS има много приложения, използва се за намиране на цикъл в граф, топологично сортиране на DAG (directet acyclic graph), търсене на пътища и др.
-
-Във файла DFS-Additional има интересни/допълнителни неща около DFS.
diff --git a/Seminar11/bfs-dfs.cpp b/Seminar11/bfs-dfs.cpp
deleted file mode 100644
index 75a6f3d..0000000
--- a/Seminar11/bfs-dfs.cpp
+++ /dev/null
@@ -1,65 +0,0 @@
-#include<iostream>
-#include"Graph-Impl/AdjacencyListGraph/AdjListGraph.h"
-#include"Graph-Impl/MatrixGraph/MatrixGraph.h"
-#include<queue>
-
-void BFS(const MatrixGraph& g, MatrixGraph::vertex_t start) {
- std::vector<bool> visited(g.vertexCount(), false);
-
- std::queue<MatrixGraph::vertex_t> q;
-
- q.push(start);
-
- while(!q.empty()) {
- MatrixGraph::vertex_t current = q.front();
- q.pop();
-
- if(visited[current])
- continue;
-
- visited[current] = true;
-
- std::cout << current << " ";
-
- auto successors = g.getSuccessors(current);
-
- for(const auto& currentVertex : successors) {
- if(!visited[currentVertex])
- q.push(currentVertex);
- }
- }
-}
-
-void DFSRec(std::vector<bool>& visited, const AdjListGraph& g, AdjListGraph::vertex_t start) {
- visited[start] = true;
-
- auto child = g.adjacent(start);
-
- std::cout << "Visited " << start << std::endl;
-
- for(const auto& currChild : child) {
- if(!visited[currChild.to]) {
- DFSRec(visited, g, currChild.to);
- }
- }
-}
-
-void DFS(const AdjListGraph& g, AdjListGraph::vertex_t start) {
- std::vector<bool> visited(g.vertexCount(), false);
- DFSRec(visited, g, start);
-}
-
-
-int main() {
- // MatrixGraph g(5);
- AdjListGraph g(5);
- g.addEdge(0, 2, 1);
- g.addEdge(0, 3, 1);
- g.addEdge(0, 1, 1);
- g.addEdge(2, 3, 1);
- g.addEdge(1, 4, 1);
- g.addEdge(3, 4, 1);
- g.addEdge(1, 3, 1);
-
- DFS(g, 0);
-} \ No newline at end of file
diff --git a/Seminar11/media/dfs-example.gif b/Seminar11/media/dfs-example.gif
deleted file mode 100644
index 463d476..0000000
--- a/Seminar11/media/dfs-example.gif
+++ /dev/null
Binary files differ
diff --git a/Seminar11/media/dir-graph.png b/Seminar11/media/dir-graph.png
deleted file mode 100644
index 5aaefed..0000000
--- a/Seminar11/media/dir-graph.png
+++ /dev/null
Binary files differ
diff --git a/Seminar11/media/graph.png b/Seminar11/media/graph.png
deleted file mode 100644
index 194cab6..0000000
--- a/Seminar11/media/graph.png
+++ /dev/null
Binary files differ
diff --git a/Seminar11/media/matrix.png b/Seminar11/media/matrix.png
deleted file mode 100644
index a2af53b..0000000
--- a/Seminar11/media/matrix.png
+++ /dev/null
Binary files differ
diff --git a/Seminar11/media/weighted-dirscted-graph (1).png b/Seminar11/media/weighted-dirscted-graph (1).png
deleted file mode 100644
index e251ebf..0000000
--- a/Seminar11/media/weighted-dirscted-graph (1).png
+++ /dev/null
Binary files differ
diff --git a/Seminar11/media/weighted-graph.png b/Seminar11/media/weighted-graph.png
deleted file mode 100644
index ed5d0b9..0000000
--- a/Seminar11/media/weighted-graph.png
+++ /dev/null
Binary files differ
diff --git a/Seminar11/media/weighted-list.png b/Seminar11/media/weighted-list.png
deleted file mode 100644
index 9d795e9..0000000
--- a/Seminar11/media/weighted-list.png
+++ /dev/null
Binary files differ
diff --git a/Seminar11/package.json b/Seminar11/package.json
deleted file mode 100644
index e69de29..0000000
--- a/Seminar11/package.json
+++ /dev/null
diff --git a/Seminar12/Dijkstra.cpp b/Seminar12/Dijkstra.cpp
deleted file mode 100644
index 3ce9de2..0000000
--- a/Seminar12/Dijkstra.cpp
+++ /dev/null
@@ -1,97 +0,0 @@
-#include"../Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h"
-#include<queue>
-#include<iostream>
-#include<list>
-
-using vertex_t = MatrixGraph::vertex_t;
-using weight_t = MatrixGraph::weight_t;
-
-bool relax(std::vector<weight_t>& distance, const MatrixGraph& g, vertex_t reached, vertex_t currentVertex) {
- if (distance[reached] > distance[currentVertex] + g.getWeight(currentVertex, reached)) {
- distance[reached] = distance[currentVertex] + g.getWeight(currentVertex, reached);
- return true;
- }
- return false;
-}
-
-// Намиране на най - къс път между два върха
-int Dijkstra(const MatrixGraph& g, vertex_t start, vertex_t end) {
- std::vector<vertex_t> parent(g.vertexCount(), -1);
- std::vector<weight_t> distances(g.vertexCount(), INT_MAX);
-
- struct VertexDistancePair {
- vertex_t vertex;
- weight_t distanceFromStart;
-
- bool operator<(const VertexDistancePair& other) const {
- return distanceFromStart > other.distanceFromStart;
- }
- };
-
- std::priority_queue<VertexDistancePair> q;
-
- distances[start] = 0;
- q.push({ start, 0 });
-
- while (!q.empty()) {
- auto currentPair = q.top();
- q.pop();
-
- if (currentPair.vertex == end) {
- auto currentVertex = currentPair.vertex;
-
- std::list<vertex_t> path;
-
- while (currentVertex != start) {
- path.insert(path.begin(), currentVertex);
- currentVertex = parent[currentVertex];
- }
-
- path.insert(path.begin(), start);
-
- for (const auto& v : path)
- std::cout << v << std::endl;
-
- return distances[currentPair.vertex];
- }
-
- const auto& adjacent = g.adjacent(currentPair.vertex);
-
- for (auto reached : adjacent) {
- if (relax(distances, g, reached, currentPair.vertex)) {
- parent[reached] = currentPair.vertex;
- q.push({ reached, distances[reached] });
- }
- }
- }
-
- return INT_MAX;
-}
-
-int main() {
- MatrixGraph g(8);
-
- g.addEdge(0, 1, 23);
- g.addEdge(0, 2, 74);
- g.addEdge(0, 3, 24);
-
- g.addEdge(1, 2, 35);
- g.addEdge(1, 4, 23);
-
- g.addEdge(2, 4, 24);
- g.addEdge(2, 3, 26);
-
- g.addEdge(3, 6, 32);
-
- g.addEdge(4, 5, 51);
- g.addEdge(4, 7, 17);
-
- g.addEdge(5, 7, 15);
-
- g.addEdge(6, 7, 32);
-
-
- int sp = Dijkstra(g, 0, 7);
-
- std::cout << std::endl << sp;
-} \ No newline at end of file
diff --git a/Seminar12/README.md b/Seminar12/README.md
deleted file mode 100644
index 8696283..0000000
--- a/Seminar12/README.md
+++ /dev/null
@@ -1,146 +0,0 @@
-# Най - къси пътища в граф.
-Обобщение: Разглеждаме накратко структурата от данни приоритетна опашка. Разглеждаме алгоритъма на Dijkstra и функцията relax.
-
-## Приоритетни опашки, но накратко
-В първата част на курса се запознахме със структурата от данни опашка. В приоритетната опашка отново можем да вкарваме и изваждаме елементи, но този път не излиза най - рано добавения елемент. Всеки елемент има приоритет и когато извадим елемент излиза най - приоритетния. Примерно, ако елементите ни са цели числа, можем да кажем, че колкото по - малък е един елемент толкова по - малък приоритет има той.
-
-Такава приоритетна опашка се нарича min priority queue.
-
-```cpp
-#include<queue>
-#include<iostream>
-
-int main() {
- // * int - от какъв тип са елементите
- // * std::vector<int> - за да държи елементите тази опашка използва друг контейнер като ги нарежда хитро в него.
- // този контейнер избираме да е std::vector<int>
- // * std::less<int> - как определяме приоритета на елементите.
- std::priority_queue<int, std::vector<int>, std::less<int>> q;
-
- q.push(3);
- q.push(2);
- q.push(4);
- q.push(1);
-
- while (!q.empty()) {
- // Излиза най - приоритетния елемент в началото 4 след това 3 и тн.
- std::cout << q.top() << " ";
- q.pop();
- }
-}
-```
-
-Приоритетните опашки и начинът за тяхната реализация може да отнеме един цял семинар. Може да мислите за приоритетната опашка като за абстрактен тип от данни, който поддържа някакъв интерфейс, и за който имаме различни хитри начини да бъде реализиран.
-
-Изваждането на елемент от приоритетната опашка е със сложност O(log(n)) където n e броя на елементите в опашката. Също така можем да построим приоритетна опашка в O(n) време.
-
-Приоритетните опашки често имат операцията decrease-key. Ако приоритетната опашка е от двойки ключ и стойност искаме да намалим ключа на дадена стойност. Тази операция е O(log(n)).
-
-## Алгоритъм на Dijkstra
-Алгоритъмът на Dijkstra намира най - къс път в ориентиран граф. **Алгоритъмът на Dijkstra не работи коректно, ако има отрицателни тегла, дори да няма отрицателни цикли!**
-
-Коректността на алгоритъма е сравнително трудна за доказване, затова ще разгледаме примерен код.
-
-```cpp
-bool relax(std::vector<weight_t>& distance, const MatrixGraph& g, vertex_t reached, vertex_t currentVertex) {
- if (distance[reached] > distance[currentVertex] + g.getWeight(currentVertex, reached)) {
- distance[reached] = distance[currentVertex] + g.getWeight(currentVertex, reached);
- return true;
- }
- return false;
-}
-
-// Намиране на най - къс път между два върха
-int Dijkstra(const MatrixGraph& g, vertex_t start, vertex_t end) {
- std::vector<vertex_t> parent(g.vertexCount(), -1);
- std::vector<weight_t> distances(g.vertexCount(), INT_MAX);
-
- struct VertexDistancePair {
- vertex_t vertex;
- weight_t distanceFromStart;
-
- bool operator<(const VertexDistancePair& other) const {
- return distanceFromStart > other.distanceFromStart;
- }
- };
-
- std::priority_queue<VertexDistancePair> q;
-
- distances[start] = 0;
- q.push({ start, 0 });
-
- while (!q.empty()) {
- auto currentPair = q.top();
- q.pop();
-
- if (currentPair.vertex == end) {
- auto currentVertex = currentPair.vertex;
-
- std::list<vertex_t> path;
-
- while (currentVertex != start) {
- path.insert(path.begin(), currentVertex);
- currentVertex = parent[currentVertex];
- }
-
- path.insert(path.begin(), start);
-
- for (const auto& v : path)
- std::cout << v << std::endl;
-
- return distances[currentPair.vertex];
- }
-
- const auto& adjacent = g.adjacent(currentPair.vertex);
-
- for (auto reached : adjacent) {
- if (relax(distances, g, reached, currentPair.vertex)) {
- parent[reached] = currentPair.vertex;
- q.push({ reached, distances[reached] });
- }
- }
- }
-
- return INT_MAX;
-}
-```
-Функцията връща най - късия път между start и end. За да имаме този път ни трябва масив, в който ще пазим предшествениците. Този масив наричаме parent.
-
-Ако имаме път 1 3 7, то
-* parent[1] = -1
-* parent[3] = 1
-* parent[7] = 3
-
-Също така в масивът distances ще записваме локално колко е цената на най - късия път от старта, открит до момента.
-Нека v e връх. Сега знаем, че distances[v] e дължината на най - късия път, който сме намерили до момента. Тоест, има някакъв път s -> v.
-
-Нека u e наследник на v. Знаем, че в distances[u] rма дължината на най - късия път, който сме открили до момента. Има два начина да стигнем до u. Първият начин е s -> u (пътят, чиято стойност е записана във distances[u]. Забележете, че ако такъв път не е открит, фактът, че стойността е INT_MAX отново води до коректно изпълнение). Вторият начин е s -> v -> u.
-
-Възможно ли е да сме намерили по - лек път от s -> u? Нека проверим. Тази проверка е отговорност на функцията relax:
-
-```
-relax(u, v):
- if d[u] > d[v] + weight(v, u) // Ако пътят s -> v -> u e по - лек от пътят d[u]
- d[u] = d[v] + weight(v, u) // Си открил нов най - лек път. Запиши го.
-```
-
-Създаваме приоритетна опашка в която ще държим наредени двойки от типа (връх, тегло на най - къс път).
-
-Всеки път от тази опашка ще вадим **върхът с най - лек път**. Затова съзваме структурата, представляваща двойка. В приоритетната опашка пътят от старта до върха ще представлява приоритета на върха. Оригиналният алгоритъм зарежда в приоритетната опашка веднага всички върхове и ъпдейтва ключовете им директно в опашката чрез функцията decrease-key. В началото всички ключове без началния са INT_MAX и след това постепенно се прилага decrease key всеки път когато открием по - кратък път. Тук приемаме друг подход, постепенно добавяме върхове в опашката, понеже std::priority_queue не поддържа decrease key. Това ще доведе до добавяне на върха няколко пъти в опашката но с различни ключове (всеки път когато намерим по - къс път). Това обаче не прави алгоритъма некоректен, просто върти малко повече.
-
-Сега, докато има елементи в опашката вземаме най - лекия връх v (този с минимален ключ т.е. с най - малък открит път от старта до него). За всеки негов съсед u, ако можем да го релаксираме го добавяме в опашката с разстоянието, което сме намерили.
-
-Когато върхът, който извадим от опашката е end в distances[end] e записан най - късия път от началото до end. Това твърдение също не е очевидно, но е вярно.
-
-Та, когато извадим end от опашката ни остава само да възстановим пътя и да върнем неговата стойност. Извеждаме го на стандартния изход, понеже това е примерен код. След това връщаме и самата дължина.
-
-Използваме std::list понеже добавянето в началото е бързо, но със същия успех бихме могли да добавяме в края на вектор примерно и да го обърнем след това.
-
-Ако искаме най - късите пътища от s до всички достижими върхове, просто ще изчакаме алгоритъма да приключи. След това ще върнем distances и parent за да можем да възстановим пътя за всеки връх.
-
-Сложността на представената версия на Dijkstra е O(|E|log(|E|)). Сложността на оригиналната Dijkstra реализирана с binary heap е
-O(|V|log|V| + |E|log|V|)
-* |V|*log(|V|) - в началото добавяме |V| елемента в приоритетната опашка. Всяко добавяне е log(|V|) време
-* |E|log|V| - Можем да имаме |E| операции decrease key (ако релаксираме за всяко ребро). Всеки decrease-key е log|V|.
-
-С изтънчени структури от данни Dijkstra може да стане и по - бърз **асимптотично**. \ No newline at end of file
diff --git a/Seminar13/README.md b/Seminar13/README.md
deleted file mode 100644
index 68c03ef..0000000
--- a/Seminar13/README.md
+++ /dev/null
@@ -1,20 +0,0 @@
-# Задачи върху графи
-
-## Задача първа
-Имаме n курса, които трябва да вземем, означени с числа от 0 до n - 1. Като вход получаваме вектор от двойки (i, j) и брой на курсовете. Всяка двойка във вектора означава, че курсът с етикет i трябва да се вземе преди курсът с етикет j. Да се провери дали е възможно курсовете да се вземат.
-
-``` Пример
-Вход: [[0, 1]], 2
-
-Изход: Да, първо вземаме курс 0 а после курс 1.
-
-Вход: [[0, 1], [1, 0]], 2
-
-Изход: Не.
-```
-
-## Задача втора
-Даден е ориентиран граф от уникални символи g. Да се напише функция, която приема графа и дума с произволна дължина и проверява дали думата може да се получи чрез конкатенирането на последователни различни върхове в графа.
-
-## Задача трета
-Да се напише функция, която намира сумата на най - големите елементи на отделните свързани компоненти в (неориентиран) граф. \ No newline at end of file
diff --git a/Seminar13/task01.cpp b/Seminar13/task01.cpp
deleted file mode 100644
index ff33136..0000000
--- a/Seminar13/task01.cpp
+++ /dev/null
@@ -1,85 +0,0 @@
-#include<vector>
-#include<queue>
-#include<iostream>
-
-bool hasCycleRec(const std::vector<std::vector<int>>& graph, int start, std::vector<bool>& visited) {
- visited[start] = true;
-
- for (const auto& vertex : graph[start]) {
- if (visited[vertex])
- return true;
-
- if (hasCycleRec(graph, vertex, visited))
- return true;
- }
-
- visited[start] = false;
-
- return false;
-}
-
-bool hasCycle(const std::vector<std::vector<int>>& graph) {
- std::vector<bool> visited(graph.size(), false);
-
- for (int i = 0; i < graph.size(); i++) {
- if (!visited[i] && hasCycleRec(graph, i, visited)) {
- return true;
- }
- }
-
- return false;
-}
-
-// Използваме алгоритъм на Kahn за топологично сортиране
-bool canFinish(int numCourses, std::vector<std::pair<int, int>>& prerequisites) {
- std::vector<std::vector<int>> graph(numCourses);
-
- for (const auto& edgePair : prerequisites)
- graph[edgePair.first].push_back(edgePair.second);
-
- // Степен на вход на върховете
- std::vector<int> inDegree(numCourses, 0);
-
- for(int i = 0; i < numCourses; i++) {
- for(const auto& vertex : graph[i]) {
- inDegree[vertex]++;
- }
- }
-
- std::queue<int> q;
-
- // Добавяме тези със степен нула. Те ще са първи в топологичната сортировка.
- for(int i = 0; i < numCourses; i++) {
- if(inDegree[i] == 0) {
- q.push(i);
- }
- }
-
- // Правим подобно на BFS търсене.
- // След като "изтрием" върховете със степен на вход 0 има други върхове
- // със степен на вход 0. Те са следващите в топологичната сортировка.
- while(!q.empty()) {
- int currentNode = q.front();
- q.pop();
-
- for(const auto& n : graph[currentNode]) {
- inDegree[n]--;
-
- if(inDegree[n] == 0)
- q.push(n);
- }
- }
-
- // Ако след това обхождане има връх със степен
- // различна от 0, то в графа има цикъл.
- for(const auto& n : inDegree) {
- if(n != 0)
- return false;
- }
-
- return true;
-}
-
-int main() {
-
-} \ No newline at end of file
diff --git a/Seminar13/task02.cpp b/Seminar13/task02.cpp
deleted file mode 100644
index 8d47b45..0000000
--- a/Seminar13/task02.cpp
+++ /dev/null
@@ -1,41 +0,0 @@
-#include<iostream>
-#include<string>
-#include<map>
-#include<vector>
-
-bool canRead(const std::multimap<char, char>& graph, const std::string& word, size_t at) {
- if(at == word.length() - 1)
- return true;
-
- auto successors = graph.find(word[at]); // Може ли да си спестим това търсене?
-
- if(successors == graph.end())
- return false;
-
- while(successors != graph.end() && (*successors).first == word[at]) {
- if((*successors).second == word[at + 1]) {
- return canRead(graph, word, at + 1);
- }
-
- ++successors;
- }
-
- return false;
-}
-
-int main() {
- std::multimap<char, char> graph;
-
- graph.insert({'a', 'c'});
- graph.insert({'a', 'd'});
- graph.insert({'c', 'b'});
- graph.insert({'b', 'd'});
- graph.insert({'d', 'k'});
- graph.insert({'d', 'c'});
- graph.insert({'d', 'a'});
-
- std::map<char, bool> visited;
- std::string word = "adaz";
-
- std::cout << canRead(graph, word, 0);
-} \ No newline at end of file
diff --git a/Seminar14/README.md b/Seminar14/README.md
deleted file mode 100644
index f74e6ae..0000000
--- a/Seminar14/README.md
+++ /dev/null
@@ -1,211 +0,0 @@
-# Абстрактен тип данни речник. Хеш таблици.
-
-*A common problem in computer science is the representation of a mapping between two sets.*
-
-## Dictionary problem
-Нека си представим абстрактен тип данни, който поддържа някакво множество от елементи, всеки от който има ключ. Искаме да поддържаме следните операции:
-* insert(item) - добави елемента в колекцията
-* delete(item) - премахни елемента от колекцията
-* search(key) - дай ми елемента, чийто ключ е key ако съществува такъв.
-
-Предполагаме, че всички елементи имат различни ключове.
-Този абстрактен тип данни наричаме dictionary.
-
-Балансирано дърво за търсене би решило проблема със сложност O(log(n)) за всяка от трите операции.
-
-Целта за днес: O(1) за тези три операции.
-
-```
-The dictionary problem is the classic problem of designing efficient data structures that implement associative arrays. The two major solutions to the dictionary problem are hash tables and search trees.
-```
-
-## Мотивация зад структурата
-Речниците са **най - популярната** нетривиална структура от данни в компютърните науки. Причината е, че много проблеми от реалния свят могат ефикасно да се решат с речници.
-
-## Интуиция
-Цял семестър сме си водили старателно записки по всички предмети и сега изпитите наближават. Това предполага много четене, разбира се от записките, които старателно сме водили цял семестър. Ясно е, че често ще ни се налага да търсим записки от определена лекция.
-
-Слагаме всички записки на куп, без никаква наредба. Сега, за да намерим записките от третата лекция по структури от данни ще ни се наложи да претърсим целия куп от лекции. Никой обаче не учи по един предмет цял ден, вероятно след 3 часа учене по структури от данни ни се иска да прочетем нещо по функционално програмиране и сега пак претърсваме целия куп.
-
-Отиваме до Икеа и си купуваме 6 кутии. Правим логичното нещо - слагаме записките по структури от данни в първата, тези по функционално във втората и тнт.
-
-Сега, ако ни се наложи да търсим записки по определен предмет вече няма да се налага да изровим целия куп с листи а само кутията в която се намират те.
-
-## Хеш функции
-Интуитивно хеш таблиците ще са просто множество от кутии (или както се наричат в практиката buckets(кофи)). За реализацията на хеш таблици използваме хеш функции, които при додаден ключ генерират индекс (хеш код), на който трябва да се запише съответната стойност.
-
-Това звучи страхотно, но по принципа на Дирихле ако имаме повече елементи за слагане в кофите отколкото кофи ще се наложи да сложим поне два елемента в една кофа. Това на практика става и преди да елементите да станат повече от кофите. Нека *X* и *Y* са два различни ключа. Абсолютно възможно е
-
-```
-h(X) = h(Y)
-```
-и това наричаме *колизия*. От тук можем да си направим два извода. Първо, хеш функцията **не е обратима** и второ ще трябва да измислим някакъв начин да се справим с тези колизии.
-
-Какво наричаме добра хеш функция?
-* Функцията трябва да използва всички данни от ключа.
-* Функцията равномерно да разпределя елементите.
-* Функцията трябва да е бърза за изчисляване.
-* Желателно е за подобни ключове функцията да връща различни резултати.
-
-Примерно
-```cpp
-int hashDummy(int key) {
- return 0;
-}
-```
-е валидна хеш функция. Е, не е особено добра. Не е изобщо добра.
-
-Какво наричаме перфектна хеш функция? Няма такава. Добрата хеш функция се държи добре върху определен вход, но няма универсална хеш функция. Намирането на добра хеш функция може да изисква голямо задълбочено разбиране в някои математически дисциплини.
-
-## Справяне с колизии - Separate chaining
-Нека си мислим за кофите като за свързани списъци.
-За всеки елемент, индексът на свързания списък, в който трябва да го добавим се определя от хеш функцията.
-
-```cpp
-int index(const Key& k) {
- return hash(key) % table.size(); // Ако не правим модулно делене рискуваме да излезем от рамките на таблицата.
-}
-```
-
-Сега наивно, добавянето може да изглежда по следния начин:
-```cpp
-void insert(const Key& k, const Value& v) {
- size_t idx = index(k);
-
- table[idx].push_back({k, v});
-}
-```
-Проблем: какво правим когато ключът вече съществува? Ако оставим кода така ще имаме списък с два ключа, имащи различни стойности.
-Полезно е да имаме функционалност, която ъпдейтва стойността на ключа. Правим следното:
-
-```cpp
-void insert(const Key& k, const Value& v) {
- size_t idx = index(k);
-
- for(auto& elementInBucket : table[idx]) {
- if(elementInBucket.key == k) {
- elementInBucket.value = v; // update key
- return;
- }
- }
-
- table[idx].push_back({k, v});
-}
-```
-
-Страхотно, сега търсенето ни се свежда до търсене в списък:
-```cpp
-Value getValue(const Key& k) {
- size_t idx = index(k);
-
- for(const auto& elementInBucket : table[idx]) {
- if(elementInBucket.key == k) {
- return elementInBucket.value;
- }
- }
- // Съобщение за грешка. Може да не е ексепшън, вие решавате.
- throw std::exception("Key not found!");
-}
-```
-
-Също така, премахването на елемент отново ни се свежда до премахване на елемент от списък.
-```cpp
-void eraseKey(const Key& k) {
- size_t idx = index(k);
-
- for(const auto& elementInBucket : table[idx]) {
- if(elementInBucket.key == k) {
- return elementInBucket.value;
- }
- }
- // Съобщение за грешка. Може да не е ексепшън, вие решавате.
- throw std::exception("Key not found!");
-}
-```
-
-Какво правим обаче когато елементите в колекцията станат много? Ясно е, че ако имаме 10 кофи и 1000 елемента нещата няма да са толкова ефикасни. Можем да преоразмеряваме таблицата. Колкото повече елементи имаме в колекцията толкова по - голяма таблица ще правим.
-
-Преоразмеряването ще стане сравнително лесно - вече знаем как да добавяме елемент и как реализираме контейнера. Просто създаваме два пъти по - голям контейнер и добавяме всички елементи в него по познатия начин.
-
-Въпросът сега е кога ще преоразмеряваме? Нека n = броя на елементите, m = броя на кофите.
-```
-LoadFactor = n / m.
-```
-Ясно е, че когато m = n следващото добавяне ще гарантира, че ще има поне една кофа с два елемента. Реално кофата с повече от един елемент се появява доста по - рано.
-
-Преоразмеряването на таблицата се прави при LoadFactor = 0,7 (Когато елементите станат 70 процента от кофите). Така, жертвайки малко повече памет, постигаме бързо търсене.
-
-## Какво друго жертваме?
-При хешовете нямаме наредба на елементите. Разбира се, можем да ги обходим, но това обхождане не гарантира нищо. Дърветата от друга страна са познати с това, че поддържат колекцията сортирана. Това понякога е полезно, но в някои случаи не ни интересува да имаме сортирана колекция.
-
-Сложността в най - лошия случай тук е O(n). Това става когато имаме лоша хешираща функция. Ако хеширащата ни функция се държи добре (разпределя равномерно информацията между кофите) очакваната сложност е O(1).
-
-```
-Although searching for an element in a hash table can take as long as searching for an element in a
-linked list — Theta(n) time in the worst case — in practice, hashing performs extremely
-well. Under reasonable assumptions, the average time to search for an element in
-a hash table is O(1).
-```
-
-## Използване на други структури за да подобрим O(n) worst case
-Лошата горна граница за търсенето ни идва от факта, че използваме свързани списъци. Вече имаме дървета, които ни позволяват O(log(n)) търсене, защо вместо свързани списъци не използваме тях примерно?
-
-Това е интересна тема за разсъждение - от една страна лошото търсене не се дължи толкова на свързания списък колкото на факта, че елементите не са разпределени добре. Дървото ще забърза нещата, но така не поддържаме ли просто едно бавно дърво (или няколко такива)?
-
-От друга страна съм чувал, че такива техники се използват. [Тук](https://openjdk.org/jeps/180) прочитаме:
-
-```
-The principal idea is that once the number of items in a hash bucket grows beyond a certain threshold, that bucket will switch from using a linked list of entries to a balanced tree. In the case of high hash collisions, this will improve worst-case performance from O(n) to O(log n).
-```
-та тази идея явно не е толкова неизползваема.
-
-## Недостатъци на Separate chaining
-Оказва се, че сложността в лошия случай не е най - големия проблем. За да разберем проблема трябва да разберем какво е cache locality.
-Темата е много интересна, но не се събира в ограниченото време което имаме.
-[Тук](https://www.youtube.com/watch?v=kcdaiPb7vaY) може да се запознаете подробно с темата.
-
-Сбито казано: когато четем памет, компютъра предполага, че съседните клетки може би скоро също ще трябва да бъдат прочетени. Затова ги записва в по - малка памет, която обаче е по - бърза.
-
-Това е и причината итерацията на масив да е в пъти по - бърза от итерацията на свързан списък. Елементите на свързания списък са разпръснати в паметта (намирахме ги с указатели) и често ни се налага да четем нова и нова памет.
-
-Когато прочетем клетка, която е записана в кеш паметта е cache hit. Когато ни се наложи да се разходим по - дълго за да намерим клетката която ни трябва това се нарича cache miss.
-
-Дори когато имаме два елемента в кофата ще направим два cache miss-a.
-
-## Open adressing
-В предишната стратегия елементите се държаха извън хеш таблицата. В отвореното адресиране **всички** елементи се държат в хеш таблицата. Този подход също се нарича затворено хеширане.
-
-Сега въпросът е как реализираме абстрактните операции? Има няколко начина.
-
-## Linear probing
-Нека започнем да разсъждаваме и да видим какви проблеми ще срещнем.
-
-### Добавяне
-Разглеждаме елементите и техните хеш кодове: {A, 2}, {B, 3}, {C, 7}, {D, 2}.
-
-Добавянето на първите три в някакъв смисъл е лесно. Имаме следния сценарий:
-
-![](media/insert-first.png)
-
-Какво правим обаче когато имаме колизия (както е в случая с D). Ами започваме линейно да търсим първата свободна клетка. Там добавяме D.
-
-![](media/insert-second.png)
-
-## Търсене
-Сега, да предположим, че търсим D. Генерираме неговия хеш код, но на негово място стои А. Логично е, познавайки стратегията си, да не се отказваме и да продължим да търсим. Търсим до момента в който не срещнем първата празна клетка.
-
-## Изтриване
-Тук нещата стават малко по - сложни. Да кажем, че изтрием С. След това търсим D. Но сега между A и D има празна клетка. Трябва да направим някаква модификация за да се справим с този проблем.
-
-Решение: добавяме два флага на клетката: empty и deleted. Ако клетката е била изтрита **не спираме да търсим**. Спираме при първата **празна клетка**. Няма проблем да добавяме елементи в изтрита клетка.
-
-Тук преоразмеряването е задължително. Отново, когато елементите станат около 70 процента преоразмеряваме.
-
-## std::unordered_map. std::unordered_set.
-
-## Тестове
-
-## Задача първа
-Даден ни е някакъв стринг. Искаме да го разделим на подстрингове от последователни елементи така, че всеки елемент в тези подстрингове да е уникален. Да се върне колко най - малко такива подстрингове трябва да имаме.
-
-Пример: abacaba => "a","ba","cab","a" (връщаме 4) \ No newline at end of file
diff --git a/Seminar14/SeparateChaining.hpp b/Seminar14/SeparateChaining.hpp
deleted file mode 100644
index 0472a2b..0000000
--- a/Seminar14/SeparateChaining.hpp
+++ /dev/null
@@ -1,110 +0,0 @@
-#ifndef SEPARATE_CHAINING_HASH
-#define SEPARATE_CHAINING_HASH
-
-#include<functional> // std::hash
-#include<list>
-#include<vector>
-
-template<class Key, class Value, class Hash = std::hash<Key>>
-class SCHash {
-private:
- using pair_type = std::pair<Key, Value>;
- using bucket = std::list<pair_type>;
- using container = std::vector<bucket>;
- using bucketIterator = typename container::iterator;
- using bucketConstIterator = typename container::const_iterator;
-
- container table;
- size_t elementsCount;
- Hash hash;
-
- size_t getIndex(const Key& key) const {
- return hash(key) % table.size();
- }
-
- bool shouldResize() const {
- return ((float)(elementsCount) / table.size()) > 0.7f;
- }
-
- bucketIterator getBucket(const Key& k) {
- return (table.begin() + getIndex(k));
- }
-
- bucketConstIterator getBucket(const Key& k) const {
- return (table.begin() + getIndex(k));
- }
-
- void resize() {
- container newTable(2 * table.size());
- table.swap(newTable);
-
- for (bucket& currentBucket : newTable) {
- for (pair_type& element : currentBucket) {
- getBucket(element.first)->push_back({ element.first, element.second });
- }
-
- // Освобождаваме паметта от кофата, вече няма да ни трябва.
- currentBucket.clear();
- }
- }
-
-public:
-
- SCHash(Hash h = Hash()) : elementsCount{ 0 }, table(32), hash(h) {}
-
- void clear() {
- elementsCount = 0;
- table = container(32);
- }
-
- void insert(const Key& k, const Value& v) {
- if (shouldResize()) {
- resize();
- }
-
- bucketIterator currentBucket = getBucket(k);
-
- ++elementsCount;
-
- for (auto& currentPair : *currentBucket) {
- if (currentPair.first == k) {
- currentPair.second = v;
- return;
- }
- }
- currentBucket->insert(currentBucket->end(), { k, v });
- }
-
- Value find(const Key& k) const {
- const auto& currentBucket = getBucket(k);
-
- for (const auto& currentPair : *currentBucket) {
- if (currentPair.first == k) {
- return currentPair.second;
- }
- }
-
- throw "Key not found!";
- }
-
- void erase(const Key& k) {
- auto currentBucket = getBucket(k);
-
- for (auto it = currentBucket->begin(); it != currentBucket->end(); ++it) {
- if (it->first == k) {
- currentBucket->erase(it);
- return;
- }
- }
- }
-
- size_t size() const {
- return elementsCount;
- }
-
- bool empty() const {
- return elementsCount == 0;
- }
-};
-
-#endif \ No newline at end of file
diff --git a/Seminar14/media/insert-first.png b/Seminar14/media/insert-first.png
deleted file mode 100644
index f0b3afc..0000000
--- a/Seminar14/media/insert-first.png
+++ /dev/null
Binary files differ
diff --git a/Seminar14/media/insert-second.png b/Seminar14/media/insert-second.png
deleted file mode 100644
index e7c97d5..0000000
--- a/Seminar14/media/insert-second.png
+++ /dev/null
Binary files differ
diff --git a/Seminar14/src.cpp b/Seminar14/src.cpp
deleted file mode 100644
index ff176fd..0000000
--- a/Seminar14/src.cpp
+++ /dev/null
@@ -1,18 +0,0 @@
-#include<iostream>
-#include<unordered_map>
-
-int main() {
- std::string example = "abcbabc";
- std::unordered_map<char, int> mp;
- int cnt = 1;
-
- for(char c : example) {
- if(mp[c] > 0) {
- ++cnt;
- mp.clear();
- }
- mp[c]++;
- }
-
- std::cout << cnt;
-} \ No newline at end of file