АСП2/К3 2020

Postavka na stranici predmeta.

1. zadatak

Postavka

Upotrebom tehnike objedinjenog ulančavanja implementirati funkciju DELETE_ENTRY koja treba da iz heš tabele (table) fizički ukloni prosledjeni^[sic] ključ (key) ukoliko on postoji. Tabela ima n ulaza, a funkcija treba da ažurira i index free tako da ne postoji slobodna lokacija sa većim indeksom.

Rešenje

Prvo tražimo lokaciju ključa za uklanjanje a zatim, ako je ključ pronađen, prevezujemo prethodnu posećenu zauzetu lokaciju, brišemo ključ iz tabele i ažuriramo pokazivač free.

DELETE ENTRY(table, n, key, free)
prev_adr = -1
adr = h(key)
while (adr ≠ -1) and (key(table[adr]) ≠ key) do
    prev_adr = adr
    adr = next(table[adr])
end_while
if adr ≠ -1 then
    if prev_adr ≠ -1 then
        next(table[prev_adr]) = next(table[adr])
    end_if
    key(table[adr]) = empty
    next(table[adr]) = -1
    if adr > free then
        free = adr
    end_if
end_if

Po novijoj verziji knjige profesora Mila V. Tomaševića pri objedinjenom ulančavanju bi trebalo da se na oslobođeno mesto prebacuje ključ sa kraja liste u kojoj se nalazio, i takav pristup se nalazi ispod:

DELETE ENTRY(table, n, key, free)
prev_adr = -1
adr = h(key)
while (adr ≠ -1) and (key(table[adr]) ≠ key) do
    prev_adr = adr
    adr = next(table[adr])
end_while
if adr ≠ -1 then
    if next(table[adr]) = -1 then
        if prev_adr ≠ -1 then
            next(table[prev_adr]) = -1
        end_if
        key(table[adr]) = empty
        next(table[adr]) = -1
        if adr > free then
            free = adr
        end_if
    else
        prev_adr = -1
        last_adr = adr
        while next(table[last_adr]) ≠ -1 do
            prev_adr = last_adr
            last_adr = next(table[last_adr])
        end_while
        next(table[prev_adr]) = -1
        key(table[adr]) = key(table[last_adr])
        key(table[last_adr]) = empty
        if last_adr > free then
            free = last_adr
        end_if
    end_if
end_if

2. zadatak

Postavka

Radix exchange algoritam.

1. Prikazati prve tri iteracije algoritma radix exchange nad sledećom sekvencom 5-bitnih neoznačenih celobrojnih ključeva:
2. Da li je algoritam stabilan? Obrazložiti ukratko.

Rešenje

Prvo odvajamo ključeve na bitove:

• 4 — 00100
• 7 — 00111
• 9 — 01001
• 10 — 01010
• 15 — 01111
• 16 — 10000
• 18 — 10010
• 23 — 10111

Prve tri iteracije radix exchange algoritma nad sekvencom

0	1	2	3	4	5	6	7
7	18	23	4	10	16	9	15
7	15	9	4	10	16	23	18
7	4	9	15	10	16	23	18
7	4	9	10	15	16	18	23

Ovaj algoritam nije stabilan jer funkcioniše po sličnom principu kao quicksort zamena. Stabilnost algoritma podrazumeva da se jednaki elementi sortiraju po indeksu u originalnom poretku, a ovde se može desiti da se prilikom zamene element koji je bio prvi među jednakima prebaci na kraj.

3. zadatak

Postavka

Posmatra se rastuće uređeni binarni hip, koji je dat u vidu niza ključeva heap. Napisati u pseudokodu efikasnu iterativnu funkciju koja menja vrednost zadatog ključa key, na zadatu vrednost new_key. Poznato je da hip ima n elemenata.

Rešenje

Algoritam prvo pronalazi ključ u hipu iterativnim obilaskom niza (ne postoji efikasnija tehnika od te jer hip ne daje nikakve garancije da će se dati element naći u levom ili desnom podstablu).

HEAP CHANGE(heap, n, key, new_key)
pos = -1
for i = 1 to n do
    if heap[i] = key then
        pos = i
        break
    end_if
