🎓 AGH - Algorytmy i Struktury Danych

✍️ Słowem wstępu...

To repozytorium zawiera rozwiązania zadań, kolokwiów, egzaminów oraz wiele przydanych algorytmów, jakie przydały mi się podczas zajęć z przedmiotu Algorytmy i Struktury Danych prowadzonego w latach 2020-2021.

Algorytmy zostały napisane z dbałością o czytelność kodu, niską złożoność obliczeniową, a przy każdym algorytmie umieszczone zostały komentarze (oraz czasem ilustracje), wyjaśniające jego działanie.

🤔 Rozwiązania zadań

---

Poniższe sekcje zawierają rozwiązania zadań z laboratoriów, zajęć prowadzonych przez koło BIT Algo, kolokwiów oraz egzaminów. Większość zadań została rozwiązana w Jupyter Notebooku, dzięki czemu możliwe było załączenie ilustracji, obrazujących ideę rozwiązania, równań matematycznych pisanych z użyciem Latex'u oraz dodanie czytelnych komentarzy, wyjaśniających krok po kroku rozwiązanie zadania.

Zadania z zajęć

---

W tej sekcji znajdują się rozwiązania zadań z laboratoriów.

---

1. Laboratorium

   • 1. Proste Algorytmy Sortowania
   • 2. Sortowanie Listy Jednokierunkowej
   • 3. Złożoność Sortowania Prostego
   • 4. Min-Max
   • 5. Odwracanie Listy
   • 6. Wyszukiwanie Binarne
   • 7. Szukanie Sumy

2. Laboratorium

   • 1. Merge Sort I Listy Jednokierunkowe
   • 1A. Merge Sort - Złączanie Serii Naturalnych
   • 2. Liczba Inwersji Tablicy
   • 3. Szukanie Sumy
   • 4. Pojemniki Z Wodą
   • 5. Lider Ciągu
   • 6. Największy Przedział

3. Laboratorium

   • 1. Quick Sort Maksymalnie Olog N Pamięci
   • 2. Wstawianie Elementu Do Kopca Binarnego
   • 3. Quick Sort Bez Rekurencji Z Własnym Stosem
   • 4. Scalanie K Posortowanych List Jednokierunkowych
   • 5. Struktura Z Wstawianiem, Usuwaniem Maksimum I Minimum W Czasie Olog N
   • 6. Struktura Ze Wstawianiem I Odczytem Mediany W Czasie Olog N
   • 7. Partition Hoare'A
   • 9. Select

4. Laboratorium

   • 1. Sortowanie W Czasie Liniowym Tablicy N Liczb Ze Zbioru 0, ..., N^2-1
   • 2. Najszybsze Sortowanie Tablicy Długości N, W Której Jest Tylko Logn Różnych Wartości
   • 3. Liniowe Sprawdzanie, Czy Dwa Słowa Są Anagramami
   • 4. Struktura Danych Ze Wstawianiem, Zliczaniem Elementów I Resetowaniem W Czasie O1
   • 6. Znajdowanie Największej Różnicy Sąsiednich Liczb W Czasie On
   • 7. Podciąg Minimalnej Długości, Zawierający Wszystkie K Kolorów

5. Laboratorium

   • 1. 0-1 Knapsack On Sump Time Complexity, Where P - Array Of Profits
   • 2. Czy Istnieje Podciąg Ciągu Liczb Naturalnych, Który Sumuje Się Do T
   • 3. Najdłuższy Wspólny Podciąg
   • 3.2. Najdłuższy Podciąg Rosnący
   • 4. Mnożenie Macierzy
   • 5. Maximin
   • 6. Wydawanie Monet
   • 7. Wędrówka Po Szachownicy

6. Laboratorium

   • 1. Black Forest
   • 2. Spadające Klocki
   • 3. Ładowanie Promu
   • 4. Głodna Żaba
   • 5. Dwuwymiarowy Problem Plecakowy
   • 6. Ścieżka W Drzewie
   • 7. Sklejanie Odcinków

