АСП1/Јун 2020

Zadaci

Prvi kolokvijum

1. zadatak

Postavka

Data je ulančana lista kod koje svaki element ima određeni informacioni sadržaj, pokazivač na sledeći element u listi, kao i pokazivač na neki proizvoljan element liste. Napisati u pseudokodu funkciju DEEP_COPY koja prihvata pokazivač na prvi element liste i pravi kopiju liste sa istim načinom i poretkom povezivanja kao u polaznoj listi (duboka kopija).

Rešenje

DEEP COPY(head)
p = head
q = r = new_node = nil
new_head = new_tail = nil
while p ≠ nil do
    new_node = GETNODE
    value(new_node) = value(p)
    other_p(new_node) = other_p(p)
    if new_head = nil then
        new_head = new_node
    else
        next(new_tail) = new_node
    end_if
    new_tail = new_node
    p = next(p)
end_while
p = head
q = new_head
while p ≠ nil do
    r = new_head
    while r ≠ nil do
        if other_p(r) = p then
            other_p(r) = q
        end_if
        r = next(r)
    end_while
    p = next(p)
    q = next(q)
end_while
return new_head

2. zadatak

Postavka

Neka je datoj funkciji POST_TO_INF prosleđen neki aritmetički izraz u postfiksnom obliku (expression). Operandi su velika slova engleskog alfabeta. Napisati iterativnu implementaciju ove funkcije koja kao rezultat vraća dati aritmetički izraz transformisan u infiksnu formu. Rezultujući izraz formirati korišćenjem potpunih zagrada.

Rešenje

POST TO INF(expression)
stack = nil
expr1 = expr2 = nil
for c in expression do
    if IS_BINARY_OPERATOR(c) then
        expr1 = POP(stack)
        expr2 = POP(stack)
        PUSH(stack, "(" + expr1 + c + expr2 + ")")
    else if IS_UNARY_OPERATOR(c) then
        expr1 = POP(stack)
        PUSH(stack, "(" + c + expr1 + ")")
    else
        PUSH(stack, c)
    end_if
end_for
return POP(stack)
PUSH(stack, value)
node = GETNODE
value(node) = value
next(node) = stack
stack = node
POP(stack, value)
if stack = nil then
    ERROR(Underflow)
else
    node = stack
    value = value(node)
    stack = next(stack)
    FREENODE(node)
    return value
end_if

3. zadatak

Postavka

Vektorska implementacija prioritetnog reda

U prioritetni red se prvo redom ubacuju sledeći elementi 2, 18, 19, 1, 9, 6. Nakon toga se iz reda uklanjaju dva elementa i potom dodaju elementi 15, 17 i 11, redom. Kapacitet vektora u koji se smeštaju elementi je 7. Manji broj označava veći prioritet. Za svaki od datih načina implementacije prikazati izgled reda nakon inicijalnog umetanja, nakon svakog brisanja i svakog umetanja poslednja tri elementa (15, 17 i 11). Ukoliko implementacija koristi neke dodatne pokazivače, naznačiti ih ispod odgovarajućeg indeksa u vektoru.

1. Implementacija održavanjem uređenosti reda
2. Implementacija markiranjem elemenata, bez umetanja preko markiranog elementa
3. Implementacija markiranjem elemenata, sa umetanjem preko markiranog elementa

Rešenje

Implementacija održavanjem uređenosti reda

1	2	6	9	18	19
2	6	9	18	19
6	9	18	19
6	9	15	18	19
6	9	15	17	18	19
6	9	11	15	17	18	19

Implementacija markiranjem elemenata, bez umetanja preko markiranog elementa

2	18	19	1	9	6
2	18	19	X	9	6
X	18	19	X	9	6
X	18	19	X	9	6	15
18	19	9	6	15	17
18	19	9	6	15	17	11

Implementacija markiranjem elemenata, sa umetanjem preko markiranog elementa

2	18	19	1	9	6
2	18	19	X	9	6
X	18	19	X	9	6
15	18	19	X	9	6
15	18	19	17	9	6
15	18	19	17	9	6	11

4. zadatak

Postavka

Neka se blok-dijagonalna matrica definiše kao kvadratna matrica A dimenzija n x n čiji su nenulti elementi smešteni samo u okviru blokova dimenzije k x k koji se nalaze na glavnoj dijagonali matrice, kao na slici i važi uslov n mod k = 0. Ukratko objasniti postupak smeštanja i izvesti adresnu funkciju pri pristupu proizvoljnom elementu matrice A[1:n, 1:n] smeštene po vrstama. Smatrati da se jedan element matrice smešta u tačno jednu memorijsku reč.