end_for
if pos = -1 then
    ERROR(Ključ nije u hipu)
end_if
heap[pos] = new_key
parent_pos = pos / 2
child_pos_1 = pos * 2
child_pos_2 = pos * 2 + 1
if (parent_pos > 0) and (heap[parent_pos] > heap[pos]) then
    while (parent_pos > 0) and (heap[parent_pos] > heap[pos]) do
        heap[pos] = heap[parent_pos]
        heap[parent_pos] = new_key
        pos = parent_pos
        parent_pos = pos / 2
    end_while
else if ((child_pos_1 ≤ n) and (heap[child_pos_1] < heap[pos])) or ((child_pos_2 ≤ n) and (heap[child_pos_2] < heap[pos])) then
    while ((child_pos_1 ≤ n) and (heap[child_pos_1] < heap[pos])) or ((child_pos_2 ≤ n) and (heap[child_pos_2] < heap[pos])) do
        if (child_pos_1 ≤ n) and (heap[child_pos_2] < heap[child_pos_1] < heap[pos]) then
            heap[pos] = heap[child_pos_1]
            heap[child_pos_1] = new_key
            pos = child_pos_1
        else
            heap[pos] = heap[child_pos_2]
            heap[child_pos_2] = new_key
            pos = child_pos_2
        end_if
        child_pos_1 = pos * 2
        child_pos_2 = pos * 2 + 1
    end_while
end_if

4. 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 tehnika kvadratnog pretraživanja. U tabelu se umeću redom ključevi 38, 31, 10, 56, 21. Odrediti prosečan broj pristupa prilikom uspešnog i neuspešnog traženja i verovatnoću popunjavanja praznih ulaza, pod pretpostavkom da su svi ključevi jednako verovatni.

Rešenje

Ovaj zadatak je rešen na prezentaciji iz heširanja na stranici predmeta.

Popunjena heš tabela

0	10
1	56
2	21
3	38
4	31
5
6

Ispitni nizovi za kvadratno pretraživanje

i / K % 7	0	1	2	3	4	5	6
0	0	1	2	3	4	5	6
1	1	2	3	4	5	6	0
2	4	5	6	0	1	2	3
3	2	3	4	5	6	0	1
4	2	3	4	5	6	0	1
5	4	5	6	0	1	2	3
6	1	2	3	4	5	6	0

• Umetanje:
  • 38 % 7 = 3 (1 pristup)
  • 31 % 7 = 3 (2 pristupa)
    • (3 + 1*1) % 7 = 4
  • 10 % 7 = 3 (3 pristupa)
    • (3 + 1*1) % 7 = 4
    • (3 + 2*2) % 7 = 0
  • 56 % 7 = 0 (2 pristupa)
    • (0 + 1*1) % 7 = 1
  • 21 % 7 = 0 (4 pristupa)
    • (0 + 1*1) % 7 = 1
    • (0 + 2*2) % 7 = 4
    • (0 + 3*3) % 7 = 2
• Prosečan broj uspešnih pristupa: $P_u = \frac{1 + 2 + 3 + 2 + 4}{5} = \frac{12}{5} = 2.4$
• 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:
  • 5: $\frac{0 + 1 + 0 + 1 + 1 + 1 + 0}{7} = \frac{4}{7}$
  • 6: $\frac{0 + 0 + 1 + 0 + 0 + 0 + 1}{7} = \frac{2}{7}$

5. zadatak

Postavka

Prikazati izgled binomnog hipa nakon svake izmene, ukoliko se prvo obriše minimum, pa se nakon toga dodaju ključevi 2, 32, 4 i nakon toga ponovo obriše minimum.

Rešenje

U originalnoj postavci je umesto broja 19 stajao broj 9. Hip tada ne bi bio validan, tako da se u rešenju smatra da je tu broj 19.

Ispod je dato konačno rešenje zadatka, a koraci se mogu simulirati u simulatoru binomnih hipova, redom umetanjem ključeva 19, 41, 15, 29, 17, 25, 3, 10 i 14, pa zatim izvršavati zadate operacije.

• 

  Ispravljena postavka zadatka

• 

  Konačni izgleda hipa

