АСП2/К3 2019

Postavka sa stranice predmeta.

1. zadatak

Postavka

Upotrebom metode heširanja implementirati funkciju FIND_NUM_OF_PAIRS koja treba da pronađe ukupan broj parova celobrojnih vrednosti u zadatom nizu arr koji u sumi po modulu n daju vrednost k koja predstavlja parametar funkcije. Za realizaciju ove funkcije treba koristiti metodu odvojenog ulančavanja.

Rešenje

Ovde nema potrebe koristiti bilo kakvo ulančavanje jer je counting sort dovoljan da izbroji ključeve koji daju neku vrednost po modulu n a zatim izmnoži izbrojano. Na primer, za n = 7 i k = 1 na sumu se redom dodaju:

1. $\frac{C[0] \cdot C[1]}{2}$
2. $\frac{C[1] \cdot C[0]}{2}$
3. $\frac{C[2] \cdot C[6]}{2}$
4. $\frac{C[3] \cdot C[5]}{2}$
5. $\frac{C[4] \cdot (C[4] - 1)}{2}$
6. $\frac{C[5] \cdot C[3]}{2}$
7. $\frac{C[6] \cdot C[2]}{2}$

FIND NUM OF PAIRS(arr, n, k)
for i = 0 to n-1 do
    C[i] = nil
end_for
for i = 1 to LENGTH(arr) do
    adr = arr[i] mod n
    if C[adr] = nil then
        C[adr] = GETNODE
        value(C[adr]) = arr[i]
        next(C[adr]) = nil
    else
        curr = next(C[adr])
        prev = C[adr]
        while curr ≠ nil do
            prev = curr
            curr = next(curr)
        end_while
        next(prev) = GETNODE
        value(next(prev)) = arr[i]
        next(next(prev)) = nil
    end_if
end_for
count = 0
for i = 0 to n-1 do
    node_count_1 = 0
    curr = C[i]
    while curr ≠ nil do
        node_count_1 = node_count_1 + 1
        curr = next(curr)
    end_while
    node_count_2 = 0
    j = (k - i) mod n
    curr = C[j]
    while curr ≠ nil do
        node_count_2 = node_count_2 + 1
        curr = next(curr)
    end_while
    if i = j then
        count = count + node_count_1 * (node_count_1 - 1) / 2
    else
        count = count + node_count_1 * node_count_2 / 2
    end_if
end_for
for i = 0 to n-1 do
    curr = C[i]
    while curr ≠ nil do
        tmp = curr
        curr = next(curr)
        FREENODE(tmp)
    end_while
end_for
return count

2. zadatak

Postavka

Prikazati izgled binomnog hipa nakon svake izmene, ukoliko se umeću ključevi 19, 11, 25 i nakon toga obriše minimum.

Rešenje

Ispod je dato konačno rešenje zadatka, a koraci se mogu simulirati u simulatoru binomnih hipova, redom umetanjem ključeva 14, 27, 12, 23, 15, 22, 5, 9 i 17, pa zatim izvršavati zadate operacije.

• 

  Postavka zadatka

• 

  Konačni izgleda hipa

3. zadatak

Postavka

Data je sekvenca ključeva: 27, 25, 14, 34, 7, 1, 5, 193, 33, 41, 73, 124. Prikazati rad radix sort algoritma po koracima.

Rešenje

Prvi korak radix sort algoritma

0	1	2	3	4	5	6	7	8	9
	1		193	14	25		27
	41		33	34	5		7
			73	124

Dobijena sekvenca posle prvog koraka: 1, 41, 193, 33, 73, 14, 34, 124, 25, 5, 27, 7

Drugi korak radix sort algoritma

0	1	2	3	4	5	6	7	8	9
1	14	124	33	41			73		193
5		25	34
7		27

Dobijena sekvenca posle drugog koraka: 1, 5, 7, 14, 124, 25, 27, 33, 34, 41, 73, 193.

Treći korak neće biti prikazan jer će u suštini samo prve dve kolone biti jako popunjene, ali se na kraju dobija poredak: 1, 5, 7, 14, 25, 27, 33, 34, 41, 73, 124, 193.

4. zadatak

Postavka