7. Laboratorium

   • 1. Tankowanie Czołgu
   • 2. Pokrycie Przedziałami Jednostkowymi
   • 3. Wybór Zadań Z Terminami
   • 4. Ładowanie Przyczepy
   • 5. Wieże
   • 6. Suma Odległości

8. Laboratorium

   • Dodaj Lepszy Sposób [Standardowe] 6. Bezpieczny Przelot
   • [Dodatkowe] 1. Kapitan Statku, Zadanie Z Kolokwium 2012-13
   • [Dodatkowe] 2. Czy Nieskierowany
   • [Obowiązkowe] 1. Pause
   • [Obowiązkowe] 2. Cykl Na 4
   • [Standardowe] 1. Dfs-Bfs
   • [Standardowe] 2. Uniwersalne Ujście
   • [Standardowe] 3. Bfs I Najkrótsze Ścieżki
   • [Standardowe] 4. Malejące Krawędzie
   • [Standardowe] 5. Krawędzie 0-1
   • [Standardowe] 7. Kosztowna Szachownica

9. Laboratorium

   • [Standardowe] 1. Ścieżka Hamiltona W Dagu
   • [Standardowe] 2. Dobry Początek - Wierzchołek, Z Którego Dojdziemy Do Każdego Innego Wierzchołka
   • [Standardowe] 3. Najkrótsze Ścieżki W Dagu
   • [Standardowe] 4. Logarytmy - Ścieżka O Minimalnym Iloczynie Wag
   • [Standardowe] 5. Problem Przewoźnika Turystycznego - Ścieżka O Maksymalnej Wartości Minimalnej Wagi
   • [Standardowe] 6. Dwóch Kierowców - Ścieżka Minimalnej Sumie Wag Co Drugiej Krawędzi
   • [Standardowe] 7. Problem Stacji Benzynowych Na Grafie

10. Laboratorium

    • #Todo [Standardowe] 2. Wyścigi
    • [Obowiązkowe] 1. Ścieżka O Malejących Krawędziach I Najmniejszej Sumie Wag Krawędzi
    • [Obowiązkowe] 2. Domknięcie Przechodnie Grafu
    • [Standardowe] 1. Sat-2Cnf
    • [Standardowe] 3. Wymiana Walut
    • [Standardowe] 4. Szachuję
    • [Standardowe] 5. Autostrady
    • [Standardowe] 6. Najlepszy Korzeń

11. Laboratorium

    • [Bst] 1. Indeksowanie Drzewa Bst
    • [Bst] 2. Suma Wszystkich Wartości W Drzewie Binarnym
    • [Bst] 3. Geny - Sprawdzanie, Czy Wszystkie Sekwencje Dna Są Parami Różne
    • [Bst] 4. Klocki
    • [Obowiązkowe] 1. Wiele Źródeł I Wiele Ujść
    • [Obowiązkowe] 2. Następnik W Drzewie Bst
    • [Max-Flow] 1. Maksymalne Skojarzenie W Drzewie
    • [Max-Flow] 2. Spójność Krawędziowa
    • [Max-Flow] 3. Formuły Logiczne Z Dwoma Wystąpieniami Zmiennej
    • [Max-Flow] 5. Maksymalna Liczba Rozłącznych Wierzchołkowo Ścieżek Z S Do T

Zadania BIT Algo

---

W tej sekcji znajdują się rozwiązania zadań z zajęć prowadzonych przez koło naukowe BIT Algo.

---

1. Zajęcia

   Niestety nie mam rozwiązań z 1. zajęć. Zadania były proste i podobne do tych z 1. laboratoriów.

2. Zajęcia

   • 1. Sortowanie Punktów Względem Odległości
   • 2. Sortowanie Tablicy Stringów W Czasie Liniowym
   • 4. Liczba Wartości W Zakresie - Złożoność O1
   • 5. Sortowanie Tablicy Z Kilkoma Wartościami Spoza Zakresu
   • 6. Tablica Zwierająca Wiele Powtórzeń - Sortowanie W Czasie On Loglogn
   • 7. Tablica N Liczb Z Zakresu [0...N^2-1]
   • 8. Sortowanie Listy Odsyłaczowej O Wartościach O Rozkładzie Jednostajnym
   • 9. Najczęściej Powtarzający Się Spójny Podciąg Długości K

