5. domača naloga

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: