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