Viikon 5 aiheena on eksponentiaaliset algoritmit. Tehtävät 1-3 käsittelevät eksponentiaalisia hakualgoritmeja ja tehtävät 5-6 dynaamista ohjelmointia osajoukoilla. KKKK luku 5 kertoo hakualgoritmeista ja luvusta 10, erityisesti kohdasta 10.4, on hyötyä tehtävissä 5-6.

Alla on vihjeitä tehtäviin. Kannattaa kuitenkin ensin miettiä ilman vihjettä. Vihjeen näet maalaamalla sen hiirellä.

Omenat

[hint]O(3^n) ratkaisu jossa kokeillaan kaikkia vaihtoehtoja on tarpeeksi nopea[/hint]

Kaverit

[hint]Kaikki valinnat voidaan saada lisäämällä uusi asukas johonkin toiseen valintaan[/hint]

Summa

[hint]KKKK 5.5[/hint]

Sanaketju

[hint]Laske jokaiselle sanojen osajoukolle $S$ ja merkille $c$, kuinka monta sanaketjua sanoista $S$ voi muodostaa siten, että viimeinen merkki on $c$.[/hint]

Laatoitus

[hint]Laske kaikille luvuille $i \leq n$ ja $m$-pituisille bittijonoille $B$, kuinka monella tavalla voit laatoittaa $i\times m$-ruudukon $2\times 1$- ja $1\times 2$-laatoilla siten, että ainoastaan ne ruudukon alareunan kohdat joita vastaava bittijonon $B$ bitti on 1 jäävät laatoittamatta.[/hint]