АСП2/К3 2017

Treći kolokvijum 2017. godine održan je 20. januara. Postavka zadataka je dostupna sa stranice predmeta.

1. zadatak

Postavka

Kako izgleda niz sa slike nakon prvih pet iteracija shakersort algoritma?

Rešenje

Niz nakon pet iteracija shakersort algoritma

12	3	34	83	21	95	34	1	18	20	83	17	44	39
3	12	34	21	83	34	1	18	20	83	17	44	39	95
1	3	12	34	21	83	34	17	18	20	83	39	44	95
1	3	12	21	34	34	17	18	20	83	39	44	83	95
1	3	12	17	21	34	34	18	20	39	83	44	83	95
1	3	12	17	21	34	18	20	34	39	44	83	83	95

2. zadatak

Postavka

Data je heš tabela sa 10 ulaza. U tabelu se unose ključevi koje se mogu sastojati od velikih i malih slova. Primarna heš funkcija je H₁(K) = (1 + len(K)) mod 10, gde len(K) vraća broj slova u prosleđenom ključu K. Vremenska lokalnost je veoma izražena, jer se nakon umetanja svakog ključa javlja veliki broj pretraživanja na taj ključ pre nego što se umetne sledeći. Kolizije se razrešavaju nestandardnom primenom dvostrukog heširanja kod koga je sekundarna funkcija H₂(K) = 3 + up_case_cnt(K), gde up_case_cnt(K) vraća ukupan broj velikih slova u ključu K.

1. Predložiti modifikaciju načina za razrešavanje kolizije tako da se minimizuje vreme uspešnog pretraživanja u datim uslovima.
2. Primenom predloženog rešenja u donju tabelu umetnuti sledeće ključeve:

   ČoKoLaDa, PalAčINka, kafA, TORtA, RoLaT, SLadoled, koLAČ

   Prikazati finalno stanje heš tabele i celokupan postupak primenom tehnike opisane u rešenju pod a).

Rešenje

1. Prilikom razrešavanja kolizije, postojeće ključeve možemo pomeriti da budu niže u ispitnom nizu duplim heširanjem a novoumetnuti ključ staviti na njegov početak kako bi se sa što manjim brojem kolizija dolazilo do najskorije umetnutih ključeva.
2. Umetanje u tabelu ide ovako:
   1. ČoKoLaDa se umeće na mesto 9
   2. PalAčINka se umeće na mesto 0
   3. kafA se umeće na mesto 5
   4. TORtA se umeće na mesto 6
   5. RoLaT se umeće na mesto 6, TORtA se pomera na mesto 3
   6. SLadoled se umeće na mesto 9, ČoKoLaDa se pomera na mesto 6, RoLaT se pomera na mesto 2
   7. koLAČ se umeće na mesto 6, ČoKoLaDa se pomera na mesto 3, TORtA se pomera na mesto 0, PalAčINka se pomera na mesto 7

Konačni izgled heš tabele nakon umetanja

0	TORtA
1
2	RoLaT
3	ČoKoLaDa
4
5	kafA
6	koLAČ
7	PalAčINka
8
9	SLadoled

3. zadatak

Postavka

Napisati iterativnu implementaciju quicksort algoritma. U telu funkcije QUICKSORT koja će predstavljati ovu implementaciju, nakon izbora pivota, pozivati funkciju PARTITION koja vraća konačnu poziciju pivota u nizu. Algoritam realizovati što efikasnije, a za pivot uzeti element niza koji je srednji po vrednosti u izboru između elemenata sa prve tri pozicije u particiji.

Rešenje

Pošto se pominje velika efikasnost, bitno je da na stek guramo veće particije a direktno obilazimo manje kako bi dubina steka bila što manja.

QUICKSORT(arr, n)
STACK_INIT(S_down)
STACK_INIT(S_up)
down = 1
up = n
from_stack = false
while (not STACK_EMPTY(S_down)) or (not from_stack) do
    if from_stack then
        down = POP(S_down)
        up = POP(S_up)
    end_if
    if (up - down = 0) or (up - down = 1) then
        if (up - down = 1) and (arr[up] < arr[down]) then
            arr[up] ↔ arr[down]
        end_if
        from_stack = true
        continue
    end_if
    first = arr[down]
    second = arr[down+1]
    third = arr[down+2]
    if (first ≤ second ≤ third) or (third ≤ second ≤ first) then
        pivot = 2
    else if (second ≤ first ≤ third) or (third ≤ first ≤ second) then
        pivot = 1
    else
        pivot = 3
    end_if
    pivot_pos = PARTITION(arr, down, up, pivot)
    lower_down = down
    lower_up = pivot_pos-1
    higher_down = pivot_pos+1
    higher_up = up
    if (lower_up - lower_down < 1) and (higher_up - higher_down < 1) then
        from_stack = true
    else if lower_up - lower_down < higher_up - higher_down then
        up = lower_up
        down = lower_down
        from_stack = false
        PUSH(S_down, higher_down)
        PUSH(S_up, higher_up)
    else
        up = higher_up
        down = higher_down
        from_stack = false
        PUSH(S_down, lower_down)
        PUSH(S_up, lower_up)
    end_if
end_while

Pošto je rečeno da se izbor pivota radi u QUICKSORT, pretpostavićemo da se taj pivot zatim prosleđuje PARTITION kao parametar.

