这是一篇英国的Algorithms And Heuristics代码代写
Structure of Examination Paper:
There are FIVE pages.
There are FOUR questions in total.
There are no appendices.
The maximum mark for the examination paper is 75 (100% of the module mark). The mark obtainable for each question is 25, and the mark obtainable for part of a question is shown in square brackets alongside the question.
Students to be provided with:
The following items of stationery are to be provided at the start of the examination:ONE answer book.
Instructions to Students:
Answer THREE questions. (Any candidate who attempts more than three questions must clearly indicate which question should not be marked by crossing through their answer to one question. Otherwise the candidate will only be credited with the first three questions attempted.)
The use of a translation dictionary between English or Welsh and another language, provided that it bears an appropriate departmental stamp, is permitted in this examination.
1.
a) Discuss whether the following sentences are true or false.
i) The problem of identifying a minimum spanning tree in an edge weighted graph can be solved in polynomial time. Since this problem generalises the problem of identifying any spanning tree in a graph, the latter problem is also solvable in polynomial time.
ii) If Π1 ∝ Π2 and Π2 is NP-complete, then Π1 is also NP complete. [5]
b) Define the bin packing problem. Using an example, describe the first-fit algorithm and state and prove its approximation ratio. [5]
c) A teacher has n students that she wants to partition into k groups. She has information on the relationships between students in the form of a symmetric matrix X, where Xij is a numerical value indicating how much students i and j dislike each other. The teacher wants to split the students into k groups so that the amount of “dislike” is minimised. Specifically, she wants to minimise the following objective function:
where Sm denotes the set of students assigned to the mth group.
i) Prove that this problem is NP-complete.
ii) Describe a suitable evolutionary algorithm for this problem. [15]
2.
a) State Kuratowski’s theorem and use it to prove the non-planarity of a graph of your choosing. [5]
b) Determine a maximum flow from v1 to v7 in the following graph. You can assume that some flow is already present in the network, as indicated.
[5]
c) Using your solution to Part b), describe how a minimum cut can be determined in an edge weighted graph by using the solution to a corresponding maximum flow problem. [3]
d) A dog rescue centre has m dogs that they want to give away to n families (maximum one dog per family). The centre has collected information about the familiespreferences in a binary matrix X, where Xij = 1 indicates that family i would be willing to adopt dog j, and Xij = 0 otherwise.
i) Describe an algorithm that will maximise the number of dogs that can be given away.
ii) Prove that this algorithm will always produce an optimal solution. [12]
3.
a) Use big-O notation to express the complexities of algorithms that take, in the worst case, the following number of steps for input of size n:
i) ((n – 1)(n – 2) × … × 2 × 1) / 2
ii) 56 + 2n + n2 + 3n3
iii) 2n (lg n) + 1001
iv) n2 × n3 + 2 [2]
b) Two well-known algorithms for searching for an integer x in a list of n integers are linear search and binary search. Compare and contrast these algorithms, and show that they have complexities O(n) and O(lg n) respectively (with regards to the number of integer comparisons performed). [5]
c) Describe Hierholzer’s algorithm for determining Eulerian cycles in an Eulerian graph and prove that this algorithm is exact. [6]
d) Describe an approximation algorithm for the Euclidean travelling salesman problem,provide an example of it operating on a problem instance, and derive its approximation ratio. [4]
e) Describe an application of simulated annealing for the TSP, making sure to include details on your method of representing solutions, cost function, neighbourhood operator(s), and acceptance criteria. [8]
