АСП2/К3 2018

1. zadatak

Postavka

Prikazati izgled binarnog hipa nakon uklanjanja minimalnog ključa i nakon umetanja ključeva 9 i 30.

         5
       /   \
     10      7
    /  \    / \
   47  32  12 31
  /
54

Rešenje

Nakon uklanjanja minimalnog ključa:

      7
    /   \
  10      12
 /  \    /  \
47  32  54  31

Nakon umetanja ključeva 9 i 30:

       7
     /   \
    9     12
   / \   /  \
  10 32 54  31
 /  \
47  30

2. zadatak

Postavka

Napisati iterativnu implementaciju sledećeg algoritma heširanja. Za heširanje se koriste dve heš funkcije, h₁(K) i h₂(K), dok se za razrešavanje kolizija koristi sekundarna heš funkcija g(k). Nad ključem K koji se ubacuje u tabelu se primenjuju i funkcija h₁(K) i h₂(K), a kao ulaz se koristi rezultat funkcije za koju se dobije manje kolizija. U slučaju jednakog broja kolizija, koristi se funkcija h₁(K). Potrebno je realizovati operacije umetanja i pretrage.

Rešenje

Prilikom umetanja tražimo prvu poziciju na kojoj je prazno mesto, prvo jednom a zatim i drugom heš funkcijom. Ako se desi da se vratimo na početnu poziciju, to znači da je tabela puna i ključ se ne može umetnuti.

INSERT(table, K)
adr1 = adr1_init = h1(K)
adr2 = adr2_init = h2(K)
repeat
    if table[adr1] = empty then
        table[adr1] = K
        return
    else
        adr1 = adr1 + g(K)
    end_if
    if table[adr2] = empty then
        table[adr2] = K
        return
    else
        adr2 = adr2 + g(K)
    end_if
until (adr1 = adr1_init) or (adr2 = adr2_init)
ERROR(Tabela je puna)

Pretraga je slična umetanju, s tim što ako naiđemo na neprazno polje prvo proveravamo da li to polje sadrži traženi ključ i nastavljamo pretragu ako ne sadrži. Pretraga se takođe završava ako su obe pretrage došle do praznog polja.

SEARCH(table, K)
adr1 = adr1_init = h1(K)
adr2 = adr2_init = h2(K)
repeat
    if table[adr1] = K then
        return true
    else if table[adr1] ≠ empty then
        adr1 = adr1 + g(K)
    end_if
    if table[adr2] = K then
        return true
    else if table[adr2] ≠ empty then
        adr2 = adr2 + g(K)
    end_if
until (adr1 = adr1_init) or (adr2 = adr2_init) or ((table[adr1] = empty) and (table[adr2] = empty))
return false

3. zadatak

Postavka

Data je sekvenca ključeva: 169, 84, 99, 6, 61, 84, 9, 96, 158, 42, 495, 46, 223. Prikazati rad shell sort algoritma po koracima. Navesti korišćenu sekvencu inkremenata i obrazložiti izbor.

Rešenje

Inkrementi su izabrani kao u rešenju šestog zadatka sa trećeg kolokvijuma 2020. godine.

Inkrement	0	1	2	3	4	5	6	7	8	9	10	11	12
Početak	169	84	99	6	61	84	9	96	158	42	495	46	223
7	96	84	42	6	46	84	9	169	158	99	495	61	223
5	84	9	42	6	46	96	84	169	158	99	495	84	223
3	6	9	42	61	46	96	84	169	84	99	495	158	223
3	6	9	42	61	46	84	84	169	96	99	495	158	223
2	6	9	42	61	46	84	84	99	96	158	223	169	495
1	6	9	42	46	61	84	84	96	99	158	169	223	495

4. zadatak

Postavka

Priloženi pseudokod prikazuje jednu varijantu bubble sort algoritma za sortiranje podataka. Objasniti glavne nedostatke priloženog algoritma i napisati u pseudokodu alternativnu implementaciju ovog algoritma koja te nedostatke ispravlja.

