AQA A-Level Computer Science Paper 1 (Python)

Data Type

An attribute of data that determines how the compiler will use the data in a program.

Language-Defined Data Types

A primitive data type provided by a programming language.

User-Defined Data Types

Custom data types designed by the user by combining existing data types for the bespoke needs of their system.

Non-Composite User-Defined Data Types

User-defined data types that contain only one data type.

Non-Composite User-Defined Data Types Examples

Enumerators — binds a group of names to constant values (e.g. January = 1 etc.).

Pointers — refers to a location in memory.

Composite User-Defined Data Types

User defined types that contain more than one data type.

Composite User-Defined Data Types Example

Records — references other datatypes, similar to how an OOP object has attributes of different data types.

Sets — unordered, iterable, mutable, and contain no duplicate data types.

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.

List

A collection of elements with an inherent order

Random.randint(1,3)

Determines a random integer from 1 to 3.

Random.choice([“1”, “2”, “3”])

Determines a random item in a list.

Random.random()

Determines a random float from 0 to 1.

Random.uniform(1,3)

Determines a random float from 1 to 3.

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 value that has a solution which does not involve any reference to the general case solution. (A condition which 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()

Procedural-Oriented Programming

A programming model which is divided into procedures.

Procedural-Orientated Programming Advantages

Easier to debug, reduced repeated code, subroutines can be saved into libraries.

Procedural-Orientated Programming Disadvantages

Focus is on completion , not integrity.

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

A property or characteristic of an object (OOP).

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.

Constructor

Constructs the attributes of the class automatically without being called.

Self

Reference to the bound object.

Instantiation

An object is defined based on 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

The relationship between two object types in which one ‘is a kind of’ the other and shares some of its properties or behaviours.

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.

Association

The relationship between two classes, categorised into either composition or aggregation.

Composition

A type of association where the composite object has ownership of the objects within it. The objects that are part of the composite objects have a lifecycle determined by the composite object. If the composite object ceases to exist then they too will cease to exist.

Aggregation

A type of association where the aggregated object has weaker form of association with the objects that it is aggregating that is the case with composition. These objects have an existence independent of the aggregated object and can continue to exist even after the aggregated object is disposed of.

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

Giving an action one name that is shared up and down a class hierarchy. Each class in the hierarchy implements the action in a way appropriate to itself.

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 data type whose properties are specified independently of any particular programming language.

Queue

A FIFO abstract data type

Linear Queue

Elements join the queue at one end and leave the queue at the other.

Queue Operations

Enqueue, dequeue, isempty, isfull

Circular Queue

When the array element with the largest possible index has been used, the next element to join the queue reuses the vacated location at the beginning 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 abstract data type.

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.

Stack Frame

The locations in the stack area used to store the values referring to one invocation of a routine.

Graph

An abstract data structure that represents complex relationships.

Directed Graph (Digraph)

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

Undirected Graph

A graph where all edges 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.

Simple Graph

A graph without multiple edges in which each edge connects to two different vertices.

Cycle

A closed path in which all edges are different and all the immediate nodes are different.

Degree of a Node

The number of neighbours for a specific node.

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.

Heuristic

An approach that uses experience to make informed guesses that assist in finding a polynomial time solution to an intractable algorithmic problem.