📘
Computer Science
https://filestore.aqa.org.uk/content/summer-2022/AQA-7517-AI-22.PDF
Paper 1
4.1.1.16 Recursive techniques
4.2.1.2 Single- and multidimensional arrays
2.1 ADTs (queues)
4.2.3 Stacks
4.2.4 Graphs
4.2.5 Trees & Tree-traversal
4.3.1 Graph-traversal
4.3.4 Search algorithms
4.3.5 Sorting algorithms
4.3.6 Optimisation algorithms
4.4.1.1 Problem-solving
6.1.3 System software
6.1.4 Operating system
Paper 2
4.5.2 Number bases
4.5.3 Units of information
4.5.4.2 Unsigned binary arithmetic
4.5.4.3 Signed binary using two’s complement
4.5.4.4 Numbers with a fractional part
4.5.4.6 Absolute and relative errors
4.5.4.8 Normalization of floating point form
4.5.6.7 Digital representation of sound
4.5.6.8 Musical Instrument Digital Interface (MIDI)
4.6.1.2 Classification of software
4.6.1.3 System software
4.6.1.4 Role of an operating system (OS)
4.6.2.1 Classification of programming languages
4.6.4 Logic gates
4.6.5 Boolean algebra
7.1.1 Internal hardware components
7.2.1 Stored program concept
4.7.3.3 The processor instruction set
4.7.3.4 Addressing modes
4.7.3.5 Machine code/assembly language operations
4.7.4.1 Input and output devices
4.7.4.2 Secondary storage devices
4.8.1 Moral, ethics, laws
4.9.1 Communication
4.9.1.1 Communication methods
4.9.1.2 Communication basics
Computer Science 1
, 4.9.2.2 Types of networking between hosts
4.9.3.1 Internet & how it works
4.9.4.11 Thin- versus thick- client computing
4.10.1 Conceptual data models and entity relationship modeling
10.2 Relational diagrams
10.3 Database design & normalization
4.10.4 Structured Query Language (SQL)
4.12.1 Functional programming paradigm
4.12.1.3 Function application
4.12.1.5 Composition of functions
4.12.2 Writing functional programs
Paper 1
4.1.1.16 Recursive techniques
A subroutine defined in terms of itself
Recursion characteristics A recursive program
Each recursive solution has two cases – When a subroutine invokes itself, the call is
Base case: A value that has a solution which known as a recursive call.
does not involve any reference to the general Another form of looping. For instance…
case solution
def sumNumbers(numbers):
total = 0
General case: The solution is defined in terms
for i in range(len(numbers)):
of itself for a value of n
total += numbers[i]
The general case gets smaller and smaller
return total
and eventually ends up at the base case – the
answer numbers = [5,7,3,8,10]
print(sumNumbers(numbers))
…will work well for this problem; adding all the
values in an array.
Example of adding values in a list Example of adding values in a list
In a new project file called recursion examples, How does the previous slide relate to the first
write the following code: example we looked at?
def sumNumbers(numbers): def sumNumbers(numbers):
if len(numbers) == 1: if len(numbers) == 1:
return numbers[0] return numbers[0]
else: else:
return numbers[0] + return numbers[0] + sum(numbers[1:])
sumNumbers(numbers[1:]) numbers = [5,7,3,8,10]
numbers = [5,7,3,8,10]
print(sum(numbers))
print(sumNumbers(numbers))
Computer Science 2
, Size of the problem
A recursive call needs some measure of the size of the problem, with each call this should decrease
For example: Factorial
The factorial of a number is defined as the number multiplied by the product of all the numbers
between itself and 0. The factorial of 0! = 1
5! = 120
Factorial example Dry run (trace table)
N! = N * (N – 1)! You may be asked to dry run a recursive
algorithm
5! = 5 x (5-1) x (4-1) x (3-1) x (2-1)
Step through the 1.1.16 Recursion animation
In this instance 5! would be written
and complete the following table:
5! = 5 x (5-1) x (4-1) x (3-1) x (2-1) = 120
n Result Answer
General case is when n > 1
Base case is when n = 1
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
print(factorial(5))
Summary
A recursive procedure is defined in terms of itself
It has a general case which is the calculation It has a base case which will end the function
The recursive program will use a stack to hold values and then pop them of the stack when required
Good for solving mathematical problems
You may well be asked to dry run a recursive algorithm
But why bother?!
System needs a lot of memory to handle recursion but recursive programs are usually shorter than
their non-recursive equivalents. Therefore more time efficient, but not space efficient.
4.2.1.2 Single- and multidimensional arrays
Arrays
An array is an indexed set of related elements. An array must be finite, indexed and must only contain
elements with the same data type.
Array Names = {“George”, “Sue”, “Mo”}
The elements of an array are given an index, which often starts from zero. For example, with the array
shown above, Names(2) would return “Mo” as the first item (“George”) is given the index 0.
Computer Science 3
, The array shown above is a one-dimensional array which could 0 1 2
be visualised with the following table: “George” “Sue” “Mo
Arrays can be created in many dimensions. For example, a two-dimensional array could look like this:
Array Maze = { {Wall, Path, Wall}, {Path, Path, Wall}, {Wall, Path, Wall}}
When an individual element is referenced, the x
coordinate is listed first.
For example, Maze(1,2) would return
Path and Maze(2,1) would return Wall.
2.1 ADTs (queues)
An abstract data structure based on an array
First item added is the first to be removed
Referred to as “first in, first out” abstract data structures
Used by computers in keyboard buffers and in the breadth first search algorithm
Linear queues
Two pointers, a front and rear pointer
Can be used to identify where to place a new item in a queue or to identify which item is at the
front of the queue
Item at the front has been in queue for longest
Emptiness can be detected by comparing the front and rear pointers
Circular queues
Front and rear pointers can move over the two ends of the queue
More memory efficient
Priority queues
Items are assigned a priority
High priority are dequeued before low
If two or more have same priority, items are removed in FIFO order
Frequently used in computer systems
Static and dynamic data structures
Static data structures Dynamic data structures
Fixed in size Change size to store their content
Computer Science 4
Computer Science
https://filestore.aqa.org.uk/content/summer-2022/AQA-7517-AI-22.PDF
Paper 1
4.1.1.16 Recursive techniques
4.2.1.2 Single- and multidimensional arrays
2.1 ADTs (queues)
4.2.3 Stacks
4.2.4 Graphs
4.2.5 Trees & Tree-traversal
4.3.1 Graph-traversal
4.3.4 Search algorithms
4.3.5 Sorting algorithms
4.3.6 Optimisation algorithms
4.4.1.1 Problem-solving
6.1.3 System software
6.1.4 Operating system
Paper 2
4.5.2 Number bases
4.5.3 Units of information
4.5.4.2 Unsigned binary arithmetic
4.5.4.3 Signed binary using two’s complement
4.5.4.4 Numbers with a fractional part
4.5.4.6 Absolute and relative errors
4.5.4.8 Normalization of floating point form
4.5.6.7 Digital representation of sound
4.5.6.8 Musical Instrument Digital Interface (MIDI)
4.6.1.2 Classification of software
4.6.1.3 System software
4.6.1.4 Role of an operating system (OS)
4.6.2.1 Classification of programming languages
4.6.4 Logic gates
4.6.5 Boolean algebra
7.1.1 Internal hardware components
7.2.1 Stored program concept
4.7.3.3 The processor instruction set
4.7.3.4 Addressing modes
4.7.3.5 Machine code/assembly language operations
4.7.4.1 Input and output devices
4.7.4.2 Secondary storage devices
4.8.1 Moral, ethics, laws
4.9.1 Communication
4.9.1.1 Communication methods
4.9.1.2 Communication basics
Computer Science 1
, 4.9.2.2 Types of networking between hosts
4.9.3.1 Internet & how it works
4.9.4.11 Thin- versus thick- client computing
4.10.1 Conceptual data models and entity relationship modeling
10.2 Relational diagrams
10.3 Database design & normalization
4.10.4 Structured Query Language (SQL)
4.12.1 Functional programming paradigm
4.12.1.3 Function application
4.12.1.5 Composition of functions
4.12.2 Writing functional programs
Paper 1
4.1.1.16 Recursive techniques
A subroutine defined in terms of itself
Recursion characteristics A recursive program
Each recursive solution has two cases – When a subroutine invokes itself, the call is
Base case: A value that has a solution which known as a recursive call.
does not involve any reference to the general Another form of looping. For instance…
case solution
def sumNumbers(numbers):
total = 0
General case: The solution is defined in terms
for i in range(len(numbers)):
of itself for a value of n
total += numbers[i]
The general case gets smaller and smaller
return total
and eventually ends up at the base case – the
answer numbers = [5,7,3,8,10]
print(sumNumbers(numbers))
…will work well for this problem; adding all the
values in an array.
Example of adding values in a list Example of adding values in a list
In a new project file called recursion examples, How does the previous slide relate to the first
write the following code: example we looked at?
def sumNumbers(numbers): def sumNumbers(numbers):
if len(numbers) == 1: if len(numbers) == 1:
return numbers[0] return numbers[0]
else: else:
return numbers[0] + return numbers[0] + sum(numbers[1:])
sumNumbers(numbers[1:]) numbers = [5,7,3,8,10]
numbers = [5,7,3,8,10]
print(sum(numbers))
print(sumNumbers(numbers))
Computer Science 2
, Size of the problem
A recursive call needs some measure of the size of the problem, with each call this should decrease
For example: Factorial
The factorial of a number is defined as the number multiplied by the product of all the numbers
between itself and 0. The factorial of 0! = 1
5! = 120
Factorial example Dry run (trace table)
N! = N * (N – 1)! You may be asked to dry run a recursive
algorithm
5! = 5 x (5-1) x (4-1) x (3-1) x (2-1)
Step through the 1.1.16 Recursion animation
In this instance 5! would be written
and complete the following table:
5! = 5 x (5-1) x (4-1) x (3-1) x (2-1) = 120
n Result Answer
General case is when n > 1
Base case is when n = 1
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
print(factorial(5))
Summary
A recursive procedure is defined in terms of itself
It has a general case which is the calculation It has a base case which will end the function
The recursive program will use a stack to hold values and then pop them of the stack when required
Good for solving mathematical problems
You may well be asked to dry run a recursive algorithm
But why bother?!
System needs a lot of memory to handle recursion but recursive programs are usually shorter than
their non-recursive equivalents. Therefore more time efficient, but not space efficient.
4.2.1.2 Single- and multidimensional arrays
Arrays
An array is an indexed set of related elements. An array must be finite, indexed and must only contain
elements with the same data type.
Array Names = {“George”, “Sue”, “Mo”}
The elements of an array are given an index, which often starts from zero. For example, with the array
shown above, Names(2) would return “Mo” as the first item (“George”) is given the index 0.
Computer Science 3
, The array shown above is a one-dimensional array which could 0 1 2
be visualised with the following table: “George” “Sue” “Mo
Arrays can be created in many dimensions. For example, a two-dimensional array could look like this:
Array Maze = { {Wall, Path, Wall}, {Path, Path, Wall}, {Wall, Path, Wall}}
When an individual element is referenced, the x
coordinate is listed first.
For example, Maze(1,2) would return
Path and Maze(2,1) would return Wall.
2.1 ADTs (queues)
An abstract data structure based on an array
First item added is the first to be removed
Referred to as “first in, first out” abstract data structures
Used by computers in keyboard buffers and in the breadth first search algorithm
Linear queues
Two pointers, a front and rear pointer
Can be used to identify where to place a new item in a queue or to identify which item is at the
front of the queue
Item at the front has been in queue for longest
Emptiness can be detected by comparing the front and rear pointers
Circular queues
Front and rear pointers can move over the two ends of the queue
More memory efficient
Priority queues
Items are assigned a priority
High priority are dequeued before low
If two or more have same priority, items are removed in FIFO order
Frequently used in computer systems
Static and dynamic data structures
Static data structures Dynamic data structures
Fixed in size Change size to store their content
Computer Science 4
