-----------------------------------------------------------
PITANJA ZA OBNAVLJANJE TEHNIKA ZA POPRAVLJANJE SLOŽENOSTI ALGORITAMA
-----------------------------------------------------------

1. Složenost Euklidovog algoritma zasnovanog na oduzimanju je:
a) linearna u odnosu na vrednost većeg argumenta
b) logaritamska u odnosu na vrednost većeg argumenta
c) kvadratna u odnosu na vrednost većeg argumenta
d) eksponencijalna u odnosu na broj cifara većeg argumenta
e) linearna u odnosu na broj cifara većeg argumenta
 
-----------------------------------------------------------

2. Složenost Euklidovog algoritma zasnovanog na deljenju je:
a) linearna u odnosu na vrednost većeg argumenta
b) logaritamska u odnosu na vrednost većeg argumenta
c) kvadratna u odnosu na vrednost većeg argumenta
d) eksponencijalna u odnosu na broj cifara većeg argumenta
e) linearna u odnosu na broj cifara većeg argumenta
 
-----------------------------------------------------------

3. Složenost optimizovane verzije klasičnog algoritma
za ispitivanje da li je broj n prost je:
a) O(n)
b) O(log(n))
c) O(sqrt(n))
d) O(nlog(log(n)))
 
-----------------------------------------------------------

4. Kada se u Eratostenovom situ precrtavaju umnošci broja d,
može da se krene od vrednosti:
a) d
b) 2*d
c) d*d
d) sqrt(d)
 
-----------------------------------------------------------

6. Pod pretpostavkom da se sve aritmetičke operacije izvršavaju u vremenu O(1)
određivanje svih prostih brojeva u intervalu od 0 do n je moguće uraditi:
a) ispitivanjem svakog pojedinačnog broja u složenosti O(n^2)
b) ispitivanjem svakog pojedinačnog broja u složenosti O(n sqrt(n))
c) ispitivanjem svakog pojedinačnog broja u složenosti O(n*log(log(n)))
d) Eratostenovim sitom u složenosti O(n)
e) Eratostenovim sitom u složenosti O(nlog(n))
f) Eratostenovim sitom u složenosti O(nlog(log(n)))
 
-----------------------------------------------------------

7. Ako bismo sve proizvode prefiksa P niza a racunali inkrementalno,
mogli bismo da koristimo rekurentnu seriju:
a) P_0 = 1, P_{k+1} = P_{k}*P_{k-1}
b) P_0 = 1, P_{k+1} = P_{k}*a_k
c) P_1 = a_0, P_{k+1} = P_{k}*a_k
d) P_0 = 1, P_{k} = P_{k+1}/a_k
 
-----------------------------------------------------------

8. Koje bi vremenske, a koje prostorne složenosti bilo izračunavanje
za svaku vrednost $i$ minimuma prvih $i$ elemenata date serije
korišćenjem tehnike inkrementalnosti?
a) vremenska O(n^2), prostorna O(n)
b) vremenska O(n), prostorna O(1)
c) vremenska O(1), prostorna O(n)
d) vremenska O(n), prostorna O(n)
 
-----------------------------------------------------------

9. Ukoliko za dati niz $a$ čuvamo niz suma njegovih prefiksa $P$
tako da se na poziciji $k$ nalazi suma prvih $k$ elemenata niza,
čemu je jednak zbir elemenata u segmentu pozicija [a,b]?
a) P_{b} - P_{a}
b) P_{b+1} - P_{a}
c) P_{b} - P_{a-1}
d) P_{a} + P_{b}
 
-----------------------------------------------------------

10. Ukoliko je potrebno m puta racunati sumu nekih segmenata
niza dimenzije n, koja će biti složenost ako koristimo niz prefiksa?
a) O(m)
b) O(n)
c) O(m + n)
d) O(m * n)
 
-----------------------------------------------------------

11. Ako je niz zadat razlikama svojih susednih elemenata
na koji način računamo elemente polaznog niza?
a) računanjem suma susednih elemenata niza razlika
b) računanjem prefiksnih suma niza razlika
c) ne možemo ih izračunati
 
-----------------------------------------------------------

12. Šta karakteriše algoritme zasnovane na tehnici dva pokazivača?
a) svaka brojačka promenljiva se uvek kreće u istom smeru
b) brojačke promenljive uvek rastu
c) brojačke promenljive uvek opadaju
d) složenost je po pravilu linearna
e) složenost je po pravilu kvadratna
f) složenost je po pravilu O(nlog(n))
 
-----------------------------------------------------------

13. Ako se tehnikom dva pokazivača u sortiranom nizu traže
parovi elemenata u nizu čija je razlika jednaka datoj, moguće je da se:
a) oba pokazivača kreću s leva na desno
b) oba pokazivača kreću s desna na levo
c) levi pokazivač ide nadesno, a desni nalevo
d) levi pokazivač ide nalevo, a desni nadesno
 
-----------------------------------------------------------

14. Ako je niz a sortiran opadajuće rotiran za $k$ pozicija ulevo,
kako možemo da tražimo najveći element u nizu $a$ traženjem prelomne tačke u nizu?
a) kao prvi element veći od a[0]
b) kao prvi element veći ili jednak a[0]
c) kao prvi element veći od a[n-1]
d) kao prvi element veći ili jednak od a[n-1]
e) kao prvi element veći od svog sledbenika
f) kao prvi element veći od svog prethodnika
 
-----------------------------------------------------------

15. Koliko puta brže će se izvesti binarna pretraga na sortiranom nizu
od milion elemenata u odnosu na linearnu pretragu (u najgorem slučaju)?
a) 2
b) 50
c) 1000
d) 50000
e) 500000
f) 1000000
 
-----------------------------------------------------------

16. Da bi se mogla sprovesti optimizacija binarnom pretragom
(binarna pretraga po rešenju) i mogla pronaći najveća vrednost $x$
za koju je zadovoljen neki uslov $P$ potrebno je dokazati
a) da je niz sortiran opadajuće
b) da je niz sortiran rastuće
c) ako neka vrednost $x$ zadovoljava uslov P, onda taj uslov
zadovoljavaju i sve vrednosti manje od $x$
d) ako neka vrednost x ne zadovoljava uslov P, onda taj uslov
ne zadovoljava nijedna vrednost veća od $x$
 
-----------------------------------------------------------

17. Ako tokom binarne pretrage važi da vrednosti strogo manje od $l$
ne zadovoljavaju uslov $P$, da vrednosti iz intervala [l,d] imaju
nepoznat status, a da vrednosti strogo veće od $d$ zadovoljavaju uslov $P$,
koju vrednost možemo vratiti kao poziciju prvog elementa koji zadovoljava uslov $P$?
a) l
b) d
c) l+1
d) l-1
e) d+1
f) d-1