3. Zajęcia

   • 1. Sprawdzanie, Czy Zbiory Są Rozłączne
   • 2. Podział Tablicy Na N Par O Najmniejszej Maksymalnej Sumie Liczb W Parze
   • 3 Dodatkowe. Algorytm, Który Rozstrzyga, Czy Każda Liczba Jest Sumą 2 Innych Liczb W Tablicy
   • 3. Sprawdzanie, Czy K. Największy Element Kopca Min Heap Jest Większy Lub Równy X
   • 4. Nieskończona Posortowana Tablica
   • 5. Sprawdzanie, Czy W Posortowanej Tablicy Istnieje Indeks I Taki, Że A[I] == I
   • 6. Najmniejsza Sumaryczna Odległość Od Wszystkich Punktów Na Osi
   • 7. Czy Istnieje Trójka Liczb Każda Z Innej Tablicy Taka, Że A + B = C
   • 8. Liczba Różnych Elementów Z Tablicy A O Różnicy Równej K
   • 9. Sortowanie Liczb Według Liczby Cyfr Jednokrotnych I Wielokrotnych
   • Dodatkowe 1. Najmniejszy Zbiór Punktów, Które Dominują Wszystkie Pozostałe

4. Zajęcia

   • 1. Cięcie Pręta
   • 2. Jak Zadanie 1., Ale Z Wypisywaniem Fragmentów Pręta
   • 3. Rekurencyjne Schody Amazona
   • 4. Minimalny Koszt Przejścia Z Pola [0][0] Do Pola [M-1][N-1]
   • 5. Najdłuższa Ścieżka Wartości Rosnących W Tablicy 2D
   • 6. Liczba Ciągów Binarnych Bez 0 I 1 Obok Siebie
   • 7. Gramy W Grę, Wybieramy Wartość Z Jednego Końca Tablicy
   • 8. Najdłuższy Fragment Stringu, Który Jest Palindromem
   • 9. Długość Najdłuższej Ścieżki Prostej W Dagu

5. Zajęcia

   • 1. Dodawanie Liczb Tak Aby Wartość Bezwzględna Sumy Po Dodaniu Każdej Pary Była Najmniejsza
   • 2. Napis Złożony Z Napisów Wielokrotnych - Maksymalna Szerokość
   • 3. Skoki Żaba Zbigniewa Po Osi Liczbowej
   • 4. Czarodziej Pascal I Największe Piękno Talerzy Ze Stosów
   • 5. Najdłuższa Ścieżka W Acyklicznym Grafie Skierowanym
   • 6. Czy String Jest Poprawnym Słowem Z Danego Języka
   • 7. Czy Da Się Zebrać Określoną Kwotę
   • 7.2. Prostokątny Kawałek Tkaniny - Największy Zysk Z Pocięcia
   • 8. Czy Istnieje Podzbiór Zbioru, Który Sumuje Się Do M

6. Zajęcia

   • 2. Wydawanie Monet
   • 3. Bezkonfliktowa Obsługa Pociągów Przez M Stacji
   • 4. Minimalna Liczba Maszyn Do Ochrony Miasta
   • 5. Najkrótszy Zbiór K Rozłącznych Przedziałów Otwartych
   • 6. Usuwanie Duplikatów Ze Stringa
   • 7. Największy Zysk Z K Zleceń Przy Ustalonym Minimalnym Kapitale
   • 8. Przyjęcie U Alicji - Największa Liczba Osób Spełniających Warunki

7. Zajęcia

   • 1. Detekcja Cyklu W Grafie Nieskierowanym
   • 2. Wiadomość - Znajomi Przekazują Znajomym
   • 3. Jeziora - Różne Warianty
   • 4. Sklejanie Przedziałów
   • 5. Sejf - Minimalna Liczba Naciśnięć Przycisków, By Go Odblokować
   • 6. Rozmiary Poddrzew
   • 7. Domy I Sklepy - Znajdowanie Odległości Każdego Domu Od Najbliższego Sklepu
   • 8. Średnica Drzewa

