CS PAPER 2 REVISION
“” = POSSIBLE COME IN THE EXAM
“”= DO NOT KNOW AND MIGHT COME IN THE EXAM
“” = DO NOT KNOW
Computational thinking
• Abstraction: filtering out and ignoring the parts of problems which are not
needed to solve a problem. It is effectively a general overview of the program
with specific details removed, for example, the London Underground map.
• Decomposition: Breaking down a problem into smaller parts which are easier
to understand. These smaller parts can be individually solved as they are easier
to comprehend, for example creating an app would need graphics, audio,
software used to create it, testers, user interface…
• Algorithmic thinking: thinking logically, just as a computer does. Usually works
back from how an intended solution can be reached by working out the steps
needed to get there.
Flowchart symbols
• Lines represent the flow of the program.
• Parallelograms show inputs and outputs.
• A rectangle shows a process, for example, x = x + 10
• A diamond represents a decision, for example, if x > y. Then there would be 2
lines coming from this, one for yes and one for no.
• A rectangle with curved sides represents a terminal, such as the start or end of
the program.
• Rectangle inside rectangle = subroutine
Trace table
A trace table is a table used to show how values in variables change throughout
instructions occurring.
Searches
Linear search
The simplest method of searching through a dataset. It gets the length of a dataset
and sets it counter to 0. It looks at the position of its counter and sees if it matches
the search. If not, the counter is incremented by 1 and the process is repeated
, Linear searches work on unordered lists. On ordered lists, they will take a long time if
the value to search for is a large number.
Binary search
Binary search is used on a dataset of pre-ordered numbers. It works by:
1. getting the midpoint in the list, getting the value, and if it is the target value
the search ends.
2. If not, it will compare the received value. If the value is less than the value to
be found, it will disregard the lower half of the list, as it knows it cannot be
lower than the midpoint value.
3. The remaining part of the list is divided in half again, and the process is
repeated.
4. When the value is found, the search has succeeded.
Note: rounding applies. If there are 7 items in the list, the midpoint would be 3.5. In
this case, the search would start from 4.
Binary searches are much more efficient than linear searches, especially on large
datasets.
In an ordered list of every number from 0 to 100, a linear search would take 99 steps
to find the value 99. A binary search would only require seven steps.
Sorts
Bubble sort
1. Start at the beginning of the list, compare the value at position 1 to the next
one up (at position 2).
2. Swap the positions of these if the second is bigger than the first.
3. Then, move both positions up one, to position 2 and 3.
4. Swap if they are in the wrong order.
5. Repeat until the end of the list.
6. Start back from the beginning and repeat this until it is in order.
Merge sort
Very simplified version:
1. Split the list in half repeatedly until all values are separate
2. Compares two values next to each other and organise.
“” = POSSIBLE COME IN THE EXAM
“”= DO NOT KNOW AND MIGHT COME IN THE EXAM
“” = DO NOT KNOW
Computational thinking
• Abstraction: filtering out and ignoring the parts of problems which are not
needed to solve a problem. It is effectively a general overview of the program
with specific details removed, for example, the London Underground map.
• Decomposition: Breaking down a problem into smaller parts which are easier
to understand. These smaller parts can be individually solved as they are easier
to comprehend, for example creating an app would need graphics, audio,
software used to create it, testers, user interface…
• Algorithmic thinking: thinking logically, just as a computer does. Usually works
back from how an intended solution can be reached by working out the steps
needed to get there.
Flowchart symbols
• Lines represent the flow of the program.
• Parallelograms show inputs and outputs.
• A rectangle shows a process, for example, x = x + 10
• A diamond represents a decision, for example, if x > y. Then there would be 2
lines coming from this, one for yes and one for no.
• A rectangle with curved sides represents a terminal, such as the start or end of
the program.
• Rectangle inside rectangle = subroutine
Trace table
A trace table is a table used to show how values in variables change throughout
instructions occurring.
Searches
Linear search
The simplest method of searching through a dataset. It gets the length of a dataset
and sets it counter to 0. It looks at the position of its counter and sees if it matches
the search. If not, the counter is incremented by 1 and the process is repeated
, Linear searches work on unordered lists. On ordered lists, they will take a long time if
the value to search for is a large number.
Binary search
Binary search is used on a dataset of pre-ordered numbers. It works by:
1. getting the midpoint in the list, getting the value, and if it is the target value
the search ends.
2. If not, it will compare the received value. If the value is less than the value to
be found, it will disregard the lower half of the list, as it knows it cannot be
lower than the midpoint value.
3. The remaining part of the list is divided in half again, and the process is
repeated.
4. When the value is found, the search has succeeded.
Note: rounding applies. If there are 7 items in the list, the midpoint would be 3.5. In
this case, the search would start from 4.
Binary searches are much more efficient than linear searches, especially on large
datasets.
In an ordered list of every number from 0 to 100, a linear search would take 99 steps
to find the value 99. A binary search would only require seven steps.
Sorts
Bubble sort
1. Start at the beginning of the list, compare the value at position 1 to the next
one up (at position 2).
2. Swap the positions of these if the second is bigger than the first.
3. Then, move both positions up one, to position 2 and 3.
4. Swap if they are in the wrong order.
5. Repeat until the end of the list.
6. Start back from the beginning and repeat this until it is in order.
Merge sort
Very simplified version:
1. Split the list in half repeatedly until all values are separate
2. Compares two values next to each other and organise.
