Algorytmy i Struktury Danych II - UMCS

Zbiór rozwiązań kilku zadań z fakultetu "Algorytmy i Struktury Danych II" na Uniwersytecie Marii Curie-Skłodowskiej w Lublinie.

📚 Spis treści

• O repozytorium
• Struktura projektu
• Zadania
• Kompilacja i uruchamianie
• Algorytmy i techniki
• Uwagi

O repozytorium

To repozytorium zawiera moje rozwiązania (na kolanie) zadań programistycznych z kursu ASD II. Każde zadanie zostało rozwiązane w języku C++ z naciskiem na optymalizację czasową i pamięciową.

Struktura projektu

├── 2/          # Zadanie "Partia o fotel" - Minimalne drzewo rozpinające (MST)
├── 4/          # Zadanie "Izba z kart" - Drzewa BST i wyszukiwanie par
├── 7/          # Zadanie "Mendolód" - Algorytm Rabina-Karpa
├── 8/          # Zadanie "Jenne" - Dopasowywanie wzorców
├── 9/          # Zadanie "Forteca Mairona" - Otoczka wypukła
├── 10/         # Zadanie "Łamanie zła" - Całkowanie numeryczne
├── 11/         # Zadanie "Loptr" - Prawdopodobieństwo i funkcje
└── README.md

Każdy folder zawiera:

• README.md - treść zadania
• *.cc - rozwiązanie w C++
• input.txt - przykładowe dane testowe

Zadania

2. Partia o fotel 🏰

Problem: Znajdowanie minimalnego drzewa rozpinającego z wagami probabilistycznymi
Algorytm: Algorytm Prima z kolejką priorytetową
Złożoność: O(E log V)
Technika: Konwersja prawdopodobieństw do logarytmów

4. Izba z kart 🏛️

Problem: Wyszukiwanie pary liczb o zadanej sumie w przedziale
Algorytm: Drzewo BST z operacjami przycinania
Złożoność: O(n log n)
Struktury: Binary Search Tree, filtrowanie przedziałami

7. Mendolód 🚀

Problem: Wyszukiwanie wzorca w sekwencji z przewidywaniem kolejnego wystąpienia
Algorytm: Rabin-Karp z hashowaniem
Złożoność: O(n + m)
Technika: Rolling hash, modularna arytmetyka

8. Jenne 🎭

Problem: Dopasowywanie wzorca z wildcardami do tekstu
Algorytm: Algorytm KMP z modyfikacjami
Złożoność: O(n)
Technika: Pattern matching z symbolami specjalnymi

9. Forteca Mairona 🏔️

Problem: Obliczanie pola otoczki wypukłej zbioru punktów
Algorytm: Graham Scan / Andrew's Algorithm
Złożoność: O(n log n)
Geometria: Convex Hull, iloczyn wektorowy

10. Łamanie zła ⚗️

Problem: Obliczanie objętości butelek o nieregularnym kształcie
Algorytm: Całkowanie numeryczne (metoda trapezów/prostokątów)
Złożoność: O(n × k) gdzie k to dokładność całkowania
Technika: Numeryczne rozwiązywanie równań całkowych

11. Loptr ⏰

Problem: Obliczanie prawdopodobieństwa wystąpienia wydarzenia w przedziale czasowym
Algorytm: Analiza funkcji dyskretnej w przedziale
Złożoność: O(1)
Technika: Analiza przypadków, arytmetyka modułowa

Kompilacja i uruchamianie

Każde zadanie można skompilować standardowo:

cd [numer_zadania]/
g++ *.cc
./a.out < input.txt

Algorytmy i techniki

Repozytorium demonstruje implementację następujących algorytmów i struktur danych:

Grafowe

• Algorytm Prima - minimalne drzewo rozpinające
• MST z wagami probabilistycznymi - konwersja przez logarytmy

Tekstowe

• Algorytm Rabina-Karpa - wyszukiwanie wzorca z hashowaniem
• Modyfikowany KMP - pattern matching z wildcardami

Geometryczne

• Otoczka wypukła - Graham Scan
• Geometria obliczeniowa - pole wielokąta

Struktury danych

• Drzewo BST - z operacjami przycinania do przedziału
• Priority Queue - w algorytmie Prima

Numeryczne

• Całkowanie numeryczne - metody przybliżone
• Rolling hash - efektywne hashowanie sekwencji

Uwagi

⚠️ Disclaimer: Te rozwiązania służą celom edukacyjnym. Zachęcam do zrozumienia algorytmów i samodzielnego rozwiązywania zadań.

Środowisko deweloperskie

• Kompilator: g++
• System: Linux/Ubuntu
• Testowanie: Lokalne pliki testowe w każdym folderze

Optymalizacje

• Używanie ios_base::sync_with_stdio(false) dla szybszego I/O
• Odpowiednie struktury danych dla każdego problemu
• Dbałość o złożoność czasową i pamięciową