8. Zajęcia

   • 1. Krasnoludy I Trolle - Wysadzanie Mostu W Grafie
   • 2. Dostarczanie Przesyłek - Minimalny Dystans, Jaki Trzeba Przebyć
   • 3. Szach I Goniec - Dużo Mapowania Grafów I Sprawdzanie, Czy Graf Zawiera Cykl Eulera
   • 4. Domino - Zadanie Na Spójne Składowe
   • 5. Liczba Możliwych Ścieżek Między Parą Wierzchołków W Dagu - Dfs

9. Zajęcia

   • #Toimprove 1. Spadające Klocki
   • 2. Problem Plecakowy - Liczba Sposobów
   • 3. Żeglarz Henryk - Grafy
   • 4. Sasza I Matrioszki - Lis
   • 5. Opieka Nad Dzieckiem - Zachłanny
   • 6. Pakowanie Bagaży - Zwykła Algorytm Na Sumę Podzbioru Z Użyciem Plecakowego
   • Dodatkowe 1. Wszystkie C4 W Grafie Nieskierowanym

10. Zajęcia

    • 1. Windy W Drapaczu Chmur
    • 2. Litery Równoważne
    • 3. Drzewo Najkrótszych Ścieżek
    • 4. Lotniska
    • 5. Ścieżki Superfajne
    • 6. Najtańsza Podróż Z Tankowaniem
    • 7. Domy I Sklepy

11. Zajęcia

    • 1. Wyspy - Egzamin 2020
    • 2. Jak Dojadę
    • 3. Algorytm Floyda-Warshalla - Rekonstrukcja Najkrótszej Ścieżki Między Dowolną Parą Wierzchołków
    • 4. Problem Wymiany Walut
    • 5. Krawędź Zmniejszająca Dystans
    • 6. Najkrótszy Cykl Pod Względem Wagowym
    • 7. Uogólnienie Problemu Najkrótszych Ścieżek
    • 8. Dziwne Opłaty

12. Zajęcia

    • 1. Stopnie Znajomości - Najkrótsze Ścieżki Bfs Lub Floyd-Warshall
    • 2. Kafejka Internetowa - Maksymalny Przepływ
    • 3. Krakowskie Korki - Najkrótsze Ścieżki O Dwóch Parametrach
    • 4. Arktyczna Sieć - Mst
    • 5. Sabotaż - Min-Cut
    • 6. Spotkanie Z Profesorem - Dijkstra Dla Grafu O Krawędziach Z Ograniczeniami

Zadania obowiązkowe (z wykładów)

---

W tej sekcji znajdują się rozwiązania zadań obowiązkowych, które zostały zadane na wykładzie. Rozwiązania tych zadań znajdują się również w sekcji Zadania z zajęć.

---

• 2. Wykład

  • 1. Quick Sort Maksymalnie Olog N Pamięci
  • 2. Wstawianie Elementu Do Kopca Binarnego

• 3. Wykład

  • 1. Tablica N Liczb Z Zakresu [0...N^2-1]
  • 2. Tablica Zwierająca Wiele Powtórzeń - Sortowanie W Czasie On Loglogn

• 5. Wykład

  • 1. 0-1 Knapsack On Sump Time Complexity, Where P - Array Of Profits
  • 2. Czy Istnieje Podciąg Ciągu Liczb Naturalnych, Który Sumuje Się Do T

• 7, Wykład

  • 1. Tankowanie Czołgu - Różne Warianty

• 8. Wykład

  • 1. Sprawdzanie, Czy Graf Jest Dwudzielny

• 9. Wykład

  • 1. Usuwanie Wierzchołków Z Grafu Skierowanego, By Pozostawał Zawsze Spójny
  • 2. Szukanie Cyklu Długości 4 W Grafie