6. zadatak

Postavka

Data je sekvenca ključeva: 159, 57, 103, 7, 74, 95, 8, 101, 179, 45, 303, 42, 219. Prikazati rad shell sort algoritma po koracima. Navesti korišćenu sekvencu inkremenata i obrazložiti izbor.

Rešenje

Data sekvenca ima 13 ključeva, i ono što inkrementi u shell sort algoritmu treba idealno da postignu jeste mešanje ključeva između "grupa", te se zato biraju uzajamno prosti inkrementi 7, 5, 3, 2 i 1.

Koraci shell sort algoritma

Inkrement	0	1	2	3	4	5	6	7	8	9	10	11	12
Početak	159	57	103	7	74	95	8	101	179	45	303	42	219
7	101	57	45	7	42	95	8	159	179	103	303	74	219
5	95	8	45	7	42	101	57	159	179	103	303	74	219
3	7	8	45	57	42	101	95	159	74	103	303	179	219
3	7	8	45	57	42	74	95	159	101	103	303	179	219
2	7	8	42	57	45	74	95	103	101	159	219	179	303
1	7	8	42	45	57	74	95	101	103	159	179	219	303

7. zadatak

Postavka

Neka se kod spoljašnjeg heširanja koristi tehnika dinamičkog heširanja. Heš tabela se sastoji od 4 baketa kapaciteta b = 2. Za heš funkciju se koriste viši bitovi heš funkcije K mod 8. Neka se u tabelu umeću redom ključevi 37, 33, 15, 24, 37, 46, 41 i 54. Ilustrovati stanje tabele nakon svakog razrešenja kolizije pri umetanju i u završnom stanju.

Rešenje

[  00  |  01  |  10  |  11  ]
                  |
               [37   ]

[  00  |  01  |  10  |  11  ]
   |              |
[33   ]        [37   ]

[  00  |  01  |  10  |  11  ]
   |              |      |
[33   ]        [37   ][15   ]

[  00  |  01  |  10  |  11  ]
   |              |      |
[33 24]        [37   ][15   ]

[  00  |  01  |  10  |  11  ]
   |              |      |
[33 24]        [37 37][15   ]

[  00  |  01  |  10  |  11  ]
   |              |      |
[33 24]        [37 37][15 46]

    [  00  |  01  |  10  |  11  ]
       |             |      |
     /   \           |      |
   |      |          |      |
[24   ][33 41]    [37 37][15 46]
000... 001...

    [  00  |  01  |  10  |  11  ]
       |             |      |
     /   \         /      /   \
   |      |      |      |      |
[24   ][33 41][37 37][46 54][15   ]
000... 001...        110... 111...

8. zadatak

Postavka

Neka je dat niz celih brojeva arr dužine n čiji se elementi nalaze u opsegu od 0 do k-1. Napisati u pseudokodu iterativnu funkciju koja pronalazi element koji se najčešće pojavljuje u nizu. Ukoliko ima više takvih elemenata dovoljno je pronaći jedan. Funkcija treba da ima što je moguće bolju vremensku i prostornu složenost. Dozvoljeno je modifikovati polazni niz.

Rešenje

Ovde su dva rešenja pogodna:

• Pošto nam je dat opseg vrednosti u nizu, može se koristiti counting sort kako bi se u vremenskoj složenosti $\mathcal{O}(n)$ i prostornoj složenosti $\mathcal{O}(k)$ pronašla vrednost koja se najviše ponavlja
• Pošto nam je dato da se polazni niz može modifikovati, može se koristiti heapsort kako bi se u vremenskoj složenosti $\mathcal{O}(n \log n)$ i prostornoj složenosti $\mathcal{O}(1)$ pronašla tražena vrednost

Ispod je dato rešenje pomoću counting sort.

FIND MAX REP(arr, n, k)
rep_max = 0
rep_elem = 0
for i = 0 to k-1 do
    c[i] = 0
end_for
for i = 1 to n do
    c[arr[i]] = c[arr[i]] + 1
    if c[arr[i]] > rep_max then
        rep_max = c[arr[i]]
        rep_elem = arr[i]
    end_if
end_for
return rep_elem