Podaci se smeštaju u heš tabelu sa 10 ulaza primenom heš funkcije h_p(K) = K mod 10. Za razrešavanje kolizija se koristi metoda objedinjenog ulančavanja. Prikazati popunjavanje date tabele nakon umetanja svakog od sledećih ključeva: 37, 41, 18, 16, 12. Nakon svih umetanja, odrediti verovatnoću popunjavanja praznih ulaza, pod pretpostavkom da su svi ključevi jednako verovatni.

Tabela iz postavke zadatka

0	1	2	3	4	5	6	7	8	9
	11							21	29
-1	8	-1	-1	-1	-1	-1	-1	-1	-1
								free

Rešenje

Tabela nakon umetanja 37

0	1	2	3	4	5	6	7	8	9
	11						37	21	29
-1	8	-1	-1	-1	-1	-1	-1	-1	-1
								free

Tabela nakon umetanja 41

0	1	2	3	4	5	6	7	8	9
	11					41	37	21	29
-1	8	-1	-1	-1	-1	-1	-1	6	-1
						free

Tabela nakon umetanja 18

0	1	2	3	4	5	6	7	8	9
	11				18	41	37	21	29
-1	8	-1	-1	-1	-1	5	-1	6	-1
					free

Tabela nakon umetanja 16

0	1	2	3	4	5	6	7	8	9
	11			16	18	41	37	21	29
-1	8	-1	-1	-1	4	5	-1	6	-1
				free

Tabela nakon umetanja 12

0	1	2	3	4	5	6	7	8	9
	11	12		16	18	41	37	21	29
-1	8	-1	-1	-1	4	5	-1	6	-1
				free

Verovatnoća popunjavanja ulaza 0 je $\frac{1}{10}$, jer se on popunjava samo ukoliko se umeće broj kongruentan sa 0 po modulu 10. Verovatnoća popunjavanja ulaza 3 je, stoga, $\frac{9}{10}$, jer se on popunjava za bilo koji drugi moduo.

5. zadatak

Postavka

Priloženi pseudokod prikazuje algoritam za uređivanje špila karata u jednoj kartaškoj igri. U igri se koristi špil od po 8 karata za svaki od 4 znaka (ukupno 32). Algoritam treba da grupiše karte istog znaka, pri čemu karte istog znaka sortira prema rastućoj vrednosti. Uočiti i objasniti greške ili nedostatke priloženog algoritma i napisati u pseudokodu ispravnu implementaciju u skladu sa zahtevima. Polje val predstavlja vrednost karte, a polje sign njen znak.

for i = 2 to 32 do
  k = cards[i]
  j = i-1
  while(j>0 and cards[j].val>k.val) do
    cards[j+1] = cards[j]
    j = j-1
  end_while
  cards[j] = k
end_for
for i = 1 to 4 do
  c[i] = 0
end_for
for j = 1 to n do
  c[cards[j].sign] = c[cards[j].sign]+1
end_for
for i = 3 downto 1 do
  c[i] = c[i+1] - c[i]
end_for
for j = 1 to n do
  b[c[cards[j].sign]] = cards[j]
  c[cards[j].sign] = c[cards[j].sign]-1
end_for

Rešenje

Sledeće greške su uočene:

• Niz cards počinje od 1 a na kraju while petlje se postavlja cards[j] na vrednost k, s tim što je jedan od uslova petlje j > 0. Ovde se mora prepraviti na cards[j + 1].
• Counting sort implementacija za sortiranje po znaku ne radi.

SORT(cards)
for i = 2 to 32 do
    k = cards[i]
    j = i - 1
    while (j > 0) and (val(cards[j]) > val(k)) do
        cards[j + 1] = cards[j]
        j = j - 1
    end_while
    cards[j + 1] = k
end_for
for i = 1 to 4 do
    c[i] = 0
end_for
for j = 1 to n do
    c[sign(cards[j])] = c[sign(cards[j])] + 1
end_for
for i = 2 to 4 do
    c[i] = c[i-1] + c[i]
end_for
for j = n downto 1 do
    b[c[sign(cards[j])]] = cards[j]
    c[sign(cards[j])] = c[sign(cards[j])] - 1
end_for

6. zadatak

Postavka

