这是一篇关于TFCS分配问题的代码代写

 

Summary

Each group will be assigned one problem from the list below, based on their preferences.

Each problem is a real-world problem in terms of difficulty, even if some of them have been written so as to be entertaining rather than realistic. The aim of the assignment is to practice skills relating to the aims of the unit – problem identification, classification and communication – and to get feedback from peers on the process.

The problems do not have identical difficulty. Some problems are more challenging than normal;groups taking those are more likely to be able to get bonus marks for doing the problem well.

Some problems are easier than others and these are kept as “emergency problems”. A group who is having trouble with their initial problem may switch to such a problem but doing so means a penalty of -25% (so -7.5/30) will be applied to the final marks for the assignment. Do not choose an emergency problem initially.

Questions

1. Curtin Tours

You are asked to write some software to plan tours around Curtin’s Bentley campus, although the aim will be to eventually roll out these tours to other campuses and perhaps universities.

Your input will be a map of the campus, expressed as a directed graph, and the index of a vertex that represents the start of the tour. The tour will go through various parts of the campus and return to the starting spot.

The edges of the map are the paths through Curtin that have been deemed important for the tour, so the route that your software decides is the best one should pass along every such edge. The tour should be optimal if possible, so ideally the tour would only pass along every edge once. If this isn’t possible, your software should announce this and attempt to minimize edge re-use.

2. High School Scheduling (Challenging)

You are employed by a contractor working for the education department. You have been passed the problem of writing an efficient piece of software that will schedule classes for a high school. You will be given the following:

• A list of staff IDs and the subjects that such a staff member can teach (e.g., maths, music). You may assume that the subjects are expressed as integers.

• A list of rooms, their capacity and whether that room serves a special purpose (e.g., computer lab, auditorium). You may assume that purposes are expressed as integers with 0 meaning “no special purpose”.

• A list of classes. You may assume that a class has an integer ID as well as a name and a year level. For example, a class may be 02 “Advanced Mathematics” Yr 7. A class also has a subject(that can be matched with staff capabilities) and a room requirement (which matches room purpose and can be zero).• A list of student cohorts. Every cohort contains an integer representing the number of students in the cohort and the classes that these students are taking in the coming term as well as an integer that is their year level (e.g., 7). The classes are listed using the class IDs.

Your task is to create a timetable that schedules the students of the different cohorts into classes and assigns each class a room and staff member. Obviously, you should avoid anomalies such as clashes in people or rooms.

Note, if the cohort needing a class is larger than the capacity of a room your software will need to split the cohort into groups. All of a cohort can probably take sport at the same time, but subjects such as metalwork probably have only one room with a relatively low capacity, so different groups in a cohort will sometimes need to take different classes at the same time.

3. Rabid Wombat Defence

You have been hired by a shady company that appears to be unduly worried that the town nearest to their not-at-all-secret facilities is going to be over-run by rabid wombats, or perhaps that the inhabitants of said town will turn into such wombats. The person briefing you don’t know and doesn’t want to know.

You are to be given a map of the town (in the form of a graph) but your solution should be general enough to apply to other towns that may be similarly endangered. You are also to be given a budget and a cost of defensive turrets. (Dividing the budget by the cost of a turret will give you the maximum number of turrets that you can afford to place.)

Your job is to locate the placements for the defence turrets at intersections in the town such that all roads in the town are covered by at least one turret. If you cannot do this within the assigned budget,your program should report this but cover as many roads as possible.

4. Unbroken Breaks (Less Challenging)

Plans are being made to prepare for the next bushfire season. Your team is to plan the location of fire breaks that fit the fire agency’s purposes.

You will be given a map whose edges represent likely locations of fire breaks. All of these breaks are connected via other potential breaks, and your job is to decide which breaks should be prioritised. If there is time and weather is sufficient, all breaks will be created but this may not be the case.

The first priority is that the fire service can travel along breaks to wherever there is a fire. That means that all breaks that you select need to be connected (have a common endpoint with another selected break). Exactly one break starts at the first vertex given to you, which is the main entry point of the fire services into the network.

The second priority is that every point can be reached. That means every location (vertex) has to have at least one break adjacent to it selected (represented by one edge that has this vertex as its endpoint).

5. Penta Stars (Emergency Problem)

An advertising company is looking to maximize the exposure to billboards that they advertise on. They only wish to book out billboards when those are on intersections of at least 5 roads.

