代写COMP2521 24T2 Assignment 2 Poodle代做Statistics统计

2024.07.16 - 首页 >> Web

COMP2521 24T2

Assignment 2

Poodle

Changelog

All important changes to the assignment specification and files will be listed here.

·[11/0700:00]Assignment released

Admin

Marks contributes 15%towards your final mark (see Assessment section for more details)

Submit see the Submission section Deadline 8pm on Friday of Week 10

Late penalty 0.2%of the maximum mark per hour or part thereof deducted from the attained mark,submissions later than 5 days not accepted

Background

You are Dr.Barktholomeow,the most fearsome hacker in the universe!

With your hacking skills,you could achieve virtually anything -rick roll the entire world, bankrupt Elon Musk,shut down TikTok...but your cause is much more nefarious (and noble).You aim to hack every computer on Earth to replace all the text on all of its files with dog and cat puns.By hacking one computer network at a time,soon,no-paw-dy will be able to h-yelp talking like t-hiss!It will be purr-fect!Meow-eow-eow-eow!

You call the process of hacking a computer "poodling".To poodle an entire network of computers,you will first poodle an initial computer which you have access to by installing a worm on it (which you affectionately call a "pug").This computer will then forward the pug to other computers that it is directly connected to so that they can be poodled as well.

networks owned by Poodle (tormerly Google),YouChewb (tormerly You lube)and Faceboop (formerly Facebook).Now you have set your sights on another popular website: Wikipetia!

Wikipetia's network consists of computers and connections between pairs of computers. Each computer has a security level between 1 and 10,and takes a certain amount of time to poodle.The security level of a computer determines what other computers it is allowed to communicate with:a computer with security level X can only send to computers with security level X+1 or smaller.Each connection is bidirectional and has a transmission time associated with it,which is the amount of time it would take to send something (such as your pug)from the computer at one end of the connection,to the computer at the other end.

Here is an example network:

In these network diagrams:

·Each set of concentric circles represents a computer

·The large number displayed on each computer indicates the number (or ID)of the computer

·The small number displayed on each computer indicates the amount of time (in seconds)needed to poodle that computer

·The number of rings (or circles)around a computer represents the security level of the computer

·Lines between computers represent connections,with the number next to each one indicating the transmission time (in seconds)across that connection

In the above network,for example,computer 4 has a security level of two (as it has two rings around it),and would take 80 seconds to poodle.After it has been poodled,it could send the pug to computer O (which would take 1 second)and computer 1 (which would take 2 seconds),but not computer 5,as it has a security level of 4.

Change into the directory you created for the assignment and run the following command:

$unzip /web/cs2521/24T2/ass/ass2/downloads/files.zip

If you're working at home,download files.zip by clicking on the above link and then unzip the downloaded file.

You should now have the following files:

Makefile This controls compilation of the program.You only need to modify this if you create additional files for your implementation.

poodle.h This contains struct definitions and function prototypes for the functions you willcomplete in the tasks below. You must not modify this file.

poodle.c This is a stub file for you to complete the tasks below.

testPoodle.c This is a main program for testing your code.You should not modify this file unless you know what you're doing.

data/ This is a directory containing network data files.The format of these files are described below.

task[1234]/ These are directories containing test data files and expected outputs.The

files ending with .in are test data files,while the corresponding .exp files contain expected outputs.

First,compile the original version of the files using the make command.This willproduce one executable:testPoodle.

Note that in this assignment,you are permitted to create as many supporting files as you like.This allows you to compartmentalise your solution into different files.For example, you could implement a Graph ADT in Graph.c and Graph.h.To ensure that these files are actually included in the compilation,you will need to edit the Makefile;the provided Makefile contains instructions on how to do this.

Network Data Files

Network data files contain the details of the network.Each file is formatted as follows:

·The first line contains two integers representing the number of computers n and the number of connections m.

·Then,for each computer there is a line containing two integers:the security level of the computer and the time taken to poodle it.The i-th of these lines (0≤i≤n-1) corresponds to computer i.

·Then,for each connection there is a line containing three integers:the two computers that it connects and the time taken to transmit anything across it.

230

340

370

350

280

440

190

012

233

452

563

041

412

151

523

262

633

The first line indicates that there are 7 computers and 10 connections.Each of the following seven lines describes a computer.For example,computer O has a security leve of 2 and takes 30 seconds to poodle.Each of the ten remaining lines describes a connection.For example,there is a connection between computers 0 and 1 that takes 2 seconds to transmit across.

The provided program in testPoodle.c will read the data file,so you won't need to do any file reading yourself,but you should understand the format of the file so that you can create your own networks for testing.

Test Data Files

Test data files contain the inputs for tests.The format of a test data file depends on the task,but each one always begins with two lines which indicate the task being tested (1-4), and the name of the network data file used in that test.More details are available under the Testing section of each task.

