Tehtävä 1a - Hajautustaulu-teoria¶

Aineistona on koordinaatit (x,y), joihin on liitetty väri. X- ja y-koordinaatien tietotyyppinä on unsigned int, ja värin tietotyyppinä string. Aineisto on tallennettuna ketjutettuun hajautustauluun, jossa avaimena käytetään koordinaattia. Hajautustaululla on 7 ämpäriä, ja käytettävä hajautusfunktio on h((x,y)) = 13*x*y mod 7.

1. Lisää seuraavat alkiot hajautustauluun ja kerro jokaisen alkion lisäyksen jälkeen kunkin ämpärin sisältö: (1, 1):punainen, (2,2):vihreä, (11,8):sininen, (154, 987):keltainen, (63, 5):valkoinen
2. Mikä on hajautustaulun täyttöaste alkioiden lisäämisen jälkeen?
3. Onko hajautusfunktio hyvä? Jos ei, niin kehittele parempi.

Tehtävä 1b - Hajautusfunktio - taikaluku¶

Selitä, miten taikaluku 0x9e3779b9 lasketaan boost::hash_combine -funktiossa (sama kuin hash-funktio koordinaateille customtypes.hh:ssa prg1:ssä ja prg2:ssa)?

Tehtävä 2a - Kruskalin algoritmi-teoria¶

Graafin virittävä puu (a spanning tree for a graph) on graafin kaarien osajoukko, joka yhdistää kaikki solmut ja muodostaa puun, eli tulos ei sisällä silmukoita (cycles). Yhdelle graafille on tyypillisesti monia mahdollisia virittäviä puita. Pienin virittävä puu (minimal spanning tree) on puu, jossa sen kaarien painojen summa on pienin. Pienin virittävä puu on hyödyllinen, jos on tarve minimoida kokonaiskustannus, eli luoda halvin mahdollinen graafi, jossa voi vielä tavoittaa kaikki solmut. Tällaisia ongelmia voit tavata esimerkiksi viestintäverkkojen konfiguroinnin ja rakentamisen yhteydessä.

Kruskalin algoritmi on yksi tapa luoda pienin virittävä puu. Lue algoritmista enlanninkielisestä Wikipedia-artikkelista Kruskal’s algorithm . Miten algoritmi toimii ja luo pienimmän virittävän puun? Huomaatko, miksi se luo nimenomaan pienimmän virittävän puun? Kruskalin algoritmi toimii myös, jos graafi ei ole yhdistetty. Tällöin se luo automaattisesti joukon virittäviä puita, eli metsän.

Tehtävä 2b - Kruskalin algoritmi-toteutus¶

Suorita Kruskalin algoritmi alla olevalle graafille. Palauta lista jäljelle jääneistä kaarista.