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
• Zadanie c. 2 (2-SAT, 2024)
  • Testovacie vstupy:  Vstupy_2SAT
• Koniec semestra

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