Inputs

In each of the tasks below,you will be given network data as input.This data will be given as an array of computers and an array of connections.Computers and connections are represented by the following structs:

struct computer {

int securityLevel; int poodleTime;

};

struct connection {

};

In the computer struct,securityLevel is the security level of the computer,and will always be an integer between 1 and 10(inclusive).poodleTime is the amount of time it takes to poodle the computer,and will always be a positive integer.

In the connection struct,computerA and computerB are the numbers (IDs)of the computers at the endpoints of the connection,and will always be between O and n-1 (where n is the number of computers),and transmissionTime willalways be a positive integer.In each connection struct,computerA and computerB will always be different.

The computers will be given in an array of size n where index i contains the details of computer i.The connections willbe given in an array of size m(where m is the number of connections).The array of connections will not contain duplicate connections.Since connections are bidirectional,this means the connections (v,w)and (w,v)cannot both appear in the array.

Before you poodle any computers,you would like to first probe the network by sending a harmless pug along different paths of computers to scan their contents.Your pug will move from computer to computer,scanning the contents of each computer before moving on to the next.You would like to measure how long this takes.

Forexample,consider the following network:

Suppose the path is 0-4-1-5-6.The total amount of time taken to probe this path is 30+

1+80+2+40+1+40+3+90=287 seconds.

As you don't have all the details about the network yet,some paths that you try may be invalid.A path can be invalid in two different ways:(1)a computer does not have a connection to the next computer on the path,or (2)a computer does not have permission

However,you can still measure the time taken betore the probe tails,which is 40+2+80+ 1+30+2+40=195 seconds.

A path may contain the same computer more than once.However,since each computer is only scanned the first time it is visited,subsequent visits to a computer take no time (0 seconds).For example,the path 1-4-0-1 would take 40+2+80+1+30+2+0=155 seconds.

If a computer appears multiple times in a row in a path,it should be treated as if it only appeared once.For example,the path 0-0-1-1-0-0 should be treated as 0-1-0.

Your task is to implement the following function:

struct probePathResult probePath(
struct computer computers[], int	numComputers,
struct connection connections[],	int numConnections,
int path[], int pathLength );

The function takes information about the network via an array of computers and an array of connections,and the path as an array of computer IDs,and returns the result of the probe in a struct probePathResult.

The struct contains two fields:status,which indicates whether the probe ran to completion or the reason if it didn't,and elapsedTime,which indicates the total amount of time taken before the probe completed or failed.The status field should be set to:

·SUCCESS if the probe ran to completion

·NO_CONNECTION if the probe failed because a computer did not have a connection to the next computer on the path

·NO_PERMISSION if the probe failed because a computer had a connection but did not have permission to communicate with the next computer on the path

Note that it is not possible for a probe to fail for two different reasons,because a probe stops as soon as one of the above problems occur.

Constraints

To earn most of the marks for this task,you may assume the following:

·The number of computers will be at most 100. ● The number of connections will be at most 100. ·The length of the path will be at most 250,000.

To earn all of the marks for this task,you must assume the following more challenging constraints:

·The number of computers will be at most 250,000.

As it is not necessarily easy to solve the problem with the more challenging constraints, you may want to solve the problem with the easier constraints first,and then come back to solve the challenge later.

Testing

All tasks can be tested using the testPoodle program.The program takes one command- line argument:the name of a test data file.

Test data files contain the parameters for a test case.The format of a test data file depends on the task,but it always begins with one integer,which is the number of the task being tested.

You can test Task 1 by running ./testPoodle with one of the test data files in the task1 directory.The format of the test data file is as follows:

·The first line contains the integer 1.

·The next line contains the name of a network data file (not including the data/ directory prefix).

·The next line contains an integer representing the length of the path,P.

·The final line contains P integers representing the IDs of the computers along the path. Note that this path may contain multiple of the same computer ID.

For example,here is a test data file for Task 1:

network-1a.txt

04156

This means this test is for task 1,it uses the network given in data/network-1a.txt,the probe path has length 5,and the probe path is O-4-1-5-6.

The expected output for this test is:

$./testPoodle task1/1.in

Probe path:0->4 ->1 ->5->6

Result:Success

Time taken:287 seconds

You can run all provided tests using the command:

$./autotest 1

Now that you have gathered information about the network,you would like to choose a computer to start at that willallow you to poodle as many computers as possible.Note that computers are able to send to multiple computers at once.

For example,consider the following network (times are intentionally not shown):

The optimal source computer is computer 8,as you will be able to poodle eight computers:O,1,2,4,5,6,7 and 8.Starting at any other computer will result in you poodling fewer computers.For example,starting at computer 3 will only allow you to poodle three computers:1,3 and 6.Note that the time taken is not relevant here.

Your task is to implement the following function:

