Applied Activity $5$ Modified

This is a group work, again. Upon completion of your assignment, include

all Student ID and Names at the end of the document. We still maintain a onesubmission$-$only per$-$group policy.

Please ensure to document each step of the process comprehensively, providing

clear and thorough explanations. You may draw and redraw the graphs $($or use

software to draw them$).$ When detailing your solution, it's crucial to follow a stepby$-$step approach as outlined below. You may also consider putting the solution

in an MS PowerPoint presentation file format, if you prefer so$.$ You may alternatively

record a $1$ to $2-$minute$-$long video for each problem where all group members

participate, but videos longer than $120$ seconds will not be considered. The videos

should not be too blurred, shaking, taken from a mobile to shoot computer screens,

or of bad quality. In short, the format of delivery is up to you as long as it$$s

reasonably concise, professional, and clear.

Add the rightmost digit of all group A$-$numbers and use the result to index the

starting point of the problems. Show this step clearly. Incorrect application of

this step will affect your grades.

For example, if the group is of two students with A$-$numbers:

$$ A$00123456$ and

$$ A$00456789,$ then

Their index is $6+9=15$

The sum of rightmost digits Problem $1$ Problem $2$ Problem $3$ Problem $4$

$9$ or less A $4$ V$2$ S$3$

$10-16$ B $3$ V$3$ S$1$

$17-23$ C $1$ V$1$ S$4$

$24-30$ D $2$ V$5$ S$2$

More than $30$ E $1$ V$4$ S$3$

One more note, for this activity, the notation x $-$ y means there is an UNDIRECTED link between

x and y

Problem $1$: Network Optimization Using Prim's Algorithm $(25$ Marks$)$

Scenario: A company plans to connect its offices in cities A through E with the least amount of cable.

The cost between cities is given in a table.

Find the minimum spanning tree $($MST$)$ using Prim's algorithm. $($Show the initial graph as well as each

step and explain by drawing the graph$)$

Connection Cost

A $$ B $2$

A $$ C $3$

B $$ C $1$

B $$ D $5$

C $$ D $8$

C $$ E $7$

D $$ E $6$

Problem $2$: Route Optimization Using Dijkstra's Algorithm $(25$ Marks$)$

Scenario: The distances between some cities are shown below. Optimize delivery routes to the cities

from the one you must start from, as per the table above. Then, show the shortest path to the Node

$5.$

Show each step in a table and explain it by drawing the undirected graph.

Route Distance

$1-24$

$1-32$

$2-410$

$3-23$

$3-42$

$4-51$

Problem $3$: Infrastructure Development Using MST $(25$ Marks$)$

Scenario: Costs between villages are shown below.

Connect villages V$1$ through V$5$ with the least amount of road possible. Show each step and explain

by drawing the graph

Connection Cost

V$1-$ V$26$

V$1-$ V$31$

V$1-$ V$45$

V$2-$ V$35$

V$2-$ V$53$

V$3-$ V$45$

V$3-$ V$56$

V$4-$ V$52$

Problem $4$: Emergency Services Network Planning $(25$ Marks$)$

Scenario: Plan the fastest emergency routes from the station assigned for you to start from to all

other stations if the travel times are as shown below. Specifically, show the shortest path to the Node

S$5.$ Show each step and explain by tabulation and drawing the graph.

Route Time

S$1-$ S$27$

S$1-$ S$32$

S$1-$ S$46$

S$2-$ S$49$

S$2-$ S$53$

S$3-$ S$41$

S$4-$ S$54$gstudent id$-$A$00266967,$A$00273345,$A$00274933$