I-ADS

Cvičenia:

Cvičenie 1:
- cvicenie1.pdf
- cvicenie1data.txt
- Nepovinné a doplňujúce úlohy (cvičenie 1)
  - Pre neorientovaný graf G=(V,E) bez slučiek vymyslite (greedy) algoritmus na jeho vrcholové ofarbenie (pozrite si aj Brooksovu vetu). Skúste nájsť graf, ktorý Váš algoritmus nedokáže ofarbiť minimálnym počtom farieb.
  - Pozrite si Kruskalov algoritmus na nájdenie najlacnejšej kostry grafu.
  - Vstupné údaje:
  - Graf_vstup
  - mapOfIndia_4
  - Napíšte algoritmus, ktorý pre dané vstupné pole n prirodzených čísel, pričom každý prvok poľa patrí do intervalu <0;k>, predspracuje vstup a po predspracovaní dokáže odpovedať na otázku, koľko prvkov poľa patrí do intervalu <a;b> pre ľubovoľné a,b také, že 0 ≤ a ≤ b ≤ k, s výpočtovou zložitosťou O(1). Zložitosť predspracovania môže byť Θ(n + k).
    - ADS2022_cvicenie2zadanie
Cvičenie 2:
- ADS-2023-3a
- ADS2021_cvicenie2data
- ADS2021_cvicenie3zadanie
- ADS2021_cvicenie3data
- Nepovinné a doplňujúce úlohy
  - Úloha „Dáma na šachovnici“ : Dama2022-tyzden3
  - Dama2022-tyzden4
  - PlanMesta-tyzden4
  - VstupyMesta
Cvičenie 3:
- Kasíno
- ADS2022_kasino
- ObchodnyCestujuci_2024
- ZSahara_29
- Dzibuti_38
- … …
Cvičenie 4:
- Kradez2024
- ADS_kradezDAT
- Batoh_2hodnoty
- ADS_4DAT
- …
Cvičenie 5:
- Jarné upratovanie2024
- udaje5a
- udaje5b
- Ďalšie úlohy:
- Naštudujte si a implementujte algoritmus LZS compress
- Naštudujte si a implementujte algoritmus Deflate.
Cvičenie 6:
- Elektromobily2024
- Stanice6
Cvičenie 7:
- Nasledujúce dva znáhodnené algoritmy sa dajú použiť pre riešenie problému 3-SAT. Napíšte program, ktorý využíva tieto algoritmy pre riešenie uvedeného problému a experimentálne ich porovnajte (t.j. napr. rýchlosť s akou nájdu interpretáciu premenných, pre ktoré je daná formula pravdivá.)
- Pre porovnanie a vyhodnotenie si vytvorte vlastné, dostatočne veľké, testovacie vstupy.
- 3-sat
Cvičenie 8, 9:
- bez materiálov

Cvičenie 10
- Cvičenie 10
- Vzorové riešenie: Riesenie-AmortA2024
Cvičenie 11
- Zadanie 11
- Vstup: doc_in

Zadania z r. 2023

Cvičenie x:
- ADS2021_cvicenie8zadanie
- ADS2021_cvicenie9zadanie
Cvičenie 8:
- Úloha 35.1-3 zo s.1111 z knihy Cormen a kol.: Introduction to algorithms
  Professor Bundchen navrhuje nasledovnú heuristiku na riešenie problému vrcholového pokrytia. Opakovane vyberajte vrchol s najväčším stupňom a odstráňte všetky hrany s ktorými inciduje. Nájdite príklad, na ktorom ukážete, že profesorova heuristika nemá aproximačný pomer 2.
  (Pomôcka: Skúste bipartitný graf s vrcholmi rovnakých stupňov vľavo a vrcholmi rôznych stupňov vpravo.)
Cvičenie 9:
- Naprogramujte dynamické pole s operáciou vkladania tak, že pri požiadavke na zväčšenie poľa sa alokuje dvojnásobná veľkosť pôvodného poľa.
- Urobte amortizovanú analýzu operácií vkladania v takomto poli.
- https://mrlvsb.github.io/upr-skripta/c/pole/dynamicka_pole.html
- Ak stihnete, naprogramujte aj operáciu vymazávania.
Cvičenie 10:
- Nasledujúce dva znáhodnené algoritmy sa dajú použiť pre riešenie problému 3-SAT. Napíšte program, ktorý využíva tieto algoritmy pre riešenie uvedeného problému a experimentálne ich porovnajte (t.j. napr. rýchlosť s akou nájdu interpretáciu premenných, pre ktoré je daná formula pravdivá.)
- 3-sat
Cvičenie 11:
- Implementujte Treap:
- https://www.ksp.sk/kucharka/treap/
Kontrolovanie zadania č. 2 (za 15 bodov) – pokyny
- Vopred si otestujte Váš program pre veľké vstupy a prípadne zmerajte čas trvania.
- Veľké testovacie vstupy pre zadanie č. 2:
- grafy
- Vstupný graf s 18 vrcholmi (správnosť riešenia je overtiteľná vizuálne):
- graph18
Cvičenie 12
- Riešte aspoň jednu z nasledujúcich úloh.
- Cvičenie 12

Archív, cvičenia 2021:
- ADS2021_cvicenie4zadanie
- ADS2021_cvicenie4data
Cvičenie 5:
- ADS2021_cvicenie5zadanie
- ADS2021_cvicenie5data
Cvičenie 6:
- ADS2021_cvicenie6zadanie
- ADS2021_cvicenie6data
Cvičenie 7:
- ADS2021_cvicenie7zadanie
Cvičenie 10:
- ADS2021_cvicenie10zadanie
Cvičenie 11:
- ADS2021_cvicenie11zadanie
Cvičenie 12:
- ADS2021_cvicenie12zadanie

Archív, cvičenia 2021: