АСП1/Јун 2020

Drugi kolokvijum

1. zadatak

Postavka

1. Da li se binarno stablo može jednoznačno rekonstruisati iz preorder i postorder obilaska tog stabla?
2. Dati sve moguće rekonstrukcije stabla čiji je preorder obilazak (?) a postorder (?).

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. (Bile su četiri moguće rekonstrukcije jer su dva čvora imala samo jedno dete.)

2. zadatak

Postavka

Morzeovi kodovi se sastoje iz tački (.) i crta (-) i svako slovo alfabeta se kodira sekvencom tački i crta. Ako se zna da jedan kod može preklapati sa početkom nekog drugog koda, osmisliti strukturu koja bi mogla da se koristi za dekodiranje Morzeovih kodova i napisati pseudokod za dekodiranje poruke kodirane Morzeovim kodovima ako se zna da se između slova nalazi blanko znak.

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, root)
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

Kodirati sekvencu BIBBIDIBOBBIDIBOO po koracima.

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

1. Definisati internu dužinu puta, eksternu dužinu puta i eksternu težinsku dužinu puta.
2. Napisati algoritam koji za dato stablo računa eksternu težinsku dužinu puta. Smatrati da listovi stabla sadrže informacije o težini. Dozvoljeno je korišćenje linearnih struktura 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.

EXTERNAL WEIGHTED PATH LENGTH(root)
QUEUE_INIT(Q_nodes)
QUEUE_INIT(Q_levels)
INSERT(Q_nodes, root)
INSERT(Q_levels, root)
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

2. zadatak

Postavka

1. (?)
2. Napisati postupak za Flojdov algoritam na datom grafu. (?)
3. Napisati najkraći put od čvora b do čvora d.

Rešenje

1. (?)
2. (?)
3. bfaced

3. zadatak

Postavka

Dat je protočni graf na slici (?). Nacrtati rezidualni graf od tog protočnog grafa i navesti sve puteve povećanog protoka i napisati njihov protok.

Rešenje

• SCBT (2)
• SACBT (2)
• SDECBT (2)
• SDACBT (2)

4. zadatak

Postavka

Opisati na koji način se u neusmerenom grafu može detektovati ciklus pomoću obilaska po širini i dubini i napisati iterativni algoritam za detekciju ciklusa u neusmerenom grafu pomoću obilaska po širini. Dozvoljeno je koristiti 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