Website Summary Files Commits Branches @commit @diff @stats
path: root / Practicum
diff options
context:
space:
mode:
Commit3395a1fc3f30b1c2744b9e43edab7b864ba9a8dd (patch)
Author
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-11-03 08:29:31 -0500
Committer
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-11-03 08:29:31 -0500
Files781ee1a895bea55336c77d05d31bd3c17879a2f7 /Practicum
Data-structures-and-algorithms-3395a1fc3f30b1c2744b9e43edab7b864ba9a8dd.tar
Data-structures-and-algorithms-3395a1fc3f30b1c2744b9e43edab7b864ba9a8dd.tar.gz
Data-structures-and-algorithms-3395a1fc3f30b1c2744b9e43edab7b864ba9a8dd.zip
Parent3ed5560f80d1175971cb658cade40190bd014a5e (diff)
Parent097b0826ae970e3115c7ba59648074b31a821896 (diff)
Merge branch 'main' of https://github.com/stoychoX/Data-structures-and-algorithms
2 files changed, 315 insertions, 0 deletions
-rw-r--r--Practicum/pract03/solutions.cpp106
-rw-r--r--Practicum/pract04/readme.md209
diff --git a/Practicum/pract03/solutions.cpp b/Practicum/pract03/solutions.cpp
new file mode 100644
index 0000000..2370a93
--- /dev/null
+++ b/Practicum/pract03/solutions.cpp
@@ -0,0 +1,106 @@
+#include <iostream>
+#include <algorithm>
+#include <vector>
+using namespace std;
+
+//Task 1
+void orderByFirstLetter(vector<string>& words)
+{
+ auto first = words.begin();
+ auto last = words.end();
+
+ for (char letter = 'a'; letter <= 'z'; letter++)
+ {
+ auto new_beg = partition(first, last, [letter](const string& str) { return str[0] == letter; });
+ first = new_beg;
+ }
+}
+
+//Task 2
+bool isEven(int n)
+{
+ return n % 2 == 0;
+}
+
+bool isOdd(int n)
+{
+ return n % 2;
+}
+
+template <class Pred>
+void mergeSortedPred(vector<int>& res, const vector<int>& first, const vector<int>& second, Pred p)
+{
+ auto beg1 = first.begin();
+ auto beg2 = second.begin();
+
+ auto end1 = first.end();
+ auto end2 = second.end();
+
+ while (beg1 != end1 && beg2 != end2)
+ {
+ if (p(*beg1) && p(*beg2))
+ {
+ if (*beg1 <= *beg2)
+ {
+ res.push_back(*beg1);
+ ++beg1;
+ }
+ else
+ {
+ res.push_back(*beg2);
+ ++beg2;
+ }
+ }
+ else
+ {
+ if (!p(*beg1))
+ ++beg1;
+
+ if (!p(*beg2))
+ ++beg2;
+ }
+ }
+
+ while (beg1 != end1)
+ {
+ if (p(*beg1))
+ res.push_back(*beg1);
+
+ ++beg1;
+ }
+
+ while (beg2 != end2)
+ {
+ if (p(*beg2))
+ res.push_back(*beg2);
+
+ ++beg2;
+ }
+}
+vector<int> mergeSortedEvensAndOdds(const vector<int>& first, const vector<int>& second)
+{
+ vector<int> res;
+ mergeSortedPred(res, first, second, isEven);
+ mergeSortedPred(res, first, second, isOdd);
+
+ return res;
+}
+
+int main()
+{
+ //task 1
+ vector<string> v = { "banana", "apple", "alpaca", "cat", "biscuit", "elephant", "string", "house", "progress", "trousers", "mouse" };
+ orderByFirstLetter(v);
+
+ for (auto it = v.begin(); it != v.end(); ++it)
+ cout << *it << " ";
+
+ //task 2
+ vector<int> v1 = { 1, 2, 3, 4, 5 };
+ vector<int> v2 = { 5, 17, 32, 80, 81, 82, 83 };
+
+ vector<int> res = mergeSortedEvensAndOdds(v1, v2);
+
+ for (auto it = res.begin(); it != res.end(); ++it)
+ std::cout << *it << " ";
+}
diff --git a/Practicum/pract04/readme.md b/Practicum/pract04/readme.md
new file mode 100644
index 0000000..351b8a8
--- /dev/null
+++ b/Practicum/pract04/readme.md
@@ -0,0 +1,209 @@
+# Практикум №4 по Структури от данни, спец. ИС
+
+Какво представляват алгоритмите за търсене? Може би е интуитивно, но те представляват методи или процедури,
+използвани за намиране на конкретен елемент в дадена колекция от данни. Ще се запознаем с няколко по-известни от тях.
+
+## Линейно търсене
+Когато търсим елемент в дадена колекция, нещото, което ни хрумва първо, е да я обходим цялата и да проверим дали той е в нея.
+Съответно, ако го намерим, искаме да върнем позицията му. Цялата тази идея е имплементирана именно в алгоритъма `Linear Search` или линейно търсене на български.
+Нека разгледаме примерна имплементация:
+
+```c++
+template <class T>
+int linear_search(const std::vector<T>& data, const T& el)
+{
+ for (int i = 0; i < data.size(); i++)
+ {
+ if (data[i] == el)
+ return i;
+ }
+
+ return -1;
+}
+```
+
+Както можем да видим, алгоритъма обхожда цялата колекция и в най-лошия случай ще направи **n** стъпки, т.е. сложността му в `worst-case` е **O(n)**.
+В `average-case` ще направи *n/2* стъпки, тъй като предполагаме, че тогава търсеният елемент ще се намира в средата на колекцията, т.е. сложността отново е **O(n)**.
+Съответно `best-case` ще ни е, когато елементът се намира в началото на колекцията, т.е. сложността е константна - **O(1)**.
+
+Хубавото на този алгоритъм е, че не изисква допълнително сортиране на елементите, което явно ще увеличи сложността му.
+
+Но дали има начин да оптимизираме този алгоритъм?
+
+Ако се замислим, сложността му няма как да бъде оптимизирана - винаги имаме обхождане на елементите на масива.
+
+Но какво друго можем да направим? Ако погледнем, ще видим, че на всяка стъпка извършваме 2 проверки - за елемента и за индекса i дали не е излезнал извън границите на нашата колекция.
+Всъщност можем да направим така, че да спестим втората проверка. Как? Ами като сложим търсения елемент в края на нашата колекция на мястото на последния елемент.
+Тази техника се нарича добавяне на `sentinel` в края на колекцията и е често срещана в практическата сфера.
+Нека видим как бихме могли да го имплементираме:
+
+```c++
+template <class T>
+int linear_search_sentinel(const std::vector<T>& data, const T& el)
+{
+ T last = data.back();
+ data.back() = el;
+
+ int i = 0;
+ while (el != data[i])
+ {
+ i++;
+ }
+
+ data.back() = last;
+
+ if(i < data.size() - 1 || data.back() == el)
+ return i;
+
+ return -1;
+}
+```
+
+Както виждаме, сложността си остава същата и в трите случая, но проверките ни драстично намаляват, което за по-обемни колекции ще е от голямо значение.
+
+## Binary Search
+Разгледахме вече случая, в който обхождаме цялата колекция. Както сами се убедихме, той не е много оптимален (особено за големи колекции), тъй като ще се наложи да ги обхожда целите.
+Нека се замислим - ако елементите ни са в сортиран вид, няма ли по-оптимален начин да намерим търсения от нас такъв? Отговорът е - да, има, и се нарича `Binary Search` или двоично търсене на български.
+
+Идеята му е да вземем средния елемент на колекцията. Той я разделя на две половини - лява и дясна.
+Първо ще сравним търсения със средния елемент - ако са равни, значи сме го открили и можем да върнем неговата позиция. Ако не са равни, ще направим следното:
+тъй като колекцията ни е сортирана, ако търсеният елемент е по-голям от средния, значи се намира в дясната половина, а ако е по-малък - съответно в лявата. По този начин ще приложим същото
+търсене върху половината, в която вече сме сигурни, че се намира нашия елемент и така, докато не стигнем до него.
+
+Нека разгледаме как бихме могли да имплементираме алгоритъма:
+
+```c++
+template <class T>
+int binary_search(const std::vector<T>& data, T el)
+{
+ int beg = 0, end = data.size() - 1;
+
+ while (beg <= end)
+ {
+ int mid = beg + (end - beg) / 2;
+
+ if (data[mid] == el)
+ return mid;
+
+ if (el < data[mid])
+ end = mid - 1;
+ else
+ beg = mid + 1;
+ }
+
+ return -1;
+}
+```
+
+Както забелязваме, на всяка итерация от цикъла размерът на интервала, в който търсим, намалява наполовина и така, докато не стане с размер 1 (когато beg и end се срещнат).
+Съответно ако размера на колекцията ни е n и сме направили x стъпки, то за да намерим x, трябва да решим следното уравнение:
+
+$$
+\frac{n}{2^x} = 1
+$$
+
+От уравнението имаме:
+
+$$
+\frac{n}{2^x} = 1 \implies n = 2^x \implies x = \log_2 n \implies \Theta(\log n)
+$$
+
+Получихме, че алгоритъмът има сложност O(logn) в `worst-case`.
+
+`Best-case` ще имаме, когато елементът, който търсим, е точно в средата. Съответно сложността ни тогава е константна (O(1)) - няма да разглеждаме други интервали.
+
+## Стандартни алгоритми за търсене - `std::find`, `std::find_if` и `std::find_if_not`
+В стандартната библиотека имаме алгоритъм, който ни намира даден елемент в колекция. Този алгоритъм се нарича `std::find`. Имплементиран е на базата на линейното търсене, което прави и слоцността му линейна.
+Използва итератори съответно към началото и края на range-a, в който ще търсим елемента, и връща итератор към намерения елемент. Ако не го намери, връща итератор към края на колекцията.
+Ето една възможна имплементация, използваща итератори:
+
+```c++
+template<class RandomIt, class T = typename std::iterator_traits<RandomIt>::value_type>
+constexpr RandomIt find(RandomIt first, RandomIt last, const T& value)
+{
+ for (; first != last; ++first)
+ {
+ if (*first == value)
+ return first;
+ }
+
+ return last;
+}
+```
+
+Съответно има негови модификации, които ни позволяват да търсим елемент, който отговаря (или не отговаря) на даден критерий. Това са методите `std::find_if` и `std::find_if_not`.
+И двата метода приемат предикат, като връщат първия елемент, който отговаря (респективно не отговаря) на него. Ако няма такъв, отново връщат итератор към края.
+
+Нека видим възможни имплементации:
+
+```c++
+template<class RandomIt, class UnaryPred>
+const RandomIt find_if(RandomIt first, RandomIt last, UnaryPred p)
+{
+ for (; first != last; ++first)
+ if (p(*first))
+ return first;
+
+ return last;
+}
+```
+
+```c++
+template<class RandomIt, class UnaryPred>
+const RandomIt find_if_not(RandomIt first, RandomIt last, UnaryPred p)
+{
+ for (; first != last; ++first)
+ if (!p(*first))
+ return first;
+
+ return last;
+}
+```
+
+
+## `std::upper_bound` и `std::lower_bound`
+`std::upper_bound` и `std::lower_bound` отново са методи от стандартната библиотека, базирани на алгоритми за търсене. Особеното тук е, че са базирани на двоичното търсене, т.е. задължават колекцията ни да е сортирана предварително, за да ги използваме.
+Сложността им е съответно O(logn).
+
+`std::upper_bound` приема итератори към началото и края на range-a, в който ще търси, както и елемент. Връща итератор към първия елемент от колекцията, който е по-голям от подадения.
+Ако няма такъв, връща итератор към края.
+
+`std::lower_bound` е подобна - приема итератори към началото и края на range-a, в който ще търси, както и елемент. Връща итератор към първия елемент от колекцията, който е по-голям **или равен** на подадения.
+Ако няма такъв, връща итератор към края.
+
+Да разгледаме и примерни имплементации:
+
+```c++
+template <class RandomIt, class T = typename std::iterator_traits<RandomIt>::value_type>
+RandomIt lower_bound(RandomIt beg, RandomIt end, const T& value) {
+ while (beg < end) {
+ RandomIt mid = beg + (end - beg) / 2;
+
+ if (*mid < value)
+ beg = std::next(mid);
+ else
+ end = mid;
+ }
+ return beg;
+}
+```
+
+```c++
+template <class RandomIt, class T = typename std::iterator_traits<RandomIt>::value_type>
+RandomIt upper_bound(RandomIt beg, RandomIt end, const T& value) {
+ while (beg < end) {
+ RandomIt mid = beg + (end - beg) / 2;
+
+ if (*mid <= value)
+ beg = std::next(mid);
+ else
+ end = mid;
+ }
+ return beg;
+}
+```
+
+---
+
+## Задачи
+[**Линк към задачите**](https://leetcode.com/problem-list/auzfnnwr/)