• 12. Wykład

  • 1. Najkrótsza Ścieżka O Malejących Wagach Między Parą Wierzchołków
  • 2. Domknięcie Przechodnie Grafu Skierowanego

• 13. Wykład

  • 1. Poprzednik Lub Następnik W Drzewie Bst
  • 2. Maksymalny Przepływ W Sieci O Kilku Źródłach I Kilku Ujściach

Zadania offline

---

W tej sekcji znajdują się rozwiązania tzw. zadań offline. Zadania offline były to zadania domowe na dodatkowe punkty. Po przesłaniu, losowane były osoby, którym zadanie zostanie ocenione.

---

• 1. Zadanie

  • Treść
  • Rozwiązanie

• 2. Zadanie

  • Treść
  • Rozwiązanie

• 3. Zadanie

  • Treść
  • Rozwiązanie

• 5. Zadanie

  • Treść
  • Rozwiązanie

• 6. Zadanie

  • Notatki
  • Treść
  • Rozwiązanie

• 7. Zadanie

  • Treść
  • Rozwiązanie

• 8. Zadanie

  • Treść
  • Rozwiązanie

• 9. Zadanie

  • Treść
  • Rozwiązanie

• 10. Zadanie

  • Treść
  • Rozwiązanie

• 11. Zadanie

  • Treść
  • Rozwiązanie

• 12. Zadanie

  • Treść
  • Rozwiązanie

Kolokwia

---

W tej sekcji znajdują się rozwiązania zadań z kolokwiów. Część jest rozwiązana bez szczegółowych wyjaśnień. Nie wszystkie zadania są rozwiązane.

---

1. 2012-2013

   • I Kolokwium

     • 1. Zadanie
     • 2. Zadanie
     • 3. Zadanie

   • II Kolokwium

     • Grupa A

       • 3. Zadanie

     • Grupa B

       • 3. Zadanie

2. 2014-2015

   • I Kolokwium

     • 1. Zadanie
     • 2. Zadanie
     • 3. Zadanie

   • II Kolokwium

     • 3. Zadanie

3. 2015-2016

   • I Kolokwium

     • 1. Zadanie
     • 2. Zadanie
     • 3. Zadanie

4. 2016-2017

   • I Kolokwium

     • 1. Zadanie
     • 2. Zadanie
     • 3. Zadanie

   • II Kolokwium

     • 1. Zadanie

5. 2018-2019

   • I Kolokwium

     • 1. Zadanie
     • 2. Zadanie

6. 2019-2020

   • I Kolokwium

     • 1. Zadanie
     • 2. Zadanie
     • 3. Zadanie

   • II Kolokwium

     • 1. Zadanie

   • I Kolokwium zaliczeniowe

     • 1. Zadanie
     • 2. Zadanie
     • 3. Zadanie
     • 3. zadanie (bardziej szczegółowe)

   • II Kolokwium zaliczeniowe

     • 1. Zadanie
     • 2. Zadanie
     • 3. Zadanie

7. 2020-2021

   • I Kolokwium

     • 1. Zadanie
     • 2. Zadanie
     • 3. Zadanie

   • II Kolokwium

     • 1. Zadanie
     • 2. Zadanie
     • 3. Zadanie

   • III Kolokwium

     • 1. Zadane
     • 2. Zadane
     • 3. Zadane

   • I Kolokwium zaliczeniowe

     • 1. Zadanie
     • 2. Zadanie
     • 3. Zadanie

   • II Kolokwium zaliczeniowe

     • 1. Zadanie
     • 2. Zadanie ( -> szczegółowy opis)
     • 3. Zadanie

Egzaminy

---

W tej sekcji znajdują się rozwiązania zadań z egzaminów (tych mam najmniej).

---

1. 2012-2013

   • Grupa A

     • 1. Zadanie
     • 2. Zadanie
     • 3. Zadanie

   • Grupa B

     • 1. Zadanie
     • 2. Zadanie
     • 3. Zadanie

