# **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
Sign in with Wallet
Connect another wallet