2023年11月25日

算法设计代写 | COMP20007 DESIGN OF ALGORITHMS Assignment 2

本次澳洲代写主要为算法设计的assignment

COMP20007 DESIGN OF ALGORITHMS Assignment 2

Programming Problems
Problem 1
1 + 2 + 2 + 2 + 1 + 2 + 2 = 12 Marks
Australia faces one of its biggest disasters: a total power outage that lasted for a few minutes.
You are the CTO for the National Super Network (NSN). NSN is responsible for Australia’s
Internet backbone and connects all key Internet servers in Australia. After the blackout you
decide that it is best to ascertain the consequences of the power outage.
NSN has built its high-speed network so that
• all server connections are bi-directional;
• any two servers are connected if they share an edge or each of themhas a path to a shared
server;
• the network can have subnetworks.
If everything is working well, all servers in a subnetwork are connected. Fortunately, each
server can be directly contacted through a slow telephone connection. You need to develop an
algorithm that determines the number of connected components in the network.

Task 1
1 Mark
Develop the pseudocode for an efficient algorithm that computes the number of connected
components in a graph G = (V, E) given vertices V and edges E. Discuss the complexity of
your algorithm in detail.
Task 2
2 Marks
Write a C program that takes the name of one file as a command line argument containing
the specification for the network, reads in a text file from standard input and prints out the
total number of connected subnetworks before the outage for this network. Suppose that the
network has n servers and each server has a unique server ID (SID)which is an integer between
0 and n 1 inclusively.
The file specified as the command line argument for this and the subsequent programming
tasks has two parts:
• The first line gives the number of servers, n, and the number of network connections in
the graph, m, separated by a space.
• The following lines specify the m connections between servers, one per line, given as the
two SIDs separated by a space. Note that each edge is listed only once.
The text file received on standard input is also given in two parts:
• The first line specifies the number of servers which are affected by the outage.
• The following line contains a list of all the SIDs affected by the outage, each separated by
a space.
An example input text file (network-1.txt) is given below. The network configuration before
the power outage is demonstrated in the following figure.

All four provided network test cases are shown at the end of the document.
You can assume that the text files used to test your program will be always sensible and cor-
rect. You do not need to perform any data validation. You can assume that a connection

between any pair of servers appears only once in the list. You can also assume the source and
destination server of a connection is always different.
14 17
0 1
0 2
0 3
4 8
4 9
4 5
4 7
5 6
5 7
6 7
10 8
10 12
10 11
10 9
11 12
11 13
12 13
An example of the text file sent in through standard input (outage-1.txt) is:
2
1 4