Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar03
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 /Seminar03
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar.gz
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.zip
Parent0841635826cb03c0e74cd75ec3c97c4c3b594d8b (diff)
Cleanup
8 files changed, 0 insertions, 536 deletions
-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
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