# Computer Science

Problem Solving

## Problem Solving Terms

Term | Definition |
---|---|

Given |
The initial situation - the starting point |

Goal |
The desired outcome - what you want to achieve |

Resources |
The things that can be used to reach the goal are that impose constraints on how the goal can be reached |

Problem |
A given where it is not obvious how to reach the goal |

## Defining A Problem

A problem is well-defined if there is a,

- clearly defined initial situation
- clearly defined goal
- clearly defined set of resources and constraints
- clear ownership - someone is responsible for arriving at the solution

## The 'U2' Problem

U2 has a concert that starts in 17 minutes and they must all cross a bridge to get there. All four men begin on the same side of the bridge. You must help them across to the other side. It is night. There is one flashlight. A maximum of two people cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each band member walks at a different speed. A pair must walk together at the rate of the slower man's pace.

- Bono - 1 minute to cross
- Edge - 2 minutes to cross
- Adam - 5 minutes to cross
- Larry - 10 minutes to cross

For example - If Bono and Larry walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Larry then returns with the flashlight, a total of 20 minutes has passed and you have failed the mission.

Explain how to get the band to their concert.

Component | Explanation |
---|---|

Given |
U2 have a concert in 17 minutes. They are on the other side of a bridge from where the concert takes place. |

Resources |
You have a single flashlight |

Constraints |
Each band member walks at a different speed, the slowest band member determines the speed of any group crossing. The flashlight must be carried on the journey and cannot be thrown across the bridge. |

Goal |
Get all the band members across the bridge in time for the concert. |

Ownership |
It's your problem, you have to solve it. |

Can you find the answer to this problem?

## Boundaries

A **boundary** is a rule that states what you can and cannot do when working towards the goal. A boundary is a type of constraint. For example, in the U2 problem, we have limited time and limited resources. We cannot throw the flashlight and the men cross at specific speeds and groups cross as quickly as the slowest member.

When solving the problem, we need to understand the constraints before we start. It is also important that we don't impose any constraints that aren't needed because of the way we choose to approach the problem.

## Some Problem-Solving Techniques

There are lots of terms used to describe the approaches you might take to solving a problem. Some are listed below.

Technique | Explanation |
---|---|

Divide & Conquer | Break the problem down into smaller, solvable sub-problems |

Gradient Descent/Ascent | Attempting every step towards the solution (one approach that you might take to the U2 problem) even if it seems to move you temporarily away from the goal |

Means-End Analysis | Setting sub-goals that lead to the solution |

Trial & Error | Select an answer and see if it works, then select another until you happen on the solution |

Brainstorming | Thinking creatively and sifting through ideas for the best ones |

Morphological Analysis | Looking at every possible combination of steps in pursuit of a goal |

Lateral Thinking | Shifting thinking patterns away from the predictable approaches to solving the problem |

Analogy | Looking for a similar problem that has already been solved |

Hypothesis Testing | Assuming an explanation and then testing that assumption |