dn-5.md

5. domača naloga

Pri tej domači nalogi boste rešili nekaj računskih problemov s pomočjo metod, ki smo jih spoznali na predavanjih. Vse naloge rešujte v OCamlu, vsako rešitev pa dobro dokumentirajte, da bo iz nje razvidna pravilnost ter časovna zahtevnost rešitve.

Pri vsaki nalogi bomo ocenjevali učinkovitost, preglednost in eleganco rešitve ter natančnost, razumljivost in pravilnost spremnega besedila.

Deli in vladaj

Rešiti morate dva klasična problema, ki se rešujeta z metodo deli in vladaj.

Hitro izbiranje

Dan naj bo neurejen seznam celih števil $[a_1, \dots, a_n]$ in število $1 \le k \le n$. Napišite algoritem, ki v času $O(n)$ poišče po velikosti $k$-to število v seznamu. Torej za $k = 1$ bi algoritem vrnil najmanjše, za $k = n$ pa največje število v seznamu.

Najbližji par točk v ravnini

Dan naj bo seznam točk $[(x_1, y_1), \dots, (x_n, y_n)]$ v ravnini. Napišite algoritem, ki v času $O(n \log n)$ izračuna par točk $(x_i, y_i)$ in $(x_j, y_j)$, ki sta si med vsemi točkami v seznamu najbližje.

Dinamično programiranje

Iz spodnjega seznama nalog na strani Project Euler rešite naloge, skupaj vredne vsaj 6 točk:

• #31 Coin Sums: 1 točka
• #67 Maximum Path Sum II: 1 točka
• #82 Path Sum: Three Ways: 2 točki
• #115 Counting block Combinations II: 2 točki
• #117 Red, Green, and Blue Tiles: 2 točki
• #215 Crack-free walls: 3 točke
• #534 Weak Queens: 4 točke