Download The Subset sum problem
Transcript
1. Introduction 1.1 Reasons for choosing the project I chose this project as I wanted to do a project which gave me scope to design and implement algorithms, especially recursive ones. From my course ‘Functional Programming (CO21)’ last year, I saw that recursion is a very elegant and powerful technique and I wanted to tackle a problem making use of it. I had never constructed a GUI before, so I wanted to choose a project which gave me practice in designing and creating a simple GUI. I also wanted to gain some experience in using JAVA as I had learnt it in my ‘Object Oriented Programming (SO21)‘ course last year, but have never really had to construct a large program using it. I thought that JAVA would also be a good platform to use for creating the GUI. I enjoy watching the Countdown programme on television, trying to solve the numbers game problems faster than the contestants. I wanted to look at the efficiency of any algorithm I produced and see whether there was scope for improving it. I would also be able to use the knowledge learnt in the “Algorithms and Complexity (CO33)” course to assist me in algorithm analysis and complexity. 1.2 Description of Problem The problem is to design at least one algorithm to solve the Countdown problem: Given 6 positive integers and a target integer, the question is whether it is possible to construct an arithmetic expression, using just the standard four operators, which evaluates to the target and uses each of the 6 numbers at most once. 6