代做COMP2521 24T2 Assignment 2 Poodle代做留学生R程序
- 首页 >> Database作业COMP2521 24T2
Assignment 2
Poodle
Changelog
All important changes to the assignment specification and files will be listed here.
[11/07 00: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.
To spread your influence as quickly as possible, your plan has been to poodle computer networks owned by the world's most popular websites. You have already poodled networks owned by Poodle (formerly Google), YouChewb (formerly YouTube) 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 can only send to computers with security level 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 0 (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.
Getting Started
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 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 and the number of connections .
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 -th of these lines (0 ≤ i ≤ n - 1) corresponds to computer .
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.
For example, consider the following network data file:
7 10
2 30
3 40
3 70
3 50
2 80
4 40
1 90
0 1 2
2 3 3
4 5 2
5 6 3
0 4 1
4 1 2
1 5 1
5 2 3
2 6 2
6 3 3
The first line indicates that there are 7 computers and 10 connections. Each of the following seven lines describes a computer. For example, computer 0 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 {
int computerA;
int computerB;
int transmissionTime;
};
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 and (where 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 where index contains the details of computer . There will always be at least one computer. The connections will be given in an array of size (where is the number of connections). The array of connections will not contain duplicate connections. Since connections are bidirectional, this means the connections and 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 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 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 still measure 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.
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.
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.
Hints will not be given for the challenge.
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
0 4 1 5 6
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 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
You can run all provided tests using the command:
$ ./autotest 1
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 will allow 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: 0, 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.
If there are multiple optimal source computers and/or multiple sets of poodled computers as a result, you may return any of them.
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
Your task is to implement the following function:
struct poodleResult poodle(
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 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 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:
3
network-3a.txt
2
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