Posted: January 5th, 2016

Theoretical Aspects of Computer Science

oursework 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: