Cvičenia: 9. týždeň

Ciele cvičení:

  • rozumieť priemernej a agregovanej zložitosti
  • rozumieť základným princípom hashovania
  • vedieť, ako možno hashovanie využiť pri ukladaní dát a následnej práci s nimi
  • vedieť, ako možno hashovanie využiť pri stringologickom Karp-Rabin-ovom algoritme

Budovanie HashSet-u

Pomocou poľa LinkedList-ov implementujte triedu, ktorá realizuje HashSet reťazcov s nemenným počtom priehradok. Poznámka: Použite hash-ovaciu funkciu z prednášky.

Pred implementáciu rozdiskutujte:

  • aké konštruktory je potrebné vytvoriť,
  • ako implementovať hash-ovaciu funkciu tak, aby sme nemali redundantný kód a vedeli ju neskôr jednoducho modifikovať.

Trieda nech obsahuje metódy:

public void add(String s);
public boolean contains(String s);
public int getCapacity(); // vrati velkost interneho pola
public int size(); // vrati pocet ulozenych retazcov
public double getLoadFactor();
public String toString();
public void printStructure(); // vypise strukturovany obsah
[$[Get Code]]
  • Zistite, či vaša implementácia naozaj reprezentuje množinu alebo vieme pridať rovnaký reťazec dvakrát.
  • Zmeňte použitú hash-ovaciu funkciu aby bola založená na lineárnej kongruencii s parametrom a. Upravte implementáciu aby sme parameter a vedeli zadať v konštruktore.
  • Rozdiskutujte vlastnosti hash-ovacej funkcie pre prípad, že veľkosť poľa je násobkom parametra a.
  • Pridajte metódu remove a upravte metódu add tak , aby Load Factor bol vždy medzi hodnotami 0,25 a 0,75. Poznámka: Táto implementácia nebude mať pevný počet priehradok.

Hľadanie výskytu intuitívne

Implementujte naivný algoritmus na nájdenie všetkých výskytov vzorky v reťazci. Využitie pritom schému:

public static void najdiVyskyty(String retazec, String vzorka) {
        int poz = 0;
        while (poz <= retazec.length() - vzorka.length()) {
                int i = 0;
                while (vzorka.charAt(i) == retazec.charAt(poz + i)) {
                        //...
                }

                //...
        }
}
[$[Get Code]]
  • Je pravdou, že každý "zaujímavý" okamih výpočtu možno charakterizovať obsahom premenných poz a i?

Algoritmus Karp-Rabin

  • Implementujte algoritmus Karp-Rabin z prednášky.
  • Rozdiskutujte zmeny v algoritme ak by sme uvažovali aj s použitím iných znakov ako malé a veľké písmena anglickej abecedy.
  • Rozdiskutujte pre aký najdlhší hľadaný reťazec s uvedeným hash-ovanim algoritmus funguje a prečo?

Pole s kapacitou a HashSet dôkazy

  • Dokážte, že amortizovaná zložitosť ľubovoľných n po sebe vykonaných operácii pridania a odobrania z koncu poľa s kapacitou bude O(n).
  • Dokážte, že amortizovaná zložitosť ľubovoľných n po sebe vykonaných operácii pridania a odobrania z vašej implementácie HashSet-u bude O(n).
  • Využite poznatky z predchádzajúcich dvoch bodov na návrh vylepšenej implementácie zásobníka a radu z tretieho cvičenia a popíšte zložitosť operácii (vkladania a vyberania) v rôznych prípadoch.
    • Toto riešenie sa vám môže zísť na štátniciach.