A-level Computing/OCR/Unit 2.2 Problem Solving and Programming

Techniques have been developed by computing professionals to solve real world problems and create computer-based solutions. Computational thinking is making use of these techniques to solve problems, with or without a computer. The principle is based on converting a messy problem into something which can be understood, formally represented and solved. This thought process is important as some of the worlds largest problems are complex and difficult to understand. Writing software is also challenging, and the hope is lessons learnt from producing software can be applied more widely to provide solutions.

Programming Constructs

Sequencing

Do one statement after the other

Iteration

Do a set of statements multiple times.

Iteration is either 'count controlled' or 'condition controlled'. Count repeats the section n times, condition waits until a condition has been met before stopping iteration.

Branching/Selection

Do a set of instructions based on conditions e.g If ... Else.

Global and Local Variables

Local

Declared and only available within a module/function/subroutine. Destroyed when subroutine ends.

Global

Declared outside of subroutines at the top of the program. Can be used anywhere within the program. Destroyed when program ends.

A local variable with the same name as the global variable takes precedence when used within the subroutine it is declared in.

Local variables should be used where possible for this reason and also as they use less memory as they are created and destroyed within their subroutine.

Functions and Procedures

Functions and procedures take zero, one or many parameters and carry out a set task. A function then returns a value whereas a procedure does not.

Passing Paramaters

By Value: passes the value to be used in the function.

By Reference: passes the location of the value to be used in the function.

Variables passed by reference could be changed by another part of the program whilst being processed.

In the exam values in pseudocode, unless stated otherwise, are passed by value .

IDE (Integrated Developer Environment)

A program to help the programmer program.

An IDE can provide many features such as:

• Debugger
• Code Editor
• Translators
• Integrated Runtime Environment
• Auto Documentation
• Syntax Highlighting
• Syntax Checking
• Auto Code Completion
• Automatic Indentation
• Error Diagnostics

Recursion

Recursion is when a subroutine (i.e a function) calls itself.

It must contain a stopping condition, if not stopped it must call itself, the stopping condition must be reachable in a finite number of loops.

Recursion Vs Iteration

• Recursion is not very memory efficent
• The place where the recursion takes place must be stored in a stack so it can be 'unwound' once the stopping condition is met. This can take up a lot of memory and even make the computer run out of memory and crash the program.

Mathematical Approaches

Historically, many problems have been solved by applying mathematics, with or without known physical laws. For example, plotting a course to the moon, or estimating the metal required to build a boat. In these cases, a reasonably accurate solution can be obtained using calculations and collected data. Problems begin to arise if the quality of the data is poor or the applied mathematics is not representative of the real world.

Messy Problems

Many problems which must be solved are far less likely to be receptive to a reliable solution. Not all problems can be easily described, due to incorrectly understood underlying issues, data being insufficient or incorrect, or the underlying issues being excessively complex. These problems cause trouble when people think they understand them. This can then lead to poor solutions, which don't solve a problem or can make things worse. Messy problems include biological and ecological systems, the climate, and societal models.

In all these cases, the sheer complexity defeats the normal scientific and mathematical approach. Help in solving messy problems will come from computational thinking and it already has - the use of the shotgun sequencing algorithm to piece together the structure of the human genome is one such example.

Breaking Down Problems

More often, difficult problems can be solved by applying algorithms. These can be helpful, as teaching a problem solving approach to a computer helps understand the problem. Algorithmic solutions can be quickly executed by modern computer systems, and it is possible to resort to trial and error. Algorithmic thinking follows four stages:

1. Understand the Problem - This can be a serious issue - how can we tell if a problem has been sufficiently understood?
2. Formulate the Problem - Produce a concise representation of the problem. The usually involves abstraction and a mathematical solution.
3. Design an Algorithm - Once a clear representation is obtained, an algorithm can be designed to apply this representation.
4. Implement the Algorithm - Write a program which can implement this algorithm.
5. Run and Solve Problem - Run the code and see if it works. Evaluate the output against the requirements.
Top down problem solving

Top Down Problem Solving

This is an approach to problem solving which involves starting with the bigger picture. This is then broken down into sub-problems, which can be represented as black boxes - where the detail is left until later.

This is a way of dividing a large program into modules. Each module solves a single problem, then all the modules are put together. This approach is aided by the realisation that all programs tend to be made up of sequences, iterations and selections.

Object Orientated Programming

OOP is another way in which decomposition is regularly used to solve programming problems. Objects consist of isolated program units containing code and data. These can then be put together to form a complete solution. The objects are an example of abstraction and can be used with or without modification.

Algorithms

The aim of writing algorithms is to produce a process that will work on a generalised representation of a problem, to allow it to work for similar problems. To produce a good algorithm it must be determined that it is correct and efficient. Proving an algorithm is incorrect can be trivial - in just one case it must be shown that it fails. Proving it is correct is far harder. Sometimes a problem is too hard and a good enough solution must be accepted.