You will be given a graph whose edges represent roads and vertices represent intersections. You may assume that any road that continues on either side of the intersection counts as two roads for the road count of that intersection.Your application should return an error message if there are no suitable intersections. If there are suitable intersections, return the vertex names of these.

6. On the Circuit (Challenging)

Successful researchers from a university are sent on a tour of several major universities in a country of their choice. They may choose a number of the top universities in that country, depending on the amount of funding they have brought in.

Your team is to write software to plan the least-cost journey for them. You will get the results of another team’s work – they have been scraping websites and will pass you a list of (one-way) flights between cities that the universities are in, their departure and arrival times/dates and their costs.

There is another file with the cost of suitable hotels in each city near the target universities. You will also be given the salary rate of the academic (per day).

The researcher will arrive in the target country at the highest-ranked university on the list and return to that city for the return flight. You do not need to consider the international flight from Australia to and from this city, only the local flights between universities in that country.

Assume that the researcher will stay at every location for at least two days, but if there is no suitable flight then it may be longer. The total cost will include the cost of all flights, the cost of all hotels (you may assuming check-in at 2pm and checkout at 10am) and the salary of the academic.

7. Travelling Salesperson

A company is planning to optimize the travel time of its sales force. Whether inside a city or across a country, the idea is to embrace efficiency by avoiding repetition. You will write software whose input is a directed graph representing locations that a salesperson must visit and the routes between them,as well as a starting node (the first node in the graph, by default).

You are to find a route that starts at the first node and visits every location exactly once before returning to the start – the only location that can be returned to. In this way, management believes,the details of costs and time will be simplified and the problem should be more easily solvable.

8. Penta Tonics (Less Challenging)

A company is looking to set up production locations in an industrial area. For reasons of safety, the production facilities need to be separated, but they also need good connections to each other. The company is initially looking to build five facilities, each producing a different co-dependent product.

While you are not allowed to know what exactly is being produced – that security thing again – you to catch some hints that the product is medicinal in nature.

You will be given a graph that represents the industrial area, with vertices representing different locations and edges representing paths between them. You are to locate a series of five locations that are all mutually inter-connected.

9. Lemmings (Challenging)

Write software that will play a level in Lemmings (the computer game) and be able to beat the level.

You may assume that another team has written an interface that allows you to control the game by selecting a lemming (in the order in which they left, or by distance from start or goal) and performing actions on it. Alternatively, you may assume that you can control the mouse and keyboard as a player would.You may not use non-explainable techniques such as neural networks. You may assume that your software will only play on the earlier levels, which would limit the different lemmings available.

10.Cyber Threats

A large company is wanting an analysis of its computer systems in order to prioritize a defense against cyber threats. You will be given a graph where every node represents a computer system (which could be hardware or software) and an edge represents a connection between two systems that could be exploited if one of the systems were compromised.

Your software should tell the company which the most important system to protect first is – one that is connected to the most other system. If there are multiple systems that are equally important, you can decide which to suggest first.

11.Bits and Addings (Less Challenging)

Create a bitwise addition module. Consider both a general module of this nature and one with a known number of bits (such as a 128-bit adder).

12. Floogal Maps

A race of small aliens is investigating the Earth and wants to be able to explore from point A to point

1. They contract your team anonymously to develop some sensible mapping software since their spaceship’s maps can’t handle roundabouts.

Your job is to write software that takes in a map (in the form of a graph) as well as two vertices A and B on that graph. Your software is to provide the shortest route from A to B as well as two alternate routes that are the next-shortest.

13.Gorillas in the Missed (Emergency Problem)

A university is carrying our research on gorilla researchers. Every year they send teams of observers into the jungle to make notes in shorthand on sightings of gorillas and the gorilla researchers that track them.

The notes end up being a list of symbols – M and F for adult gorilla males and females and m and f for juveniles. A gorilla that is spotted but whose gender is not obvious is marked with a G or g. When a gorilla researcher is spotted, this is marked with a R followed by a 1-digit number to identify the specific gorilla researcher.

Your team will be given the digitized form of these notes – a string of symbols. You are to count up the sightings of gorillas and gorilla researchers and determine whether there are five times more gorilla females as compared to adult males and also whether there is more than one gorilla researcher per hundred gorillas. (These are in terms of sightings for gorillas, not individuals since you don’t have information on individual gorillas.)

14.Beam Me Down

A genius inventor (you know he’s not a mad genius because his card reads “Definitely not mad or evil”) is tasking your team with writing some software to find the best way to link his communication ground stations. You know that this is totally legitimate because he assures you that they definitely don’t communicate with a battery of orbital lasers.

