Computer Science Notes
Paper 2 - Computational thinking, algorithms and programming
2.1 Algorithms
2.1.1 Computational Thinking
Decomposition means breaking down a problem into smaller, more manageable
sub-problems. Dealing with each small part of the problem is much simpler than trying to
deal with a complex system.
Abstraction is simplifying a problem by removing unnecessary detail in order to focus on
the important features.
Algorithmic Thinking is defining the problem in a series of steps to be carried out in order
to solve a problem. Identifying a precise set of instructions needed to solve a problem.
2.1.2 Designing, creating and refining algorithms
Pseudocode is presenting an algorithm using a structured form of English
,Trace tables
Trace tables involve going through an algorithm or program line-by-line.
Write down whenever a value changes.
A trace table is used to test algorithms and programs for logic errors that appear when an
algorithm or program executes
This algorithm to decide what bus fare rate to change. Complete the trace table for the input
value 7
01 age = int(input(“Enter age ”)
02 if age < 5 then
03 fare = “Free”
04 elseif age < 16 then
05 fare = “Half fare”
06 else
07 fare = “Full fare”
08 print(fare)
09 endif
Line age fare Output
1 7
2 7
4 7
5 7 Half fare
8 7 Half fare Half fare
Types of errors
Syntax errors occur when the grammatical rules of the language have been broken or used
incorrectly
Examples:
Variables not declared properly before use
Incompatible data types
Logic errors occur during run-time and might produce unexpected or incorrect results
Examples:
Division by zero stops the program
Programs may not complete because of loop conditions being incorrect
Incorrect output
Causes:
Conditions that cannot be met in conditional statements
Incorrect algorithms
Incorrect expressions
, 2.1.3 Searching and sorting algorithms
Searching
Linear search
It starts with the first value and checks all values in order until it finds the target item.
If it reaches the end of list without finding the target item, it reports the item has not been
found
Advantages:
Easy to implement
Can search an unordered list
Disadvantages:
Every single value in the list needs to be checked before you can be certain that a value is
not present in a list which is time consuming.
Binary search
Select middle number or left of middle when the list is an even number
Checks if selected number is equal to target number
If searched number is larger, discard left half // if searched number is smaller, discard right
half
Repeat until the number is found or remaining list is of size 1/0 (number not found)
Advantages:
Highly efficient (much faster)
Disadvantages:
The list must be ordered so it cannot always be used
Paper 2 - Computational thinking, algorithms and programming
2.1 Algorithms
2.1.1 Computational Thinking
Decomposition means breaking down a problem into smaller, more manageable
sub-problems. Dealing with each small part of the problem is much simpler than trying to
deal with a complex system.
Abstraction is simplifying a problem by removing unnecessary detail in order to focus on
the important features.
Algorithmic Thinking is defining the problem in a series of steps to be carried out in order
to solve a problem. Identifying a precise set of instructions needed to solve a problem.
2.1.2 Designing, creating and refining algorithms
Pseudocode is presenting an algorithm using a structured form of English
,Trace tables
Trace tables involve going through an algorithm or program line-by-line.
Write down whenever a value changes.
A trace table is used to test algorithms and programs for logic errors that appear when an
algorithm or program executes
This algorithm to decide what bus fare rate to change. Complete the trace table for the input
value 7
01 age = int(input(“Enter age ”)
02 if age < 5 then
03 fare = “Free”
04 elseif age < 16 then
05 fare = “Half fare”
06 else
07 fare = “Full fare”
08 print(fare)
09 endif
Line age fare Output
1 7
2 7
4 7
5 7 Half fare
8 7 Half fare Half fare
Types of errors
Syntax errors occur when the grammatical rules of the language have been broken or used
incorrectly
Examples:
Variables not declared properly before use
Incompatible data types
Logic errors occur during run-time and might produce unexpected or incorrect results
Examples:
Division by zero stops the program
Programs may not complete because of loop conditions being incorrect
Incorrect output
Causes:
Conditions that cannot be met in conditional statements
Incorrect algorithms
Incorrect expressions
, 2.1.3 Searching and sorting algorithms
Searching
Linear search
It starts with the first value and checks all values in order until it finds the target item.
If it reaches the end of list without finding the target item, it reports the item has not been
found
Advantages:
Easy to implement
Can search an unordered list
Disadvantages:
Every single value in the list needs to be checked before you can be certain that a value is
not present in a list which is time consuming.
Binary search
Select middle number or left of middle when the list is an even number
Checks if selected number is equal to target number
If searched number is larger, discard left half // if searched number is smaller, discard right
half
Repeat until the number is found or remaining list is of size 1/0 (number not found)
Advantages:
Highly efficient (much faster)
Disadvantages:
The list must be ordered so it cannot always be used