for i:=1 to n-1 do
    for j:=n-1 downto 1 do
        if arr[j]>arr[j+1] then
            b:=arr[j]; arr[j]:=arr[j+1]; arr[j+1]:=b;
        end_if
     end_for
end_for

Rešenje

Kod ovog algoritma jeste najveći problem to što n-1 puta radi iteraciju kroz niz, kada je to potrebno raditi samo dok se ne desi da nije bilo nijedne zamene u unutrašnjoj petlji. Drugi problem jeste nepotreban prolazak od kraja do početka niza, kada je prolazak od početka do kraja potencijalno efikasniji zbog keš memorije. Takođe, nije potrebno prolaziti kroz sortirani deo prilikom zamene elemenata.

BUBBLE SORT REVISITED(arr, n)
i = 1
repeat
    broj_zamena = 0
    for j = 1 to n-i do
        if arr[j] > arr[j+1] then
            arr[j] ↔ arr[j+1]
            broj_zamena = broj_zamena + 1
        end_if
    end_for
    i = i + 1
until broj_zamena = 0

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 3. Odrediti prosečan broj pristupa prilikom neuspešnog traženja i verovatnoću popunjavanja praznih ulaza, pod pretpostavkom da su svi ključevi jednako verovatni.

Tabela iz postavke zadatka

0	14
1
2	11
3	24
4	18
5
6	13

Rešenje

Ispitni nizovi

0	1	2
0	0	0
4	5	6
1	3	5
5	1	4
2	6	3
6	4	2
3	2	1

• Prosečan broj neuspešnih pristupa: $P_{nu} = 1 + \frac{5}{7} + \frac{5 \cdot 4}{7 \cdot 6} + \frac{5 \cdot 4 \cdot 3}{7 \cdot 6 \cdot 5} + \frac{5 \cdot 4 \cdot 3 \cdot 2}{7 \cdot 6 \cdot 5 \cdot 4} + \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3} =$

  $= 1 + \frac{5}{7} + \frac{10}{21} + \frac{2}{7} + \frac{1}{7} + \frac{1}{21} = \frac{8}{3} \approx 2.67$

• Verovatnoća popunjavanja:
  • 1: $\frac{1}{3} \left(\frac{6}{7} + \frac{2}{7} + \frac{4}{7}\right) = \frac{4}{7}$
  • 5: $\frac{1}{3} \left(\frac{1}{7} + \frac{5}{7} + \frac{3}{7}\right) = \frac{3}{7}$

6. zadatak

Postavka

Napisati u pseudokodu funkciju za uklanjanje minimalnog ključa u binomnom hipu i njegovu naknadnu reorganizaciju. Nije potrebno sprovesti potencijalno spajanje stabala nakon uklanjanja čvora sa minimalnim ključem. Binomni hip predstavljen pomoću objekta klase BinHeap koja sadrži ulančanu listu objekata BinTree koji predstavljaju pojedinačna binomna stabla. Lista je uređena rastuće po stepenu stabla. Binomno stablo se sastoji od čvorova predstavljenih objektima klase BinNode. Funkcija kao argument prima objekat klase BinHeap. U nastavku je dat spisak metoda koje su na raspolaganju, njihove povratne vrednosti i klase objekata za koje ih treba pozvati.

Metoda	Povratna vrednost	Objekat klase
getFirst	pokazivač na početak liste šume binomnih stabala	BinHeap
findMin	pokazivač na binomno stablo u čijem korenu je minimalni ključ	BinHeap
getOrder	red stabla	BinTree
setOrder	nema	BinTree
getRoot	pokazivač na koren binomnog stabla	BinTree
getNumOfChildren	broj potomaka čvora binomnog stabla	BinNode
getChildAtPos(index)	pokazivač na čvor koji je potomak objekta BinNode na poziciji index	BinNode

Rešenje

Sledeće pretpostavke su usvojene pri implementaciji:

