Consider the following problem: Directed Hamiltonian Cycle Problem (DHCP) Given a directed graph, decide if it contains a path that visits every vertex exactly once, and terminates at the same vertex at which it started. Investigate the computational complexity of this problem in two stages:

1. Individually or in a small group, develop code to try and solve the DHCP using exhaustive search, a greedy method, a meta-heuristic, and special algorithms for special case. You will be guided through lab exercises, but you are encouraged to improve on these. You should test each method on DHCP instances with varying parameter sizes (number of vertices, structure of the graph, etc.), record (1) the time taken, and (2) how close the optimization methods get to an optimal solution. You need to test over a large range of randomly generated DHCP instances, and produce averaged results for each tested parameters set.
2. Use a Jupyter Notebook (jupyter.org and “Anaconda Python 3.4” through Apps Anywhere) to run your computational experiements, and write a report based on them. You should analyse and comment on these experimental results. Your report should be structured as follows: (10 marks) 1) Definition of the problem (Decision, computation, and optimization versions). Discuss their complexity class membership (P, NP, NP-complete, NP-hard, etc.). Fix the notation for the rest of the report. (10 marks) 2) Discuss the testing methodology, and how the random instances are generated/sampled.

3. Report on the performance of the methods used to solve the problem. For each method, give its pseudo-code, its time complexity using O-notation, and discuss its performance in practice (e.g. timing and/or accuracy plot). (10 marks) a) Exhaustive search. (10 marks) b) Greedy heuristic. (10 marks) c) Meta-heuristic. (10 marks) d) Special cases that are tractable in polynomial time. (10 marks) 4) Conclusion with recommendations on when each method is most suitable. (10 marks) 5) Reflection. (What have you learnt? What could you have done differently? If you collaborated on the coding then specify your contribution clearly.) Marks are also allocated for: (10 marks) 1. Presentation. Good use of English (spelling, grammar and clarity of language). Good use of visual aids (graphs, tables, etc.). (10 marks) 2. Referencing. Appropriate selection of academic references; correct referencing the CU Harvard referencing style. Show the list of references at the end of your report.