Primer matrice za $n = 6, k = 2$

-	1	2	3	4	5	6
1	X	X
2	X	X
3			X	X
4			X	X
5					X	X
6					X	X

Rešenje

1. Prvo gledamo u kojem se "bloku" na dijagonali nalazi element koji biramo. Taj blok možemo naći kao $i_b = \left\lfloor\frac{j-1}{k}\right\rfloor$.
2. Nakon toga, možemo na osnovu indeksa bloka (koji kreće od 0) možemo naći $i$ i $j$ indekse za gornji levi ćošak tog bloka kao $i_{blok} = j_{blok} = i_b \cdot k + 1$.
3. Sada računamo indeks trenutnog elementa na osnovu tri podatka: koliko se elemenata nalazi u prethodnim blokovima, koliko se elemenata nalazi iznad trenutnog elementa u trenutnom bloku i koliko se elemenata nalazi levo od trenutnog elementa u trenutnom bloku.
   1. Prethodni blokovi: $A_{pret} = i_b \cdot k^2$ (u svakom bloku se nalazi po $k^2$ elemenata)
   2. Iznad: $A_{izn} = (i - i_{blok}) k$ (u svakom redu nalazi se $k$ elemenata)
   3. Levo: $A_{lev} = j - j_{blok}$
4. Konačna adresna funkcija: $A = A_{11} + (A_{pret} + A_{izn} + A_{lev}) S = A_{11} + (i_b \cdot k^2 + (i - i_{blok}) k + j - j_{blok}) S =$

   $= A_{11} + \left(\left\lfloor\frac{j-1}{k}\right\rfloor \cdot k^2 + \left(i - \left\lfloor\frac{j-1}{k}\right\rfloor \cdot k - 1\right) k + j - \left\lfloor\frac{j-1}{k}\right\rfloor \cdot k - 1\right) S$

5. Uslov: $|i - j| < k$

Drugi kolokvijum

1. zadatak

Postavka

Postorder i preorder obilazak

1. Da li je, pomoću datog preorder i postorder obilaska binarnog stabla moguće rekonstruisati jedinstveno binarno stablo? Detaljno obrazložiti odgovor.
2. Ukoliko je preorder obilazak stabla VALDENJOM, a postorder obilazak stabla DLEAOMJNV, rekonstruisati stablo. Ukoliko postoji više mogućih stabala, dati izgled svakog od njih.

Rešenje

1. Ne može, jer ako neki čvor ima samo jedno dete ne može se odrediti da li je to levo ili desno dete samo iz preorder i postorder obilaska tog stabla.
2. Moguće su četiri rekonstrukcije, jer se ne zna da li je čvor D levo ili desno dete čvora L i takođe da li je čvor J levo ili desno dete čvora N.

        V             V              V                V
     /     \       /     \        /     \          /     \
    A       N     A       N      A       N        A       N
   / \     /     / \     /      / \       \      / \       \
  L   E   J     L   E   J      L   E       J    L   E       J
 /       / \     \     / \    /           / \    \         / \
D       O   M     D   O   M  D           O   M    D       O   M

2. zadatak

Postavka

Slova Morzeove azbuke kodiraju se kao kombinacija crtica (-) i tačaka (.) (A = .- , B= -… , itd.). Neka je poznat način kodiranja svih slova azbuke i poznato je da su kodovi prefiksni, odnosno da kraći kod može biti prefiks dužeg koda.

1. Predložiti i opisati strukturu stabla pogodnu za operaciju dekodovanja pojedinačnih simbola poruke.
2. Implementirati funkciju DECODE_MORSE koja na osnovu strukture predložene pod a) dekodira neku zadatu poruku. Poruka je prosleđena kao argument funkcije (msg) i predstavlja nisku crtica i tacaka. Smatrati da su kodirana slova odvojena blanko znakovima.

Rešenje

Struktura pogodna za dekodiranje Morzeovih kodova jeste binarno stablo gde grane ulevo označavaju da kod na tom mestu sadrži tačku a grane udesno da kod na tom mestu sadrži crtu i u svakom čvoru se čuva u koje slovo se dekodira kod čije su grane praćene da bi se stiglo do tog čvora, ili 0 ako se taj kod ne dekodira ni u jedno slovo.

DECODE MORSE(msg)
i = 0
new_msg = ""
while msg[i] ≠ 0 do
    p = root
    while (msg[i] ≠ ' ') and (p ≠ nil) do
        if msg[i] = '.' then
            p = left(p)
        else if msg[i] = - then
            p = right(p)
        else
            ERROR(Invalid code)
        end_if
        i = i + 1
    end_while
    i = i + 1
    if (p = nil) or (sign(p) = 0) then
        ERROR(Invalid code)
    end_while
    new_msg = new_msg + sign(p)