• getFirst vraća promenljivu referencu na lvrednost do početka ulančane liste, kako bismo mogli da ažuriramo taj početak
• getChildAtPos isto vraća promenljivu referencu na lvrednost. Ovo je kako bismo decu trenutnog čvora mogli da postavimo na nil, kako ne bi bila uništena prilikom dealokacije stabla (pretpostavljamo da postoji funkcija FREETREE koja to radi, slično FREENODE)
• Postoji funkcija GETTREE koja samo alocira stablo i kao koren postavlja svoj prvi argument
• Ulančana lista je jednostruko ulančana, pa naknadno moramo dohvatati elemente liste koje sadrže stablo sa minimalnim korenom nakon pozivanja findMin
• Ulančana lista u hipu sadrži polje next koje pokazuje do sledećeg čvora ulančane liste i polje value koje pokazuje na BinTree objekat, i sve operacije kao što su se koristile na ASP1 su podržane

REMOVE MIN KEY(binheap)
first_node = binheap.getFirst()
if first_node = nil then
    return
end_if
min_tree = binheap.getMin()
prev_node = nil
curr_node = first_node
while value(curr_node) ≠ min_tree do
    prev_node = curr_node
    curr_node = next(curr_node)
end_while
next(prev_node) = next(curr_node)
root = min_tree.getRoot()
for i = 1 to root.getNumOfChildren() do
    child = root.getChildAtPos(i)
    tree = GETTREE(child)
    tree.setOrder(child.getNumOfChildren())
    INSERT_TREE(binheap, tree)
    root.getChildAtPos(i) = nil
end_for
FREETREE(min_tree)
FREENODE(curr_node)

INSERT TREE(binheap, bintree)
curr = binheap.getFirst()
prev = nil
while curr ≠ nil do
    if value(curr).getOrder() ≥ bintree.getOrder() then
        if prev = nil then
            binheap.getFirst() = GETNODE
            value(binheap.getFirst()) = bintree
            next(binheap.getFirst()) = curr
        else
            next(prev) = GETNODE
            value(next(prev)) = bintree
            next(next(prev)) = curr
        end_if
        return
    end_if
    prev = curr
    curr = next(curr)
end_while
next(prev) = GETNODE
value(next(prev)) = bintree
next(next(prev)) = nil

7. zadatak

Postavka

Podaci se smeštaju u heš tabelu sa 8 ulaza primenom heš funkcije po metodu deljenja. Za razrešavanje kolizija se koristi metoda slučajnog pretraživanja (c = 3). Prikazati proces razrešavanja kolizije i generisati ispitne nizove za ključeve 21 i 18. Objasniti da li kod ovog metoda u opštem slučaju dolazi do primarnog i sekundarnog grupisanja i zašto.

Rešenje

Pošto se koristi metoda slučajnog pretraživanja, moramo generisati slučajni niz za generisanje ispitnog niza:

    011 = 3
*2  110 = 6
*2 1100
-8  100
⊕3  111 = 7
*2 1110
-8  110
⊕3  101 = 5
*2 1010
-8  010
⊕3  001 = 1
*2  010 = 2
*2  100 = 4
*2 1000
-8  000
⊕3  011 ...

Ispitni nizovi za 21 i 18

21	18
5	2
0	5
3	0
4	1
2	7
6	3
7	4
1	6

Proces razrešavanja kolizije:

• 21 % 8 = 5
• Ako je ulaz 5 zauzet: (5 + 3) % 8 = 0
• Ako je ulaz 0 zauzet: (5 + 6) % 8 = 3
• itd.

U opštem slučaju neće doći do primarnog grupisanja jer je sekvenca ključeva u ispitnom nizu nasumična a ne linearna, ali će doći do sekundarnog grupisanja jer ispitni niz zavisi samo od matične adrese i rednog broja pokušaja.

8. zadatak

Postavka

Precizno objasniti kako se dolazi do složenosti algoritama za sortiranje a) kvadratnom selekcijom b) stablom selekcije i c) spajanjem. U kojem od ovih algoritama se razlikuju najbolji, srednji i najgori slučaj složenosti.