README.md

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.