AQA A-Level Computer Science Paper 1 (Python)

Variable

A memory location that can be used to store data which can be updated while the code is running.

Constant

A memory location that can be used to store data which cannot be updated whilst the code is running.

Modular Programming

The breaking down of a major task into smaller subtasks.

Subroutine

A set of instructions with a callable name.

Function

A subroutine which always returns a value when called.

Procedure

A subroutine which may return a value when called.

Subroutine Advantages

Avoids repeating code, enables sub-testing, enables top-down development, allows for modular programming.

Parameters

Data passed into subroutines.

Recursion

A subroutine which calls itself.

Base Case

A condition that stops recursion.

Local Variables

Variables within a single subroutine that can only be used in that subroutine.

Local Variables Advantages

Keeps the subroutine self-contained.

Local Variable Disadvantages

Only exists whilst the subroutine is executing, only accessible within the subroutine, local and global variables with the same name can be misidentified.

Global Variables

Defined in the main program and can be used in any subroutine called from the main program.

Built-in Functions

print(), min(), max(), sorted(), int()

Object-Orientated Programming

Defines separate objects that have their own associated attributes and methods that can be easily grouped together in a logical way.

Attributes

OOP variables that define characteristics of the object.

Methods

OOP subroutines that define the actions of the object.

Class

A set of objects which share a common data structure and common behaviour.

Object

An instance of a class which uses attributes and methods from the class.

Constructor

Constructs the attributes of the class automatically without being called.

Self

Reference to the bound object.

Instantiation

The creation of objects from a class.

OOP Advantages

Produces reusable code and objects, data is protected, code produced contains fewer errors, solutions are easier to understand, easier to enforce design consistency.

Inheritance

Classes can inherit attributes and methods from other classes.

Super-classes

A class from which another class can inherit from.

Sub-class

A class which inherits from another class.

Super Constructor

Sets up the parent class inside the child class.

Composition

If the containing object is destroyed, so are the objects it contains.

Aggregation

If the containing object is destroyed, the objects it contains are not destroyed.

Encapsulation

Grouping data and subroutines to make a program easier to understand.

Public Attributes and Methods (+)

Attributes and methods that can be accessed from outside of the class. All methods tend to be public.

Protected Attributes and Methods (_)

Attributes and methods that can be accessed within its class and by subclasses. Most attributes should at least be protected.

Private Attributes and Methods (__)

Attributes and methods that can only be accessed from within its class. Some attributes, especially those holding personal information, should be private.

Getters

Methods that ‘get’ a private attribute value.

Setters

Methods that ‘set’ the private attribute value.

Polymorphism

A method used in a class hierarchy can be used differently in each class.

Overriding Polymorphism

Methods that are defined with the same identifier in the superclass, but have a different implementation in a subclass.

Overloading Polymorphism

Allows multiple methods that require different parameters to use the same name.

Object Storage

Objects are stored in a dictionary, which can be accessed using the code self.__dict__

Class Attributes

An attribute for the whole class, not just the object. Often used to keep track of how many objects have been instantiated. Called using class.classvariable.

Static Method

Does not need to have self in the parameter list because it is designed to be invoked through the class and not an object.

Abstract Method

Consists of only a signature and no implementation used to specify that a subclass must provide an implementation of the method.

Virtual Method

Implementation can be redefined by subclasses.

OOP First Principle — Encapsulate What Varies

Data inside the object should only be accessed through an interface (the object’s methods).

OOP Second Principle — Favour Composition over Inheritance

Composition is less rigid than the relationship that exists in inheritance. An object might be ‘composed’ of several other objects, but it would not necessarily make sense to say that it inherited the characteristics.

OOP Third Principle — Program to Interfaces, not Implementation

Focus your design on what the code is doing, not how it does it.

Elementary Data Type

The simplest type of data, such as Boolean, char, float, or integer.

Composite Data Type

A data type made up of smaller forms of data, such as array or string.

Abstract Data Type

