CS1PR16 PROBLEM SOLVING
Programming is a process of problem solving. In order for a computer to be able to solve a problem it
must be translated from natural language into an algorithm.
The difference between natural language and an algorithm is called a semantic gap – the difference
between 2 descriptions of an object using different linguistic representations.
General steps of problem solving:
The purpose of writing a program is to solve a problem. In order to be able to do that, we must:
Understand the problem
Break the problem down into manageable pieces
Design a solution for each of the pieces
Analyze the complexity of the algorithm – it may be necessary to break the problem down more
Consider alternatives and refine the solutions – first thought may not always be the best one
Implement the solution – the pieces come back together at this stage
Test the solution and fix any problems that still exist
Many software projects fail because the developers didn't fully understand the problem. We need to
avoid ambiguities and uncertainties. As the problems become larger, the solution must be organized
into manageable pieces.
Algorithm – a set of steps that define how a task is performed.
The steps must be ordered – they are to be performed in a specified order
They must be doable – if a step is not doable it means you haven't broken it down enough
An algorithm must have an end – it can't be processing forever
Properties of an algorithm:
o Correct – always leads to the correct outcome, deterministic – the same input always
leads to the same output
o Efficient – can be measured in terms of resources
o Unambiguous – solves the problem in a general way. An algorithm is independent of the
means used to implement it.
The ways to describe an algorithm:
Natural language
Pseudocode – semi-formal representation of an algorithm
Flowcharts – visual representation using symbols. There is a defined syntax:
Programming language
Problem solving strategies
Ask questions: what, why, where and when:
o What is the input data and where is it coming from?
o What does the data look like? - a number of projects failed because people didn't
understand the data they were working with (e.g. mixed up metric and imperial system)
o Is the data sensible? - especially if you get it from the user
o Is it within the correct range?
o What should the output look like?
o How many times is the process going to be repeated?
o What error conditions may come up?
Look for familiar things – if the solution already exists, use it – that's what libraries are for
Means-ends analysis – beginning and end states are often given
o You need to figure out the steps needed to get from the beginning to the end, then
work out the details
Divide and conquer – break down large problems into smaller problems which are easier to
solve – this technique is very commonly used
There are 3 basic programming constructs:
Sequence – performing one step after the other
Selection – decision making, also called conditional statement – used to make yes/no decisions
Iteration – looping; a combination of sequence and selection that can repeat steps
Any problem, regardless of how complex, can be broken down into those constructs.