The ground stations also must communicate with each other, though, and this is where the trouble comes in. For various reasons, the inventor doesn’t trust normal communication channels and wishes to use his own. He does have a limited budget, though, so he wants to get the communication done as cheaply as possible.

You will be given a graph to hide the actual locations (vertices) and communication channels (edges) but you will be given a scaled version of the costs for each channel (edge). Even with these safeguards you will be required to sign a NDA promising not to divulge his secrets. It’s somewhat stricter than normal because that “termination” clause isn’t talking about the agreement or your employment.

In essence, there needs to be a path of communication methods between any pair of locations and the overall costs of the communication channels should be minimized.

15. Line graphs

An eccentric mathematician is trying to lay out a range of graphs in a straight line in such a way that

the distance between adjacent vertices is minimized. You will be given a graph and asked to do this.

You can think of this as finding an ordering of vertices such that the greatest cost between any pair of

neighbouring vertices (e.g., v0 and v1, v1 and v2, …) is minimized. You do not need to worry about the costs between other vertices and there are no set start and end vertices. You only care about the greatest cost between any pair of neighbouring vertices, not the total cost.

16.Priorities

An organizational consultant is looking to label a range of tasks with either critical, high, medium, or low priority. She has a list of tasks and their relationships to one another and is trying to assign appropriate priorities. Her main problem is that when two tasks are related directly (i.e., not through another task) then they can’t be set at the same priority level.

Unable to find a suitable assignment of tasks, she recruits your team to check if such an assignment is even possible. You will be given a list of tasks (numbered from 0 to T-1 where T is the number of tasks) and a list or relationships. Each relationship is a pair of tasks and indicates that those two tasks are directly related. Where more than two tasks are directly related, this will be displayed as several pairs to show each binary relationship.

17.Duelling Mosaics 1

Three rival teams of researchers are studying ancient mosaics left behind by some long-forgotten civilization. Both teams believe that the way that tile sections of different colours connect is a key to identifying the origin of this artwork and perhaps also a way to decipher some hidden meaning.

You are hired by one team, who believe that the connect thing to look for is lack of connections between tile sections. You will be given a series of mosaics, abstracted as graphs. Each vertex represents a discrete section of the mosaic, and the edges represent connections between these sections that the researchers have identified.

You are to generate software to find the greatest sub-set of mosaic sections such that none of the sections in the sub-set is connected to any other mosaic in this set.

18.Duelling Mosaics 2

Three rival teams of researchers are studying ancient mosaics left behind by some long-forgotten civilization. Both teams believe that the way that tile sections of different colours connect is a key to identifying the origin of this artwork and perhaps also a way to decipher some hidden meaning.

You are hired by one team, who believe that the connect thing to look for is lack of connections between tile sections. You will be given a series of mosaics, abstracted as graphs. Each vertex represents a discrete section of the mosaic, and the edges represent connections between these sections that the researchers have identified.

You are to generate software to find the smallest sub-set of mosaics such that each connection between mosaic sections has at least one of the connected mosaics in your chosen sub-set.

19.Duelling Mosaics 3

Three rival teams of researchers are studying ancient mosaics left behind by some long-forgotten civilization. Both teams believe that the way that tile sections of different colours connect is a key to identifying the origin of this artwork and perhaps also a way to decipher some hidden meaning.

You are hired by one team, who believe that the connect thing to look for is lack of connections between tile sections. You will be given a series of mosaics, abstracted as graphs. Each vertex represents a discrete section of the mosaic, and the edges represent connections between these sections that the researchers have identified.

You are to generate software to find the smallest sub-set of connectionssuch that each mosaic section is connected to at least one of the connections in your chosen sub-set.

20.Can’t quite put my finger on it…

The head of an organization that deals in moving large numbers of small but valuable goods between locations is looking for a way to select his cut of the goods. He had previously hired a different coding team to select items who’s worth totals to a total value of one tenth of the total worth of all items gained that month, but that team were unable to do so, claiming that sometimes this just isn’t possible.

Your programming team is now being “requested politely” to check on this claim. Your software just needs to determine whether it is possible to make sure a selection of items but doesn’t necessarily need to determine what those items are.

You can expect appropriate rewards if you succeed and really don’t want to fail. If your work backs up the claims of the other team, they will be appropriately grateful as well, since that will mean that they keep all of their fingers, which they are (currently) rather attached to.

You will be given a list of items and the worth of each item. You may assume that all item values are in integers and that the tenth-share amount is also rounded up to an integer.