A logical description of how data is viewed and the possible operations done on the data.

Queue

A FIFO data structure.

Queue Operations

Enqueue, dequeue, isempty, isfull

Circular Queue

An algorithm that reuses the spaces that have been freed by dequeuing items from the front of the array.

Priority Queue

A queue that allows some items to ‘jump’ the queue is they have an associated priority.

Dynamic Data Structures

Allocates and deallocates memory from heap, avoiding overflow errors.

Heap

An area of memory especially allocated for use by dynamic data structures.

Static Data Structures

Cannot allocated or deallocate memory, as it is fixed in size.

Stack

A LIFO data structure.

Stack Operations

Push, pop, peek, isfull, isempty

Call Stack

A system level data structure that provides the mechanism for saving local variables, passing parameters, and return addresses to subroutines.

Graph

An abstract data structure that represents complex relationships.

Directed Graph (Digraph)

A graph where routes are uni-directional or bi-directional.

Undirected Graph

A graph where all routes are non-directional.

Weighted Graph

A graph where edges have a cost of traversal.

Unweighted Graph

A graph where edges have no cost of traversal.

Adjacency Matrix

A table where each row and column represents a table, and the item at [row, column] indicates a connection.

Adjacency Matrix Advantages

Convenient to work with, adding edges is simple.

Adjacency Matrix Disadvantages

A sparse graph with not many edges will leave most of the cells empty, wasting memory.

Adjacency Matrix Uses

When there are many edges between vertices, edges are frequently changed, or when the presence of edges needs to be tested.

Adjacency List

A list or dictionary of nodes, where the value is a list of adjacent nodes.

Adjacency List Advantages

Only uses storage for connections that exist, a good way of representing a large, sparse graph.

Adjacency List Disadvantages

Hard to change edges.

Adjacency List Uses

When there are few edges between nodes, edges are rarely changed, and the presence of edges does not need to be tested.

Page Rank Algorithm

Google uses a directed graph of web pages.

Depth-first Graph Traversal

Traversing a graph by going as far down a path as possible before backtracking and going down the next path.

Depth-First Uses

Navigating a maze.

Breadth-first Graph

Traversing a graph by going to all the adjacent nodes of the current node, and all the adjacent nodes to those.

Breadth-first Uses

Shortest path for an unweighted graph.

Dijkstra’s Shortest Path Algorithm

Utilises a breadth first search and a priority queue to determine the shortest path between two nodes.

Tree

A connected, undirected graph with no cycles.

Rooted Trees

One node is identified as a root, and every node except the root has one unique parent.

Node

An item of data.

Edge

Connects two nodes.

Root

A tree node that has no incoming edges.

Child

A node connected to a node in the level above it.

Parent

A node connected to a node in the level below it.

Subtree

A set of nodes and edges comprised of a parent and all of its descendents.

Leaf

A node that has no children.

Binary Tree

A rooted tree in which each node has a maximum of two children.

Pre-order Tree Traversal

Visit the root, then traverse the left sub-tree, then the right sub-tree, marking off nodes as you pass their left side.

Pre-order Tree Traversal Uses

Copying a tree.

In-order Tree Traversal

Traverse the left sub-tree, then visit the root, then traverse the right sub-tree, marking off nodes as you pass their bottom side.

In-order Tree Traversal Uses

Searching a binary tree, outputting the contents in ascending order.

Post-order Tree Traversal

Traverse the left sub-tree, then traverse the right sub-tree, then visit the root, marking off nodes as you pass their right side.

Post-order Tree Traversal Uses

Infix to Postfix conversions, producing a postfix expression from a tree, emptying a tree.

Tree Traversal Time Complexity

O(log n) — The execution time grows logarithmically with the input size, meaning it has an efficient time.

Infix Notation

Equations are written as they are usually.

Prefix Notation

Equations are written with the operators first, then the operands.

Postfix Notation

Operands are written first, then operators.

Hash Table

A data structure that uses a hashing algorithm and MOD table size to associate unique keys with values.