2023 TFCS Assignment Problems

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 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.

For your problem, you will do the following:

• Turn it into a decision problem if it is not already in that form.

• Classify the problem by computability and complexity.

• Consider how to solve this problem in the most straight-forward manner. This brute-force

solution is likely to not be efficient. You are thinking about a possible algorithm, and can code it up if you like, but there is no coding required since algorithms can be displayed as pseudo- code. If you do decide to code up the solution, you may use any language you wish but all of the code must be generated by your team members.

• Research whether this is a known problem.

o If it is, research best practice for solving this problem. This may mean producing a

solution that is not exact.

o Ifitisnot,attempttoimprovetheinitialsolution.Eitherfindanefficientsolutionor

provide an argument why this may not be possible.

Your group will have three tasks, involving writing a report as if your team were contractors reporting

to an industry client. These three parts add up to the total of 30 marks for the assignment.

1. Create a draft report that covers as many of the above points as possible. (Issues not covered by the unit by that point are obviously not needed for the draft.) This will be submitted to Blackboard as a group in two locations (a submission link and a share location where other students can access it). [Due Sept 22, worth 9 marks.]

2. Each individual student will be given a list of groups to review. The student will review the draft reports from those groups and will do their best to give feedback on them. [Due Oct 5, worth 6 marks.]

3. The groups will take that feedback and use it to improve their solution. The group will also complete the report, based on further progression in the unit. [Due Oct 20, worth 16 marks.]

Your team is allowed to use information that is freely available and tools (LLMs or otherwise) but the final work must be essentially that of the group. That means that if you use a LLM such as ChatGPT, you are responsible for ensuring that all information in that is correct, and that arguments are logical, and references exist and are relevant. If this is not the case, the group may be accused of academic misconduct, and we all want to avoid that.

Please do your best to write in as professional a way as possible – this is not a normal assignment and should be written as if you were submitting it in a professional manner. You may want to look up some professional reporting formats before you start.

Problems

Your group will be assigned one of the following problems, based on your preferences. Two groups will be assigned to each problem.

1. CurtinTours

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 weighted graph, and the index of a vertex that represents the start of the tour. The tour will go through all the key parts of the campus and return to the starting spot.

The vertices of the map are the locations in Curtin that have been deemed important for the tour and the edges connecting them are possible paths between them. The route that your software decides is the best one should pass through every vertex.

The tour guide will be giving a speech to try to influence those on the tour to enrol at Curtin and it is desirable to have as much time for this speech as possible. For this reason, the tour chosen should be the one that the tour be as long as possible, while still only visiting every vertex once.

2. LocationLocation

Your team is tasked by a member of a security team to develop a way of finding possible locations for key incidents. You will be provided with a map snippet and an area map (both anonymised as mixed graphs – ones that may have both direct and undirected edges).

Your software is to determine places in the map where the map snippet fits. In other words, any parts of the larger graph that are identical to the smaller graph.

This will be used by the security team for critical incidents, where they have been able to obtain information from captured footage that give hints to a location, but don’t detail the location itself. For this reason, the software must be as fast as possible, but memory usage isn’t a consideration.

3. Breakup

A company that specialises in corporate takeovers is looking for an automated way to redistribute shipping networks of companies whose assets they are stripping. Your team will be given an undirected weighted graph that represents such a network and an integer n and your software’s task will be to separate the graph into n unconnected components by removing edges.

In order to minimize lost opportunities, a further requirement is that if there are multiple ways to achieve the above aim, your project should remove a set of edges whose total weight is minimal.

4. LocationVocation

A firm of town planners is studying relationships between some of the more iconic locations. You are asked to find similarities in the maps of any two townships as follows: given two maps that represent the layout of the two townships, find the largest cluster of identical roads between the two.

A pair of road clusters are considered identical if their graphs can be relabelled so that one becomes identical to the other – vertices and edges must have identical connectivity.

5. ExpandedEuler

A mathematician is studying Eulerian circuits and asks your team to implement a solution to find a variant. Given an undirected graph, find a Eulerian circuit if one exists. If not, find a circuit that touches every vertex and repeats the least number of edges possible.

6. PipeDream

Given a network whose edges represents pipes (with edge weights giving volume capacity) and whose vertices represent junction between those pipes, find the best path through the network that passes through every junction. The goodness of a path is determined by the weight of the largest pipe in the path with the aim being to minimize that weight.

7. A Cluster of Cliques

Design software that will simplify a graph by grouping all vertices in the graph into the largest possible clique that each is a member of and creating a new graph whose vertices are these cliques and whose edges are the edges between any vertices in the connected cliques.