Algorithmic Problem Solving :
- Put you name and student ID as a comment on each le (and in the footer of the discussion le).
- Make sure your programs strictly follow the instructions given at the end of each task.
- Save your les into a single folder called assignment and create a zip le of this folder called yourFirst-Name_yourLastName.zip.
- Submit your zip le containing your solution to Moodle. Make sure that your assignment is not in Draft You need to click Submit to successfully submit the assignment.
- Your assignment will not be accepted unless it is a readable zip
- Your submitted zip le should only include the following les:
- pdf (or greedy.rtf if you prefer)
- any other les included will not be assessed
- Students who do not attend their interview will have one week from the release of assignment results to make alternate arrangements, otherwise they shall receive 0 marks for the assignment
- Last year, many students were detected by the plagiarism detector and almost all got zero mark for the assignment and, as a result, failed the unit. Helping others is NOT okay. Please do not share your solutions with others. If someone asks you for help, ask them to visit us during consultation hours for help
- Your demonstrator will check in on your progress on the assignment in week 8, make sure you have something to show them as they will use the opportunity to give you some valuable feedback on your work (which may help you improve your nal mark!)
- You are not allowed to import any Python library or module and should not be using any inbuilt python functions that simplify the tasks you are told to implement.
- Your program will be checked against a number of test cases. Do not forget to include comments in your code explaining your algorithm. If your implementations have bugs, you may still get some marks based on how close your algorithm is to the correct algorithm. Also, ma the boundary cases properly.
- This assignment requires an understanding of greedy algorithms and brute force solutions to problems in order to complete. These are covered in weeks 5 and 6 respectively but you can begin working on the assignment as soon as it is released.
- This assignment is non-trivial and is designed to give you the opportunity to practice a large component of the unit content. It’s okay if you can’t nish everything, but try the best you can. You are strongly encouraged to start as early as possible and get assistance in consultation sessions and from your tutors and demonstrators.
- It is possible that you may like to revisit this assignment as we cover more in the unit as you may discover other better ways of approaching the tasks given.
Marks: This assignment has a total of 100 marks and contributes to 18% of your nal mark. Late submission will have 10% o the total assignment marks per day (including weekends) deducted from your assignment mark, i.e., 10 marks per day. So, if you are 1 day late, you will lose 10 marks. Assignments submitted 7 days after the due date will normally not be accepted.
Graph problems: 100 marks
- Code readability (Non-trivial comments where necessary and meaningful variable names) 10 marks
- Code decomposition (appropriate decomposition and avoiding duplicate code or duplicate functions) 10 marks
- reading from a le 5 marks
- writing to a le 5 marks
- intersection of two graphs 5 marks
- union of two graphs 5 marks
- dierence of two graphs 5 marks
- supergraph 15 marks
- connectivity 15 marks
- greedy cheapest connection 10 marks
- greedy discussion 5 marks
- bruteforce cheapest connection 10 marks
Graphs apply to many problems and are common in issues of connectivity and networks. For this assignment we are imagining ourselves as professional programmers already and have taken on a client, a Ms. Fathima Arda Moor. Ms. Moor runs a large wheat farm in western Victoria (Australia) and has recently purchased some of her neighbouring farms; she wishes to combine together the water systems to allow for more e‑cient irrigation of each farm’s crops.
Fortunately each of these farms had their piping systems mapped in blueprints (which are relatively easy to digitise); Unfortunately some of these farms include multiple separate piping systems for handling irrigation so she has turned to you for help.
- Simple Graph-Joining
In this task you will be considering dierent ways of combining two graphs together into a single graph. This will help Fathima connect together some of the more straightforward piping systems between farms.
For each of the problems in this task, you can expect to receive weighted graphs in adjacency matrix format (with the weight representing the relative likelihood of that pipe breaking), for example the graph G (found in
Figure 1: graph G
corresponds to the adjacency matrix:
1.1 Interpreting le input
The assignment will include several example graphs to test your code with, each will be found within their own le with each le representing an adjacency matrix and the format followed is as such:
space separated values for edges from firstVertexName
space separated values for edges from lastVertexName
For the example graph G, the le would look like so:
0 1 2 1 9
1 0 0 6 0
2 0 0 15 2
1 6 15 0 7
9 0 2 7 0
Prepare a python program ( graphFileOps.py ) which accepts a le name and produces an adjacency matrix based on the data in that le. Make sure that you can identify vertices by their name (which need not be one character) and be sure to close the le when you are done with it.
1.2 Writing to a le
Later on in this assignment you will be required to write adjacency matrices to a le. Add to your existing python le (graphFileOps.py ) a program which accepts a le name and a table representing an adjacency matrix which writes the adjacency matrix to that le. This should follow the same format as the input les.
A good way to test this would be to read in one of the input les and write to another le. If you code is correct, these les should be identical. Be sure to close the le when you are done with it.
Write a python program (intersection.py ) which accepts two le names (representing graphs) and nds the intersection of both graphs. In this context, the intersection refers to set of vertices and edges that are shared by any two graphs. Where an edge is shared but has dierent weights in each graph, the weight of the edge in the intersection graph is the larger of the weights. Where an intersection includes a vertex with no edges, that vertex is removed from the intersection
For example consider also the graph H (found in H.txt) below:
Figure 2: graph H
If we were to take the intersection of the two graphs G and H, we would receive the following graph ( G \H)
G and H share the following vertices: a,c,w and Q
- and H share the following edges: < a,c>,<a,w> and <c,w>
As the intersection does not include any edges connecting Q, the vertex Q is not included in the intersection
Once your program has determined the intersection between two graphs, it should write the resultant graph to a le; this le should be named in the following format: graphOne_and_graphTwo.txt so for example if graph G and H were input (from les G.txt and H.txt respectively), the resultant graph would write the following:
0 19 1
19 0 6
1 6 0
to the le named G_and_H.txt
The intersection graph will allow Ms. Moor to remove the most unreliable pipes from the system where they are duplicated.