GCSE AQA COMPUTER
SCIENCE
COMPLETE NOTES
SPECIFICATION:
1. Fundamentals of algorithms- page 2
2. Programming- page 5
3. Fundamentals of data representation- page 8
4. Computer systems- page 18
5. Fundamentals of computer networks- page 32
6. Ethical, legal and environmental impacts of digital technology on wider society,
including issues of privacy- page 41
1
, FUNDAMENTALS OF ALGORITHMS:
REPRESENTING ALGORITHMS
What is an algorithm?
An algorithm is a sequence of steps that can be followed to complete a task.
A computer program is an implementation of an algorithm & that an algorithm is not a
computer program.
What is abstraction?
Abstraction involves removing unnecessary detail from a problem so that you can focus
on the essentials.
EXAMPLE:
All maps- Maps just show a representation of some relevant real world information
What is decomposition?
Decomposition involves breaking down a large problem into smaller sub-problems.
Then the sub-problems can be broken down further until each small task is manageable
ADVANTAGES:
- The problem becomes easier to solve when it consists of a number of small
subtasks or modules
- Some modules may be reusable in other programs, saving development time in
the future
- A team of programmers can work together with each person tackling a different
module
2
,SEARCHING ALGORITHMS
What is linear search?
This is a simple algorithm used to find a value in a list of data. The algorithm runs as
follows:
1. Identify a search term.
2. Look at the first item in the list.
3. Compare the item with the search term.
4. Is the current item the same as the search term? If so, the item has been
found. If not, move to the next item.
5. Repeat from step two until the last item in the list has been reached.
6. If the end of the list has been reached and the search term has not been
found, then the search term is not in the list and the algorithm can stop.
EXAMPLE: This algorithm could be used to search the following list for the number 1:
3, 2, 4, 1, 5
The algorithm would produce:
3, 2, 4, 1, 5 (1 compared to 3 - not found)
3, 2, 4, 1, 5 (1 compared to 2 - not found)
3, 2, 4, 1, 5 (1 compared to 4 - not found)
3, 2, 4, 1, 5 (1 compared to 1- found)
What is binary search?
Values need to be in ORDER
The algorithm runs as follows:
1. Start by setting the counter to the middle position in the list.
2. If the value held there is a match, the search ends.
3. If the value at the midpoint is less than the value to be found, the list is
divided in half, the lower half of the list is ignored and the search keeps to
the upper half of the list.
3
, 4. Otherwise, if the value at the midpoint is greater than the value to be found,
the upper half of the list is ignored and the search keeps to the lower half of
the list.
5. The search moves to the midpoint of the remaining items. Steps 2 through 4
continue until a match is made or there are no more items to be found.
EXAMPLE:This algorithm could be used to search the following list for the number 7:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
In a trace table, this would look like:
What is the difference between binary and linear search?
- Linear search is best used when the data is not in order, or for smaller lists.
- However, when the list is much longer and the data is in order, it is far more
efficient to calculate the indexes needed to perform a binary search
4
SCIENCE
COMPLETE NOTES
SPECIFICATION:
1. Fundamentals of algorithms- page 2
2. Programming- page 5
3. Fundamentals of data representation- page 8
4. Computer systems- page 18
5. Fundamentals of computer networks- page 32
6. Ethical, legal and environmental impacts of digital technology on wider society,
including issues of privacy- page 41
1
, FUNDAMENTALS OF ALGORITHMS:
REPRESENTING ALGORITHMS
What is an algorithm?
An algorithm is a sequence of steps that can be followed to complete a task.
A computer program is an implementation of an algorithm & that an algorithm is not a
computer program.
What is abstraction?
Abstraction involves removing unnecessary detail from a problem so that you can focus
on the essentials.
EXAMPLE:
All maps- Maps just show a representation of some relevant real world information
What is decomposition?
Decomposition involves breaking down a large problem into smaller sub-problems.
Then the sub-problems can be broken down further until each small task is manageable
ADVANTAGES:
- The problem becomes easier to solve when it consists of a number of small
subtasks or modules
- Some modules may be reusable in other programs, saving development time in
the future
- A team of programmers can work together with each person tackling a different
module
2
,SEARCHING ALGORITHMS
What is linear search?
This is a simple algorithm used to find a value in a list of data. The algorithm runs as
follows:
1. Identify a search term.
2. Look at the first item in the list.
3. Compare the item with the search term.
4. Is the current item the same as the search term? If so, the item has been
found. If not, move to the next item.
5. Repeat from step two until the last item in the list has been reached.
6. If the end of the list has been reached and the search term has not been
found, then the search term is not in the list and the algorithm can stop.
EXAMPLE: This algorithm could be used to search the following list for the number 1:
3, 2, 4, 1, 5
The algorithm would produce:
3, 2, 4, 1, 5 (1 compared to 3 - not found)
3, 2, 4, 1, 5 (1 compared to 2 - not found)
3, 2, 4, 1, 5 (1 compared to 4 - not found)
3, 2, 4, 1, 5 (1 compared to 1- found)
What is binary search?
Values need to be in ORDER
The algorithm runs as follows:
1. Start by setting the counter to the middle position in the list.
2. If the value held there is a match, the search ends.
3. If the value at the midpoint is less than the value to be found, the list is
divided in half, the lower half of the list is ignored and the search keeps to
the upper half of the list.
3
, 4. Otherwise, if the value at the midpoint is greater than the value to be found,
the upper half of the list is ignored and the search keeps to the lower half of
the list.
5. The search moves to the midpoint of the remaining items. Steps 2 through 4
continue until a match is made or there are no more items to be found.
EXAMPLE:This algorithm could be used to search the following list for the number 7:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
In a trace table, this would look like:
What is the difference between binary and linear search?
- Linear search is best used when the data is not in order, or for smaller lists.
- However, when the list is much longer and the data is in order, it is far more
efficient to calculate the indexes needed to perform a binary search
4
