---
# System prepended metadata

title: '**Assignment 5**'

---

# **Assignment 5**

## Problem 1
(0, 5, 3) : (5, 0, 3), (3, 5, 0)
(1, 4, 3) : (0, 5, 3), (5, 0, 3), (4, 4, 0), (1, 5, 2)
(1, 5, 2) : (0, 5, 3), (6, 0, 2), (1, 4, 3), (3, 5, 0)
(2, 3, 3) : (0, 5, 3), (5, 0, 3), (5, 3, 0), (2, 5, 1)
(2, 4, 2) : (1, 5, 2), (1, 4, 3), (6, 0, 2), (2, 3, 3), (4, 4, 0), (2, 5, 1)
(2, 5, 1) : (0, 5, 3), (7, 0, 1), (2, 3, 3), (3, 5, 0)
(3, 2, 3) : (0, 5, 3), (5, 0, 3), (6, 2, 0), (3, 5, 0)
(3, 3, 2) : (1, 5, 2), (2, 3, 3), (6, 0, 2), (3, 2, 3), (5, 3, 0), (3, 5, 0)
(3, 4, 1) : (2, 5, 1), (1, 4, 3), (7, 0, 1), (3, 2, 3), (4, 4, 0), (3, 5, 0)
(3, 5, 0) : (0, 5, 3), (8, 0, 0), (3, 2, 3)
(4, 1, 3) : (0, 5, 3), (5, 0, 3), (7, 1, 0), (4, 4, 0)
(4, 2, 2) : (1, 5, 2), (3, 2, 3), (6, 0, 2), (4, 1, 3), (6, 2, 0), (4, 4, 0)
(4, 3, 1) : (2, 5, 1), (2, 3, 3), (7, 0, 1), (4, 1, 3), (5, 3, 0), (4, 4, 0)
(4, 4, 0) : (3, 5, 0), (1, 4, 3), (8, 0, 0), (4, 1, 3)
(5, 0, 3) : (0, 5, 3), (8, 0, 0), (5, 3, 0)
(5, 1, 2) : (1, 5, 2), (4, 1, 3), (6, 0, 2), (5, 0, 3), (7, 1, 0), (5, 3, 0)
(5, 2, 1) : (2, 5, 1), (3, 2, 3), (7, 0, 1), (5, 0, 3), (6, 2, 0), (5, 3, 0)
(5, 3, 0) : (3, 5, 0), (2, 3, 3), (8, 0, 0), (5, 0, 3)
(6, 0, 2) : (1, 5, 2), (5, 0, 3), (8, 0, 0), (6, 2, 0)
(6, 1, 1) : (2, 5, 1), (4, 1, 3), (7, 0, 1), (6, 0, 2), (7, 1, 0), (6, 2, 0)
(6, 2, 0) : (3, 5, 0), (3, 2, 3), (8, 0, 0), (6, 0, 2)
(7, 0, 1) : (2, 5, 1), (5, 0, 3), (8, 0, 0), (7, 1, 0)
(7, 1, 0) : (3, 5, 0), (4, 1, 3), (8, 0, 0), (7, 0, 1)
(8, 0, 0) : (3, 5, 0), (5, 0, 3)

array[i][j] = new Vertex();
            Vertex* temp = array[i][j];
            temp->init(i,j);
            
struct Vertex {

    string color;
    int d;
    Vertex* p;
    Vertex* adj[6];
    int name;


    void init(int i,int j){
    
        color = "white";
        d = 10000;
        p = nullptr;
        for(int i = 0; i < 6; ++i){
            adj[i]= nullptr;
        }
        name = (i+1)*10 + (j+1);
    }

};



A)
(8,0,0),(3,5,0)
(8,0,0),(5,0,3)
(3,5,0),(0,5,3)
(3,5,0),(3,2,3)
(5,0,3),(5,3,0)
(3,2,3),(6,2,0)
(5,3,0),(2,3,3)
(6,2,0),(6,0,2)
(2,3,3),(2,5,1)
(6,0,2),(1,5,2)
(2,5,1),(7,0,1)
(1,5,2),(1,4,3)
(7,0,1),(7,1,0)
(1,4,3),(4,4,0)
(7,1,0),(4,1,3)


