Paper, Order, or Assignment Requirements

Coursework 2 – Complexity
THEORETICAL ASPECTS OF COMPUTER SCIENCE- COURSEWORK 2

UNDERSTANDING AND OVERCOMING INTRACTABILITY IN ALGORITHMS DESIGN

The partition problem is the task of deciding whether a given set S of positive integers can be partitioned into two subsets S1 and S2 such that both have the same sum. Although the partition problem is NP- complete, there is a polynomial time dynamic programming solution, and there are heuristics that solve the problem either optimally or approximately. For this reason, it has been called “The Easiest Hard Problem”. Source is Wikipedia.
More generally the k-partition problem can be sated as: Given a set of integers S = {x1, x2, …, xn} and an integer k (k >1). Find k subsets of S that constitute a partition for S (no two subsets have an element in common) and such that the numbers in each subset sum to the same amount, or conclude that no such k-partition exists. The problem is NP-Complete. For example, with S = {2, 5, 4, 9, 1, 7, 6, 8} and k = 3, a possible solution would be: {2, 5, 7}, {4, 9, 1}, {6, 8} because all of them sum up to 14

You are required to write a report about algorithms suitable for tackling the 2-partition problem, defined above, and investigate their computational complexities in practice by implementing them. You will be provided with the basic C++ classes to help you and you can use any code you prefer. Please do not include your code or pseudo-code or discussions as an image as you will get 0 for that, do not copy other’s work as this results in failing the coursework.
You report should cover the following:

1. Outline in pseudo-code an Exhaustive Search (Brute Force) solution for the problem (5 marks)
a. Give its time complexity using O-notation b. Discuss its complexity in practice
c. Plot the running time for randomly generated sets A where |A|= n= 10, 20, 30 and 40
2. Outline in pseudo-code a Dynamic Programming solution for the problem (5 marks)
a. Give its time complexity using O-notation b. Discuss its complexity in practice
c. Plot the running time for randomly generated sets A where |A|= n= 10, 20, 30 and 40
3. Outline in pseudo-code Greedy or Random Sampling approaches to solve this problem(5 marks)
a. Give its time complexity using O-notation b. Discuss its complexity in practice
c. Plot the running time for randomly generated sets A where |A|= n= 10, 20, 30 and 40
4. Outline in pseudo-code for Simulated Annealing or Genetic Algorithm for this problem(5 marks)
a. Give its time complexity using O-notation b. Discuss its complexity in practice
c. Plot the running time for randomly generated sets A where |A|= n= 10, 20, 30 and 40
5. Write a conclusion with recommendations on when each method is most suitable (5marks)
a. Reflect on what you have learnt?
b. What could you have done differently?
6. Present your work clearly, using graphs and referencing wherever appropriate (5 marks)