The function takes information about the network (in the same manner as probePath), determines the optimal source computer,and returns the result in a

struct chooseSourceResult.

The struct contains three fields:sourceComputer,which indicates the optimal source computer,numComputers,which indicates the number of computers that can be poodled, and computers,which is a dynamically allocated array containing those computers.The array must be sorted in ascending order.

If there are multiple optimal source computers and/or multiple sets of poodled computers as a result,you may return any of them.

Constraints

Testing

You can test task 2 by running ./testPoodle with one of the test data files in the task2 directory.The format of the test data file is as follows:

·The first line contains the integer 2.

·The next line contains the name of a network data file (not including the data/ directory prefix).

For example,here is a test data file for task 2:

network-2a.txt

This means this test is for task 2 and it uses the network given in data/network-2.txt. The expected output for this test is:

$./testPoodle task2/1.in

Source computer:computer 8

Number of reachable computers:8 Reachable computers:

-computer 0 -Computer 1 -Computer 2 -Computer 4 -Computer 5 -computer 6 -computer 7 -Computer 8

You can run all provided tests using the command:

$./autotest 2

Now it is time to take over the world (ahem,network)with your mischief!Given a source computer,your aim is to poodle as many computers as possible,as quickly as possible.

For example,consider the following network:

Suppose your source computer is computer 2.To poodle all the computers as quickly as possible,it should be sent along these paths (highlighted in dotted red):

The following table summarises when each computer will be poodled,and which computers each computer will send your pug to after it has been poodled.

The function takes information about the network and a source computer,and returns a plan to poodle computers as quickly as possible that details,for each computer (that can be poodled),the quickest time that it can be poodled,and the computers that it will need to send the pug to after it has been poodled,in a struct poodleResult.

The poodleResult struct will contain the same kind of information as in the table shown above.The struct contains two fields:numSteps,which is the number of steps in the plan, which is equal to the number of computers that can be poodled,and steps,which is a dynamically allocated array of struct steps.Each struct step contains three fields: computer,which is the ID of a computer that will be poodled,time,which is the time that it willbe poodled,and recipients,which is a linked list of computers that it will send the pug to after it has been poodled.

The array must be sorted in ascending order by time,and each list of recipients must be sorted in ascending order by computer ID.If multiple computers will be poodled at the same time,they may be placed in any order.If there are multiple valid plans (that would result in computers being poodled as quickly as possible),then you may return any of them.

Assumptions

For simplicity,assume that a computer is able to send to multiple computers at the same time.

Constraints

·The number of computers will be at most 100.

● The number of connections will be at most 100.

Testing

You can test task 3 by running ./testPoodle with one of the test data files in the task3 directory.The format of the test data file is as follows:

·The first line contains the integer 3.

·The next line contains the name of a network data file (not including the data/ directory prefix).

·The next line contains the ID of the source computer. For example,here is a test data file for task 3:

This means this test is for task 3,it uses the network given in data/network-3a.txt,and the source computer is 2.

The expected output for this test is:

$./testPoodle task3/1.in

Plan:

-computer 2 poodled at 1 seconds -pug sent to:3,5

-computer 3 poodled at 5 seconds -pug sent to:0

-computer 0 poodled at 7 seconds -pug sent to:4

-computer 5 poodled at 8 seconds -pug sent to:6

-computer 4 poodled at 9 seconds -pug sent to:1

-computer 6 poodled at 11 seconds -computer 1 poodled at 16 seconds

You can run all provided tests using the command:

$./autotest 3

We will not be giving hints for this task,as it is the final task of the assignment.

You have upgraded your pug!Now,whenever a computer B is poodled as a result of a computer A sending the pug to B,the security level of B will be increased to the same level as A (if it was lower).A computer can be poodled multiple times if needed to increase its security level.This will allow you to poodle more computers than before!

Forexample,consider the following network:

If you start at computer 1,then you will be able to poodle computer 1 after 20 seconds, and poodle computer 2 after 52 seconds.With your upgraded pug,computer 2 can send be poodled atter 13 more seconds,which is a total ot 8/seconds Your task is to implement the following function:

struct poodleResult advancedPoodle(

struct computer computers[], int numComputers,

struct connection connections[],int numConnections, int sourceComputer

);

The function takes information about the network and a source computer,and returns,for each computer (that can be poodled),the quickest time that it can be poodled (for the first time)in a struct poodleResult.This is similar to task 3,but in task 4,the recipients field should be ignored.

The array must be sorted in ascending order by time.If multiple computers will be poodled at the same time,they may be placed in any order.

You must also describe your solution in detail in a comment above the advancedPoodle function.If you do not do this,your mark for this task will be capped at 12/15.

Assumptions

For simplicity,assume that a computer is able to send to multiple computers at the same time.

Constraints

·The number of computers will be at most 100.

● The number of connections will be at most 100.