PARTITION(arr, down, up, pivot_pos)
i = down
j = up
pivot = arr[pivot_pos]
while i < j do
    while (arr[i] ≤ pivot) and (i < j) do
        i = i + 1
    end_while
    while arr[j] > pivot do
        j = j - 1
    end_while
    if i < j then
        if j == pivot_pos then
            pivot_pos = i
        end_if
        arr[i] ↔ arr[j]
    end_while
end_while
arr[pivot_pos] ↔ arr[j]
return j

4. zadatak

Postavka

Napisati u pseudokodu funkciju za dekrementiranje ključa koji se nalazi u binarnom nerastućem (max) hipu. Smatrati da je hip smešten u nizu čiji indeksi počinju od 0. Funkcija kao svoj parametar dobija indeks ključa u nizu koga treba dekrementirati.

Rešenje

HEAP KEY DEC(i)
arr[i] = arr[i]-1
left = 2 * i + 1
right = 2 * i + 2
while ((left ≤ n) and (arr[left] > arr[i])) or ((right ≤ n) and (arr[right] > arr[i])) do
    if right ≤ n then
        if arr[right] > arr[left] then
            high = right
        else
            high = left
        end_if
    else
        high = left
    end_if
    arr[i] ↔ arr[high]
    i = high
    left = 2 * i + 1
    right = 2 * i + 2
end_while

5. zadatak

Postavka

Podaci se smeštaju u heš tabelu sa 7 ulaza primenom heš funkcije h_p(K) = K mod 7. Za razrešavanje kolizija se koristi metoda dvostrukog heširanja sa sekundarnom heš funkcijom h_s(K) = 4 + K mod 2. Obrazložiti na koji način u ovom slučaju može doći do sekundarnog grupisanja i navesti sekvencu od tri ključa koja proizvodi ovaj efekat u konkretnom slučaju. Navedene ključeve uneti u tabelu.

Rešenje

U ovom slučaju može doći do sekundarnog grupisanja kada uneti ključevi daju isti ostatak pri deljenju sa 7 i pri deljenju sa 2. Takvi su recimo ključevi 0, 14 i 28.

Tabela sa unetim ključevima

0	0
1
2
3
4	14
5
6
7
8	28

6. zadatak

Postavka

Fibonačijev hip

1. Koja je razlika između dodavanja u binomni hip i Fibonačijev hip? Objasniti kratko i precizno, u jednoj do dve rečenice.
2. U prazan Fibonačijev hip dodaju se elementi 10, 5, 17, 3, 12, 11, 1, potom se briše element sa vrednošću 1, nakon čega se dodaju elementi 7 i 2. Nacrtati izgled hipa nakon prvih sedam umetanja i nakon svake naredne izmene hipa.

Rešenje

1. Pri dodavanju u Fibonačijev hip uneti čvor se samo ulančava, a grupisanje slično binomnom hipu se dešava tek kod izbacivanja najmanjeg elementa.
2. Ispod su dati izgledi hipa nakon date četiri operacije.

• 

  Izgled hipa nakon umetanja 10, 5, 17, 3, 12, 11, 1.

• 

  Izgled hipa nakon brisanja 1.

• 

  Izgled hipa nakon umetanja 7.

• 

  Izgled hipa nakon umetanja 2.

7. zadatak

Postavka

Podaci se smeštaju u heš tabelu sa n ulaza primenom heš funkcije h(K) = K mod n. Za razrešavanje kolizija se koristi metoda kvadratnog pretraživanja, ali nije dozvoljeno koristiti operaciju množenja (kvadriranja). Predložiti metod brisanja i napisati pseudokodove operacija brisanja i umetanja.

Rešenje

Možemo primetiti da $2^2 - 1^2 = 3, 3^2 - 2^2 = 5, 4^2 - 3^2 = 7, ...$ što znači da umesto kvadriranja možemo da radimo samo sabiranje sa sledećim neparnim brojem.

DELETE(H, key)
i = init = H(key)
step = 3
while (T[i] ≠ key) and (T[i] ≠ empty) do
    if (step ≠ 3) and (i = init) then
        return
    end_if
    i = i + step
    step = step + 2
end_while
if T[i] ≠ empty then
    T[i] = deleted
end_if

INSERT(H, key)
i = init = H(key)
step = 3
while (T[i] ≠ empty) and (T[i] ≠ deleted) do
    if (step ≠ 3) and (i = init) then
        ERROR(Tabela puna)
    end_if
    i = i + step
    step = step + 2
end_while
T[i] = key

8. zadatak

Postavka

Objasniti kako se može modelirati ponašanje algoritama sortiranja poređenjem. Za dati model izvesti teorijsku granicu složenosti u najgorem slučaju.

Rešenje

Ponašanje algoritma se može modelirati stablom odlučivanja. Svako odlučivanje se modeluje unutrašnjim čvorom a svaki ishod listom, tako da složenost u najgorem slučaju dobijamo kao visinu tog stabla. Pošto je broj ishoda ovakvog stabla odlučivanja jednak $n!$, a najveći broj listova u stablu visine $h$ jednak $2^h$, možemo da izjednačimo $n! = 2^h$. Kad logaritmujemo obe strane jednačine i primenimo Stirlingovu aproksimaciju ($n! > \left(\frac{n}{e}\right)^n$) dobijamo $h = \log(n!) > n \log\left(\frac{n}{e}\right) > n \log n - n \log e = O(n \log n)$.