end_while
return new_msg

3. zadatak

Postavka

Primenom LZW algoritma prikazati postupak kodiranja znakovnog niza BIBBIDIBOBBIDIBOO, ako je data početna tabela sa kodovima simbola. Napisati kodiranu poruku i izgled tabele simbola nakon postupka kodiranja.

Rešenje

Krajnje kodirano: 0204153628033

Tablica LZW kodova (prva četiri data u postavci)

Slovo	Kod
B	0
D	1
I	2
O	3
BI	4
IB	5
BB	6
BID	7
DI	8
IBO	9
OB	10
BBI	11
ID	12
DIB	13
BO	14
OO	15

Postupak dekodovanja

Unos	String	Ispis	Dodaje se u tabelu
B	B
I	BI	0 (B)	BI
B	IB	2 (I)	IB
B	BB	0 (B)	BB
I	BI
D	BID	4 (BI)	BID
I	DI	1 (D)	DI
B	IB
O	IBO	5 (IB)	IBO
B	OB	3 (O)	OB
B	BB
I	BBI	6 (BB)	BBI
D	ID	2 (I)	ID
I	DI
B	DIB	8 (DI)	DIB
O	BO	0 (B)	BO
O	OO	3 (O)	OO
	O	3 (O)

4. zadatak

Postavka

Dužine puteva u stablu

1. Formalno definisati i objasniti internu, eksternu i težinsku eksternu dužinu puta u binarnom stablu.
2. Napisati u pseudokodu implementaciju funkcije koja izračunava težinsku eksternu dužinu puta binarnog stabla na čiji koren ukazuje pokazivač root. Smatrati da listovi stabla poseduju informaciju o težini čvora. Dozvoljeno koristiti gotove linearne strukture podataka.

Rešenje

• Interna dužina puta je zbir dužina puteva od korena do svakog internog čvora.
• Eksterna dužina puta je zbir dužina puteva od korena do svakog eksternog čvora.
• Eksterna težinska dužina puta je zbir proizvoda dužina puteva od korena do svakog eksternog čvora i težine tih eksternih čvorova.

Za potrebe ovog algoritma smatra se da su eksterni čvorovi izjednačeni sa listovima.

CALC EXT WPL(root)
QUEUE_INIT(Q_nodes)
QUEUE_INIT(Q_levels)
INSERT(Q_nodes, root)
INSERT(Q_levels, 0)
node = nil
level = 0
pwe = 0
while not QUEUE_EMPTY(Q_nodes) do
    node = DELETE(Q_nodes)
    level = DELETE(Q_levels)
    if (left(node) = nil) and (right(node) = nil) then
        pwe = pwe + level * weight(node)
    end_if
    if left(node) ≠ nil then
        INSERT(Q_nodes, left(node))
        INSERT(Q_levels, level + 1)
    end_if
    if right(node) ≠ nil then
        INSERT(Q_nodes, right(node))
        INSERT(Q_levels, level + 1)
    end_if
end_while
return pwe

Treći kolokvijum

1. zadatak

Postavka

Dat je usmeren, aciklični graf predstavljen pomoću matrice susednosti kod koga su čvorovi numerisani od 1 do n. Objasniti kako se korišćenjem odgovarajućeg grafovskog algoritma mogu prenumerisati čvorovi tako da matrica susednosti postane gornja trougaona i napisati u pseudokodu funkciju RELABEL koja prenumerisanje.

Rešenje

RELABEL(G, n)
topsort_length = 0
for i = 1 to n do
    in_deg[i] = 0
    for j = 1 to n do
        if M[j, i] then
            in_deg[i] = in_deg[i] + 1
        end_if
    end_for
    if in_deg[i] = 0 then
        topsort_length = topsort_length + 1
        topsort[topsort_length] = i
    end_if
end_for
for i = 1 to n do
    node = topsort[i]
    for j = 1 to n do
        if M[node, j] then
            in_deg[j] = in_deg[j] - 1
            if in_deg[j] = 0 then
                topsort_length = topsort_length + 1
                topsort[topsort_length] = j
            end_if
        end_if
    end_for
end_for
return topsort

2. zadatak

Postavka

Graf iz postavke drugog zadatka.

Floyd-ov algoritam. Na slici je dat usmereni težinski graf.

1. Predstaviti dati graf odgovarajućom matričnom reprezentacijom.
2. Pronaći najkraća rastojanja među čvorovima upotrebom Floyd-ovog algoritma. Postupak prikazati po koracima.
3. Na osnovu rezultat pod b) rekonstruisati najkraću putanju između čvorova b i d.