B)
(8,0,0),(3,5,0)
(3,5,0),(0,5,3)
(0,5,3),(5,0,3)
(5,0,3),(5,3,0)
(5,3,0),(2,3,3)
(2,3,3),(2,5,1)
(2,5,1),(7,0,1)
(7,0,1),(7,1,0)
(7,1,0),(4,1,3)
(4,1,3),(4,4,0)
(4,4,0),(1,4,3)
(1,4,3),(1,5,2)
(1,5,2),(6,0,2)
(6,0,2),(6,2,0)
(6,2,0),(3,2,3)


C)
YES OFKROS, BFS method uses less pouring steps compared to DFS method
{(8, 0, 0), (3, 5, 0), (3, 2, 3), (6, 2, 0), (1, 5, 2), (1, 4, 3), (4, 4, 0)}



D)
The algorithm is doing exactly that and the algorithm is absolutely and undeniably true.

E)
NO

F)
IT IS NOT POSSIBLE. No vertex (6,1,1) in DFS and BFS method which produce all items that are reachable. since (6,1,1) is not present in both trees, thus there is no way to get (6,1,1) from (8,0,0)

G)
Yes, WLOG we can reverse the order of pouring :)
(8, 0, 0) can always be obtained from v ∈ V − {v0} by pouring all water from second and third jug to first jug
v will always have a move in which all water in either second or third jug is poured all the way to first jug


H)
False
(8, 0, 0) is reachable from (6, 1, 1) by pouring all water from second and third jug to first jug but (6, 1, 1) is not reachable from (8, 0, 0) as proved in (F)



## Problem 2

```
SpreadOfInfluence(X) -> X arbitrary vertex

for each vertex u in V do
        u.active <- false
        u.influence <- 0

Initialize an empty queue Q

count <- 1

Enqueue(Q, x)

while Q ≠ Ø 
    x <- Dequeue(Q)
    
    set x as active
    
    for every node y connected to x
        
        if y is not active then
            add w(x,y) to y.influence
            
        if y.influence ≥ t(y) and y is not active then 
            count = count + 1
            Enqueue(Q,y)
            
return count

```

## Problem 3
Known that since all the weights are distinct, hence there is a unique MST.


## Problem 4
Assume we can get all the edges connected to vertex u in MST T given using Adj[u]
```
UpdateMST(T, root, e′):
    for each vertex x in V do
        x.color ← white
        x.path ← ø
    
    max_weight ← w(e′)
    max_edge ← (e′)
    u ← e′.u
    v ← e′.v
    u.color ← gray
    
    
    initialize empty queue Q
    
    Enqueue(Q, root)
    While Q ≠ ø do
        x ← Dequeue(Q)
        
        for each y in Adj[x] do
            if y.color = white then
                y.color ← gray
            
                if y.path ≠ ø then
                    y.path = x.path + (x, y)
                else
                    y.path = (x, y)
                Enqueue(Q,y)
        
        x.color ← black
        
    our_path = v.path ⋂ u.path
    
    for each edge in our_path do
        if w(edge) > max_weight then
            max_weight ← w(edge)
            max_edge ← edge
    
    
    if w(max_edge) > w(e') then
        remove max_edge from T
        add e' to T
        
        
    return T
        
```


Kalo pake CycleDetection lecnotes
```
UpdateMST(G, T, e′):

// Include new edge e' as part of the MST, thus creating a single cycle in the new MST T'
T'.E = T.E U e'

Let cycle be an empty array
cycle = CycleDetection(T)         -> receives set of V,E as input, then returns a set of nodes that are in cycle

max_edge = ø                           -> (node1, node2)

for i = cycle length down to 1
    if i = 1 then
        current_edge_weight = w(cycle[1], cycle[length of cycle])
        
        if w(max_edge) < current_edge_weight then
            max_edge = (cycle[1], cycle[length of cycle])
    else
        current_edge_weight = w(cycle[i], cycle[i-1])
        
        if w(max_edge) < current_edge_weight then
            max_edge = (cycle[i], cycle[i-1])

    
if w(e') < w(max_edge) then
    remove max_edge from T'
else
    remove e' from T'


return T'
```
## Problem 5

### 7 itu v, kiri itu parentnya kanan. Bikin tree nya dari sini aja
**A)**

