AS and A Level OCR AS/A Level Computer Science
Computational techniques (2.2.2)
Navigate to resources by choosing units within one of the unit groups shown below.
Introduction
Overview
Delivery guides are designed to represent a body of knowledge about teaching a particular topic and contain:
- Content: A clear outline of the content covered by the delivery guide;
- Thinking Conceptually: Expert guidance on the key concepts involved, common difficulties students may have, approaches to teaching that can help students understand these concepts and how this topic links conceptually to other areas of the subject;
- Thinking Contextually: A range of suggested teaching activities using a variety of themes so that different activities can be selected which best suit particular classes, learning styles or teaching approaches.
Curriculum content
Overview
Content (from A level)
a) Features that make a problem solvable by computational methods.
b) Problem recognition.
c) Problem decomposition.
d) Use of divide and conquer.
e) Use of abstraction.
f) Learners should apply their knowledge of:
- backtracking
- data mining
- heuristics
- performance modelling
- pipelining
- visualisation to solve problems.
H.B. Meyer Backtracking algorithm animation is a great way to visualise backtracking process. There are also links to other backtracking algorithms but the use of Google translate (from German) might be necessary.
Sorting-algorithms website contains a very visual comparison of different sorting algorithms. We can change parameters and see the differences in performance depending on array sizes and how sorted they are.
Thinking conceptually
Overview
Common misconceptions or difficulties students may have
To make a problem solvable computationally, the analysis and design stages of product development will convert a ‘story’ that a customer has to a specific and unambiguous set of objectives and assumptions/limitations. Activity and data flow diagrams will identify type of variables, data structure and the computational stages that will be required.
The word ‘solution’ refers to the required output, while the ‘problem’ can refer to instances of input data – a file to parse, a string to encrypt, etc. A learner has a set of tools, which can include knowledge of 2d arrays, recursion, API’s and so on. The purpose is to map the problem to the tools, so that the learner could write out a list of tools that will be needed for a particular problem. This process of mapping will inevitably split the main problem into smaller simpler sub-tasks – the process known as ‘decomposition’. This process also allows us to compare the sub-tasks and group them by type, known as ‘abstraction’. Recognising that multiple sub-tasks can be solved in a similar way will prompt the learner to write a self-contained piece of code, a function or a sub, that can be reused on multiple sub-tasks. Often, the sub-tasks are quite similar, for example reading another line in a file, so they can be automated through iteration. If the sub-tasks are really similar but only differ in a parameter (e.g. search upper half of the list vs search the lower half of the list), recursion becomes a powerful tool and gives us the ability to branch while iterating , known as the ‘divide and conquer’ technique used in algorithms like Quicksort. In such algorithms, efficiency can be improved if we can skip some of the processing-‘prune’ it.
Learners need to be aware that the simplest approach of running through every possible combination of inputs can often be avoided through backtracking – which involves setting up a constraint and eliminating obvious dead-end solutions based on that constraint. This is similar to multiple-choice technique in tests where a pupil eliminates obviously wrong options to concentrate on the ones that are possible answers. Backtracking is not a trivial concept but can be made easier through visualisation, for example through graphs and binary trees, or solving popular puzzles like Sudoku or Solitaire. Backtracking together with heuristics helps with particularly hard problems where enumeration (considering every possibility) is not practical. Understanding of heuristics leads us to the solutions that work but we might suspect are not the best; in other words, they satisfy all constraints but are not optimal. Data mining refers to a search for patterns in a set of data. Efficient data mining can utilise heuristics to find patterns; for example, an antivirus program scans all files on a computer looking for virus signatures (patterns); by scanning sensitive system files first, or the Downloads folder, the antivirus program can improve its chances of finding a virus – by using previous knowledge of where viruses tend to enter the system. Visualisation is another way of looking for patterns and the use of infographics and sophisticated graphing theory makes data mining much easier.
Speaking of large sets of data, as an algorithm has to deal with increasing volume of data, it might slow down disproportionately with the increase in data volume. This needs to be predicted with performance modelling before there is a problem. The use of pipelining identifies which processing stages can be carried out concurrently and which ones can’t.
Santa’s Dirty Socks (Computer science unplugged) is another way to illustrate an algorithm.
Rosettacode.org has implementations of most algorithms in different programming languages, so pupils can try a variety of competing algorithms and time them to see how efficient they are.
Thinking contextually
Activity 1: Divide and conquer
Task A: How does Quicksort use the so-called divide and conquer strategy?
[Solution]
Quicksort uses a pivot to split/move the data into smaller parts, the ones larger than pivot get moved to the part above the pivot, the ones that are lower get moved below pivot, and these parts which are recursively further split into smaller parts, thus avoiding making comparisons between all the list items.
[End solution]
Task B: Using RosettaCode.org site (see resource; available under GNU Free Documentation License 1.2.) find Quicksort implementation in your favoured language. Copy it out and supply with annotations that explain what each line does and especially how recursion makes it possible.
Activity 2: Backtracking
Task A: After looking at the definition of computational ‘backtracking’, put the definition in plain English terms and identify a list of three real-life (non-computing) applications of backtracking.
[Solution]
Backtracking is a step in solving a computing problem after all possibilities have been identified, for example all combinations of a chess move. Some of these possibilities can be eliminated if checked against a constraint.
Real-life application 1: Answering multiple-choice questions – they rely on elimination of first, obviously wrong alternatives, and then once the options are narrowed, eliminating the options that are true some times (but not all the time), living the only true answer.
Real-life application 2: Police detectives compile a list of suspects and then eliminate those against a constraint which could be an alibi or the lack of a motive.
Real-life application 3: Employers recruiting new workers have a stack of CVs to go through. By setting a constraint (e.g. an experience with a certain machine), they can eliminate a whole subset of applicants.
Could also consider: Navigating a maze, performing genetic selection – creating a dog breed with particular attributes, applying ‘gut feelings’ (e.g. this doesn’t look right, too good to be true, just run), behavioural experiments.
[End solution]
Task B: Which computational problems can assisted through visualisation?
[Solution]
Binary search can be helped by constructing a binary tree.
[End solution]
Binary search of a sorted list – if a central array element (pivot) is larger than our criteria, we can eliminate the whole half of the array.
Activity 3: Visualising data and data mining
Pilot users were asked to rate the new interface for the upcoming update of the office software which was meant to address the complaints that the previous version was confusing the novices. The users who participated in the study were asked two questions:
On the scale of 1–10 (where 1 is unusable and 10 is fully usable without training or reading the manual) rate the ease of use of the interface’.
‘On the scale of 1–10 (where 1 is not comfortable with computers at all and 10 is expert) rate the level of your general computer knowledge’.
The software supplier is trying to get a sense of how the level of experience correlates with the perception of the new interface.
The responses were as follows:
| Name | Rating of Interface | Level of Computer Experience |
|---|---|---|
| Jack | 2 | 1 |
| Bill | 6 | 5 |
| Norma | 8 | 6 |
| Gulchita | 9 | 8 |
| Aron | 5 | 6 |
| Amir | 1 | 2 |
Task: Develop a program that plots the responses, so that a visual correlation can be established (correlation is stronger when data points are arranged in a narrow cloud and is weaker when that cloud is rounder). You can use this diagram as a guide:
[Solution]
Learners can even use Scratch if Turtle or Small Basic is not available.
They need to work out the algorithm for drawing the axis (optional) and plotting the dots. The dots look better to the casual user if they have labels on them, for example respondents’ names and scores.
In this solution, for simplicity, three arrays were used, instead of a 2d array. The arrays hold respondents’ names, rating of the new interface and level of computer experience, respectively.
Activity 4: Shuffling a list
Task: Given this list, how would you shuffle it to randomise the position of the elements? (Elements must be unchanged.)
ar=[5,2,8,9,5,7,3]
[Solution]
There are multiple approaches to designing this algorithm but the simplest approach is to ‘pop’ (remove) elements from random indices and add them to the end of the list – just like the process of real-life card shuffling. First, we can see how to do it once, then extend to a loop.
Acknowledgements
Overview
OCR’s resources are provided to support the teaching of OCR specifications, but in no way constitute an endorsed teaching method that is required by the Board and the decision to use them lies with the individual teacher. Whilst every effort is made to ensure the accuracy of the content, OCR cannot be held responsible for any errors or omissions within these resources. We update our resources on a regular basis, so please check the OCR website to ensure you have the most up to date version.
© OCR 2015 - This resource may be freely copied and distributed, as long as the OCR logo and this message remain intact and OCR is acknowledged as the originator of this work.