I-ADS

Cvičenia:

  • Cvičenie 1:
  • Cvičenie 2:
    • 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).
  • Cvičenie 2b (nepovinné):
  • Cvičenie 3:
  • Cvičenie 4:
  • Cvičenie 5:
  • Cvičenie 6:
  • Cvičenie 7:
  • 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:
  • 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šenie úlohy 4 z písomky počas semestra