a)
{25,26}
{25,15}
{25,24}
{25,35}
{26,74}
{26,16}
{26,36}
{15,71}
{15,14}
{24,23}
{24,34}
{35,45}
{74,66}
{74,56}
{74,46}
{71,13}
{71,12}
{71,11}
{23,22}
{23,33}
{34,44}
{45,55}
{66,65}
{66,73}
{11,72}
{11,21}
{22,32}
{33,43}
{44,54}
{65,64}
{73,61}
{73,62}
{73,63}
{72,31}
{72,41}
{72,51}
{32,42}
{43,53}
{62,52}



b)
{25,26}
{26,74}
{74,66}
{66,56}
{56,46}
{46,36}
{36,35}
{35,34}
{34,24}
{24,14}
{14,15}
{15,16}
{16,71}
{71,13}
{13,12}
{12,11}
{11,72}
{72,21}
{21,22}
{22,23}
{23,33}
{33,32}
{32,31}
{31,41}
{41,42}
{42,43}
{43,44}
{44,45}
{45,55}
{55,54}
{54,53}
{53,52}
{52,51}
{51,61}
{61,62}
{62,63}
{63,64}
{64,65}
{65,73}


B)
a)
{71,16}
{71,15}
{71,14}
{71,13}
{71,12}
{71,11}
{16,74}
{16,26}
{15,25}
{14,24}
{13,23}
{12,22}
{11,72}
{11,21}
{74,66}
{74,56}
{74,46}
{74,36}
{25,35}
{24,34}
{23,33}
{22,32}
{72,31}
{72,41}
{72,51}
{72,61}
{66,65}
{66,73}
{56,55}
{46,45}
{34,44}
{33,43}
{32,42}
{51,52}
{61,62}
{65,64}
{73,63}
{55,54}
{43,53}


b)
{71,16}
{16,74}
{74,66}
{66,56}
{56,46}
{46,36}
{36,26}
{26,25}
{25,15}
{15,14}
{14,13}
{13,12}
{12,11}
{11,72}
{72,21}
{21,22}
{22,23}
{23,24}
{24,34}
{34,35}
{35,45}
{45,44}
{44,43}
{43,33}
{33,32}
{32,31}
{31,41}
{41,42}
{42,52}
{52,53}
{53,54}
{54,55}
{55,65}
{65,64}
{64,63}
{63,62}
{62,61}
{61,51}
{61,73}



## Problem 6
A
a
```
S = {SFO}
T ={}

S = {SFO, LAX}
T ={(SFO,LAX)}

S = {SFO, LAX, DEN}
T ={(SFO,LAX), (LAX, DEN)}

S = {SFO, LAX, DEN, ORD}
T ={(SFO,LAX), (LAX, DEN), (DEN, ORD)}

S = {SFO, LAX, DEN, ORD, ATL}
T ={(SFO,LAX), (LAX, DEN), (DEN, ORD), (ORD, ATL)}

S = {SFO, LAX, DEN, ORD, ATL, MIA}
T ={(SFO,LAX), (LAX, DEN), (DEN, ORD), (ORD, ATL), (ATL, MIA)}

S = {SFO, LAX, DEN, ORD, JKF, BOS, ATL, MIA, JFK}
T ={(SFO,LAX), (LAX, DEN), (DEN, ORD), (ORD, ATL), (ATL, MIA), (ORD, JFK)}

S = {SFO, LAX, DEN, ORD, JKF, BOS, ATL, MIA, JFK, BOS}
T ={(SFO,LAX), (LAX, DEN), (DEN, ORD), (ORD, ATL), (ATL, MIA), (ORD, JFK), (JFK, BOS)}

S = {SFO, LAX, DEN, ORD, JKF, BOS, ATL, MIA, JFK, BOS, DFW}
T ={(SFO,LAX), (LAX, DEN), (DEN, ORD), (ORD, ATL), (ATL, MIA), (ORD, JFK), (JFK, BOS), (ORD, DFW)}

S = {SFO, LAX, DEN, ORD, JKF, BOS, ATL, MIA, JFK, BOS, DFW, HNL}
T ={(SFO,LAX), (LAX, DEN), (DEN, ORD), (ORD, ATL), (ATL, MIA), (ORD, JFK), (JFK, BOS), (ORD, DFW), (LAX, HNL)}

minimum total = 7562

table:
        ATL    BOS    DEN    DFW    HNL    JFK    LAX    MIA    ORD    SFO
w[u]    606    191    834    802    2555   722    349    595    908    0
p[u]    ORD    JFK    LAX    ORD    LAX    ORD    SFO    ATL    DEN    -

```