Koristeći ideju quick sort algoritma, napisati u pseudokodu funkciju koja vraća k-ti najmanji element u zadatom nizu celih brojeva arr. Prilikom izbora pivot-a, koristiti medijanu od tri pogodno izabrane vrednosti.

Rešenje

QUICK SELECT(arr, k)
min = FIND(arr, 1, n, k)
return min
FIND(a, low, high, k)
j = PARTITION(a, low, high)
i = low + k - 1
if i = j then
    return a[i]
end_if
if j > i then
    return FIND(a, low, j - 1, k)
else
    return FIND(a, j + 1, high, k - j)
end_if
PARTITION(a, down, up)
i = down
j = up
pivot_pos = MEDIAN(a[i], i, a[j], j, a[(i + j) / 2], (i + j) / 2)
pivot = a[pivot_pos]
while i < j do
    while (a[i] ≤ pivot) and (i < j) do
        i = i + 1
    end_while
    while a[j] > pivot do
        j = j - 1
    end_while
    if i < j then
        if j == pivot_pos then
            pivot_pos = i
        end_if
        a[i] ↔ a[j]
    end_if
end_while
a[pivot_pos] = a[j]
a[j] = pivot
return j
MEDIAN(a, pos_a, b, pos_b, c, pos_c)
if (a > b) xor (a > c) then
    return pos_a
else if (b < a) xor (b < c) then
    return pos_b
else
    return pos_c
end_if

7. zadatak

Postavka

Podaci se smeštaju u heš tabelu sa 9 ulaza primenom heš funkcije hp(K)=K mod 9. Za razrešavanje kolizija se koristi metoda linearnog pretraživanja sa korakom 2. Definisati pojam primarnog i sekundarnog grupisanja, a zatim na primeru delimično popunjene tabele sa slike, ilustrovati jedan scenario umetanja kod kojeg se dešava primarno grupisanje i jedan scenario umetanja kod kojeg se dešava sekundarno grupisanje.

Tabela iz postavke zadatka

0	27
1
2	11
3
4
5	23
6
7
8	8

Rešenje

Sekundarno grupisanje je kada heš funkcija za dva različita ključa vraća istu matičnu adresu, pa su im i ispitni nizovi jednaki. Kada umetnemo ključ 18, dobijamo sekundarno grupisanje:

• 18 % 9 = 0 (ovde se desilo sekundarno grupisanje, jer ključevi 27 i 18 imaju istu matičnu adresu 0)
  • (0 + 2) % 9 = 2 (ovde se desilo primarno grupisanje, jer se ispitni niz po modulu 0 i ispitni niz po modulu 2 ovde preklapaju)
  • (2 + 2) % 9 = 4

Tabela nakon umetanja ključa 18

0	27
1
2	11
3
4	18
5	23
6
7
8	8

Primarno grupisanje je kada se dva ispitna niza od različitih matičnih adresa preklope. Ta pojava se takođe može ilustrovati na primeru umetanja ključa 20:

• 20 % 9 = 2 (ovde se desilo sekundarno grupisanje, jer ključevi 11 i 20 imaju istu matičnu adresu 2)
  • (2 + 2) % 9 = 4 (ovde se desilo primarno grupisanje, jer se ispitni nizovi po modulu 2 i po modulu 0 ponovo preklapaju)
  • (4 + 2) % 9 = 6

Tabela nakon umetanja ključa 20

0	27
1
2	11
3
4	18
5	23
6	20
7
8	8

8. zadatak

Postavka

Neka se kod spoljašnjeg heširanja koristi heš tabela sa 4 baketa, koji imaju kapacitet b = 3. Za heš funkciju se koristi metod deljenja K mod 4, a za razrešavanje kolizije linearno pretraživanje. Neka se pri brisanju koristi metod selektivnog pomeranja (analogno kao kod unutrašnjeg heširanja). U tabelu treba umetnuti ključeve 60, 18, 23, 50, 47, 34, 82, 14, 67 i 38, a zatim brisati ključeve 50, 47, 23 i 34. Prikazati izgled tabele nakon svakog razrešenja kolizije pri umetanju, kao nakon svakog brisanja.

Rešenje

Konačan izgled heš tabele je:

60						14	18	82	38	67