Coursework Description: Sliding puzzles In this coursework, you are supposed to check whether a given directed graph is acyclic. For example, for this graph: The answer would be "no" since there is a cycle b>e>c>b. On the other hand, if the edge between b and c was reversed: The answer would now be "yes" since there is no cycle. In order to answer the question in general, there are different algorithms. We will now have a look at one of them. The sink elimination algorithm A sink in a directed graph is a vertex with no outgoing edges, like vertex f in the examples above. An acyclic graph will always have a sink (can you figure out why this is true?). Of course the converse is not true: a graph with a sink is not necessarily acyclic (the first graph above is a counterexample). But we can use sinks as the basis of an algorithm using this idea: If a graph is acyclic, it has a sink. Also, removing that sink gives us again an acyclic graph (since any cycles would already have existed in the original graph), so there is again a sink, and we can repeat this until the graph is empty. That is, we use the following steps: 1. If the graph is empty, return "yes" (represented by a suitable value like true or 1). 2. If the graph has no sink, return "no" (represented by a suitable value like false or 0 ). 3. Otherwise, remove a sink from the graph and repeat. For example, starting from the first graph above, we would first remove f and then return "no" since there is now no sink. For the second graph, we would remove f,c,e,d,b, a in this order and then return "yes" because there is nothing left. Try to go through this example with pen and paper to make sure you understand how it works. Tasks to be performed: Task 1 (10 marks). Set up a project (Java or C++ ) as you did for the tutorial exercises. Task 2 (20 marks). Choose and implement a data structure which can represent directed graphs. It must provide the necessary infrastructure for the algorithm, such as finding a sink and removing a vertex. If you use one of the graph representations from the lecture and tutorials, consider how efficiently the operations can be performed on each. Task 3 (10 marks). Add a simple parser which can read the description of a graph from an input file. The input files will contain pairs of numbers, one per line, like: 12 31 25 Meaning that there are edged from vertex 1 to vertex 2 etc. Task 4 (20 marks). Implement an algorithm to determine if the given graph is acyclic. You can use the one presented above, but if you are curious and want to do some more research, you could also use a different one. The implementation should produce additional output to show how it obtained the answer. For example, for the sink elimination algorithm, it should print the sinks it has found and eliminated. Task 5 (10 marks). Make your program find and output a cycle in the given graph in case it is not acyclic. Task 6 ( 30 marks). Write a brief report (no more than 3 A4 pages) containing the following: a) A short explanation of your choice of data structure and algorithm. b) A run of your algorithm on two small benchmark examples, one of which is acyclic and the other one isn't. This should include the supporting information as described in Task 4. c) A performance analysis of your algorithmic design and implementation. This can be based either on an empirical study, e.g., doubling hypothesis, or on purely theoretical considerations, as discussed in the lectures and tutorials. It should include a suggested order-of-growth classification (Big-O notation). To be submitted: - Your zipped source code (for Tasks 1 to 5) in Java or C++. Your source code shall include header comments with your student ID and name