b
```
(BOS,JFK) -> YES
(LAX,SFO) -> YES
(ATL,MIA) -> YES
(ATL,ORD) -> YES
(JFK,ORD) -> YES
(ATL,JFK) -> NO
(DFW,ORD) -> YES
(DEN,LAX) -> YES
(BOS,ORD) -> NO
(DEN,ORD) -> YES
(DEN,SFO) -> NO
(JFK,MIA) -> NO
(DFW,MIA) -> NO
(BOS,MIA) -> NO
(DFW,LAX) -> NO
(ORD,SFO) -> NO
(JFK,LAX) -> NO
(JFK,SFO) -> NO
(HNL,LAX) -> YES

minimum total = 7562
```


B
a
```
S = {ATL}
T = {}

S = {ATL, MIA}
T = {{ATL, MIA}}

S = {ATL, MIA, JFK}
T = {{ATL, MIA}, {ATL, JFK}}

S = {ATL, MIA, JFK, BOS}
T = {{ATL, MIA}, {ATL, JFK}, {JFK, BOS}}

S = {ATL, MIA, JFK, BOS, ORD}
T = {{ATL, MIA}, {ATL, JFK}, {JFK, BOS}, {JFK,ORD}}

S = {ATL, MIA, JFK, BOS, ORD, DFW}
T = {{ATL, MIA}, {ATL, JFK}, {JFK, BOS}, {JFK,ORD}, {ORD,DFW}}

S = {ATL, MIA, JFK, BOS, ORD, DFW, DEN}
T = {{ATL, MIA}, {ATL, JFK}, {JFK, BOS}, {JFK,ORD}, {ORD,DFW}, {ORD,DEN}}

S = {ATL, MIA, JFK, BOS, ORD, DFW, DEN, SFO}
T = {{ATL, MIA}, {ATL, JFK}, {JFK, BOS}, {JFK,ORD}, {ORD,DFW}, {ORD,DEN}, {DEN,SFO}}

S = {ATL, MIA, JFK, BOS, ORD, DFW, DEN, SFO, LAX}
T = {{ATL, MIA}, {ATL, JFK}, {JFK, BOS}, {JFK,ORD}, {ORD,DFW}, {ORD,DEN}, {DEN,SFO}, {SFO,LAX}}

S = {ATL, MIA, JFK, BOS, ORD, DFW, DEN, SFO, LAX, HNL}
T = {{ATL, MIA}, {ATL, JFK}, {JFK, BOS}, {JFK,ORD}, {ORD,DFW}, {ORD,DEN}, {DEN,SFO}, {SFO,LAX}, {LAX,HNL}}
table:
        ATL    BOS    DEN    DFW    HNL    JFK    LAX    MIA    ORD    SFO
w[u]    0      49     60     50     139    79     39     69     59     80   
p[u]           JFK    ORD    ORD    LAX    ATL    SFO    ATL    JFK    DEN        

minimum cost = 624
```
b
```
(LAX,SFO) -> YES
(BOS,JFK) -> YES
(DFW,ORD) -> YES
(JFK,ORD) -> YES
(DEN,ORD) -> YES
(ATL,MIA) -> YES
(BOS,ORD) -> NO
(ATL,JFK) -> YES
(DEN,SFO) -> YES
(DEN,LAX) -> NO
(ORD,SFO) -> NO
(ATL,ORD) -> NO
(DFW,JFK) -> NO
(JFK,MIA) -> NO
(DFW,LAX) -> NO
(JFK,SFO) -> NO
(DFW,MIA) -> NO
(JFK,LAX) -> NO
(BOS,MIA) -> NO
(HNL,LAX) -> YES

minimum cost = 624
```



# C
# O
# V
# I
# D
# -
# 1
# 9
# ~~~~~~~~~~~~~~
# GG
# GG
# GG
# GG
# GG
# GG
# GG
# GG