Rešenje

Rešenje stavke pod c je bfaced.

Matrična reprezentacija grafa

-	a	b	c	d	e	f
a	∞	7	3	10	8	∞
b	∞	∞	∞	22	∞	1
c	∞	∞	∞	5	2	∞
d	∞	∞	∞	∞	∞	12
e	∞	∞	∞	1	∞	∞
f	6	∞	∞	∞	∞	∞

Floyd-ov algoritam za $k = 1$

∞	7	3	10	8	∞
∞	∞	∞	22	∞	1
∞	∞	∞	5	2	∞
∞	∞	∞	∞	∞	12
∞	∞	∞	1	∞	∞
6	13	9	16	14	∞

Matrica prethodnika za $k = 1$

0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0
0	1	1	1	1	0

Floyd-ov algoritam za $k = 2$

∞	7	3	10	8	8
∞	∞	∞	22	∞	1
∞	∞	∞	5	2	∞
∞	∞	∞	∞	∞	12
∞	∞	∞	1	∞	∞
6	13	9	16	14	14

Matrica prethodnika za $k = 2$

0	0	0	0	0	2
0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0
0	1	1	1	1	2

Floyd-ov algoritam za $k = 3$

∞	7	3	8	5	8
∞	∞	∞	22	∞	1
∞	∞	∞	5	2	∞
∞	∞	∞	∞	∞	12
∞	∞	∞	1	∞	∞
6	13	9	14	11	14

Matrica prethodnika za $k = 3$

0	0	0	3	3	2
0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0
0	1	1	3	3	2

Floyd-ov algoritam za $k = 4$

∞	7	3	8	5	8
∞	∞	∞	22	∞	1
∞	∞	∞	5	2	17
∞	∞	∞	∞	∞	12
∞	∞	∞	1	∞	13
6	13	9	14	11	14

Matrica prethodnika za $k = 4$

0	0	0	3	3	2
0	0	0	0	0	0
0	0	0	0	0	4
0	0	0	0	0	0
0	0	0	0	0	4
0	1	1	3	3	2

Floyd-ov algoritam za $k = 5$

∞	7	3	6	5	8
∞	∞	∞	22	∞	1
∞	∞	∞	3	2	15
∞	∞	∞	∞	∞	12
∞	∞	∞	1	∞	13
6	13	9	12	11	14

Matrica prethodnika za $k = 5$

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

Floyd-ov algoritam za $k = 6$

14	7	3	6	5	8
7	14	10	13	12	1
21	28	24	3	2	15
18	25	21	24	23	12
19	26	22	1	24	13
6	13	9	12	11	14

Matrica prethodnika za $k = 6$

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

3. zadatak

Postavka

Graf iz postavke trećeg zadatka.

Na slici je dat protočni graf u okviru koga postoji već uspostavljen protok po pojedinim granama. Nacrtati rezidualni graf i navesti sve moguće puteve povećanog protoka u sledećoj iteraciji, uz navođenje kapaciteta za te puteve.

Rešenje

Rezidualni graf za treći zadatak.

Mogući putevi povećanog protoka:

• SCBT (2)
• SACBT (2)
• SDECBT (2)
• SADECBT (2)

4. zadatak

Postavka

Neka se posmatra se neusmeren netežinski graf.

1. Na koji način se u ovakvom grafu može ostvariti provera cikličnosti grafa korišćenjem algoritama za obilazak po širini i po dubini? Objasniti i nacrtati primer.
2. Napisati u pseudokodu implementaciju funkcije koja korišćenjem obilaska po širini određuje da li je prosleđeni graf cikličan. Smatrati da je graf predstavljen matricom susednosti. Dozvoljeno je koristiti gotove linearne strukture podataka.

Rešenje

Obilaskom po širini ili dubini se u neusmerenom grafu može detektovati ciklus tako što prilikom obilaska detektujemo da posećujemo čvor koji smo već posetili, a da to nije otac trenutnog čvora u stablu obilaska.

IS CYCLIC(G)
for i = 1 to n do
    visited[i] = 0
end_for
QUEUE_INIT(Q_nodes)
QUEUE_INIT(Q_parents)
INSERT(Q_nodes, 1)
INSERT(Q_parents, 0)
node = parent = 0
while not QUEUE_EMPTY(Q_nodes) do
    node = DELETE(Q_nodes)
    parent = DELETE(Q_parents)
    for (node, i) ∈ E do
        if i = parent then
            continue
        end_if
        if visited[i] then
            return true
        end_if
        INSERT(Q_nodes, i)
        INSERT(Q_parents, node)
        visited[i] = true
    end_for
end_while
return false