COMP2521 Data Structures and Algorithms

Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

COMP2521 24T2

Assignment 2

Poodle

Changelog

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

·[11/0700:00] Assignment released

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 ownea by Pooale (tormerly Google),YouLnewb (tormerly You lube)ana 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

lf 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 will complete 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 will produce 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 level 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 0 and n-1 (where n is the number of computers),and transmissionTime will always 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.There willalways be at least one computer.The connections will be 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.

In some or most of the tasks,additional input will be given,such as a source computer or an array of computers.You may assume that all given computer numbers are valid.

Task 1:Path Probing

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.

For example,consider the following network:

Suppose the pathis 0-4-1-5-6.The total amount of time taken to probe this pathis 30+1+80+2+40+1+40+3+90=287 seconds.

connection to the next computer on tne patn,or(2)a computer does not nave permission to communicate with the next computer on the path,as its security level is too low.For example,the  path  5-4-0-1-2-3-6  is  invalid as there is no connection  between  1  and  2. However,you can stillmeasure the time taken before the probe fails,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

The given path will always contain at least one computer.

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.

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

·The number of connections will be at most 250,000. ·The length of the path 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:

1

network-1a.txt

5

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 pathis 0-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

Task 2:Choosing a Source

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:

struct         chooseSourceResult     chooseSource(

struct computer computers[],        int        numComputers,

struct connection connections[],          int          numConnections

);

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.

Constraints

·The  number of computers will  be  at  most  100.

● The number of connections will be at most 100.

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:

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

Task 3:Poodling

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.

Computer

Time poodled

Pug sent to

2

1

3,5

3

5

0

0

7

4

5

8

6

4

9

1

6

11

None

1

16

None


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 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 willcontain 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 will be 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

Task 4:Advanced Poodling

Hints will not be given 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!

For  example,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

pooalea atter 13 more seconas,whicn is a total ot 8/seconasYour 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.

Testing

You can test task 4 by running ./testPoodle with one of the test data files in the task4

directory.The format of the test data file is as follows: ·The first line contains the integer 4.

·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 4:

4

network-4a.txt

1

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

Plan:

-computer 1 poodled at 20 seconds -computer 2 poodled at 52 seconds -computer 0 poodled at 87 seconds

You can run all provided tests using the command:

$./autotest 4

发表评论

电子邮件地址不会被公开。 必填项已用*标注