2. 2019-2020

   • I Termin

     • 1. Zadanie
     • 2. Zadanie
     • 3. Zadanie

   • II Termin

     • 1. Zadanie
     • 2. Zadanie
     • 3. Zadanie

   • III Termin

     • 1. Zadanie
     • 2. Zadanie
     • 3. Zadanie

3. 2020-2021

   Niektóre zadania dałoby się lepiej rozwiązać

   • Termin zerowy

     • 1. Zadanie
     • 1. Zadanie (lepsze rozwiązanie)
     • 2. Zadanie
     • 3. Zadanie
     • 3. Zadanie (ze zwracaniem ścieżek)

   • I Termin

     • 1. Zadanie
     • 2. Zadanie

   • II Termin

     • 2. Zadanie

   • III Termin

     • 1. Zadanie ( -> szczegółowy opis)
     • 2. Zadanie
     • 3. Zadanie (słabe rozwiązanie)
     • 3. Zadanie (lepsze rozwiązanie v1)
     • 3. Zadanie (lepsze rozwiązanie v2)

⚙️ Algorytmy - szczegółowy opis oraz implementacje

---

Poniższe sekcje zawierają moje implementacje algorytmów wykorzystywanych podczas rozwiązywania zadań. Każdy algorytm został szczegółowo opisany, wyznaczona została złożoność obliczeniowa oraz pamięciowa, a także przeprowadzone zostały testy poprawności.

Algorytmy z wykładów

---

W tej sekcji znajdują się moje implementacje algorytmów omawianych na wykładach wraz ze szczegółowym opisem oraz testami poprawności.

---

1. Algorytmy grafowe

   • Dfs Cykl Eulera, Ścieżka Eulera, Spójność
   • Dfs Sortowanie Topologiczne Dagu
   • Algorytm Bellmana-Forda - Najkrótsze Ścieżki Jeden Do Wszystkich, Dowolne Wagi
   • Algorytm Dijsktry - Najkrótsze Ścieżki Jeden Do Wszystkich, Tylko Nieujemne Wagi
   • Algorytm Floyda-Warshalla - Najkrótsze Ścieżki Między Każdą Parą Wierzchołków, Dowolne Wagi
   • Mst - Algorytm Kruskala
   • Mst - Algorytm Prima
   • Maksymalny Przepływ Grafy Skierowane Lub Nieskierowane
   • Reprezentacja Grafu, Bfs I Dfs
   • Silnie Spójne Składowe Grafu Skierowanego
   • Znajdowanie Maksymalnych Skojarzeń W Grafach Dwudzielnych
   • Znajdowanie Mostów W Grafie, Punkty Artykulacji
   • [Wykorzystywane. Przez Grafowe] Rodzina Zbiorów Rozłącznych

2. Algorytmy zachłanne

   • Ciągły Problem Plecakowy
   • Kodowanie Huffmana
   • Problem Szeregowania Zadań

3. Algorytmy dynamiczne

   • Dyskretny Problem Plecakowy
   • Impreza Instytutowa Firmowa
   • Impreza Instytutowa Ii
   • Najdłuższy Rosnący Podciąg Niespójny
   • Problem Komiwojażera

4. Algorytmy

   • Drzewa Bst
   • Drzewa Czerwono-Czarne
   • Drzewa Przedziałowe

Moje opracowania - pomocne w nauce

---

W tej sekcji znajdują się moje przemyślenia dotyczące algorytmów, różne implementacje, porównania ich wydajności oraz przykłady zastosowań - kiedy, który algorytm, dla jakich danych.

Materiał zawarty w tej sekcji może posłużyć do powtórzenia wiadomości z danego zakresu. Algorytmy oraz struktury danych zostały pogrupowane tematycznie w poszczególnych plikach, dzięki czemu łatwiejsze było porównanie ich zastosowania oraz charakterystyki.

---

Moje opracowania

• Algorytmy Sortowania - Listy Odsyłaczowe Jednokierunkowe
• Algorytmy Sortowania - Tablice
• Algorytmy Wyszukiwania i Wybierania
• Drzewiaste Struktury Danych
• Liniowe Struktury Danych