AQA

General information

On average it takes our students 12 months to complete this course, however you have up to 24 months.

Study completely online using our award-winning learning platform, My CS Insideout.

Specification

Representing algorithms

  • the term algorithm
  • the term decomposition
  • the term abstraction
  • the systematic approach to problem-solving
  • inputs, processing and outputs
  • the purpose of simple algorithms

Efficiency of algorithms

  • algorithm usage
  • algorithm efficiency

Searching algorithms

  • Linear searching algorithms
  • Binary searching algorithms

Sorting algorithms

  • Merge sorting algorithms
  • Bubble sorting algorithms

  • theoretical understanding of programming
  • practical understanding of programming

Data types

  • variable declaration
  • constant declaration
  • assignment
  • iteration
  • selection
  • subroutine (procedure/function)
  • definite (count controlled)
  • indefinite interaction (condition controlled)
  • nested selection
  • nested iteration
  • meaningful identifier

Arithmetic operations in a programming language

  • addition
  • subtraction
  • multiplication
  • real division
  • integer division, including remainders.

Relational operations in a programming language

  • equal to
  • not equal to
  • less than
  • greater than
  • less than or equal to
  • greater than or equal to

Boolean operations in a programming language

  • NOT
  • AND
  • OR

Data structures

  • the concept of data structures
  • Use arrays (or equivalent)
  • Use records (or equivalent)

Input/output

  • obtain user input from the keyboard
  • output data and information from a program to the computer display

String handling operations in a programming language

  • length
  • position
  • substring
  • concatenation
  • convert character to character code
  • convert character code to character
  • string conversion operations:
    • string to integer
    • string to real
    • integer to string
    • real to string

Random number generation in a programming language

  • The use of random number generation

Structured programming and subroutines (procedures and functions)

  • the concept of subroutines
  • the advantages of using subroutines
  • parameters of subroutines
  • local variables
  • structured approach to programming

Robust and secure programming

  • data validation routines
  • simple authentication routines
  • testing
  • types of errors
  • types of test data

Number bases

  • decimal (base 10)
  • binary (base 2)
  • hexadecimal (base 16)
  • The use of binary to represent all data and instructions
  • The use of hexadecimal in computing

Converting between number bases

  • the use of binary to represent whole numbers
  • the use of hexadecimal to represent whole numbers
  • convert in both directions between:
    • binary and decimal
    • binary and hexadecimal
    • decimal and hexadecimal

Units of information

  • bit
  • kilobyte
  • megabyte
  • gigabyte
  • terabyte

Binary arithmetic

  • binary addition
  • binary shift

Character encoding

  • 7-bit ASCII
  • Unicode

Representing images

  • pixel
  • image size
  • colour depth
  • image file sizes calculation
  • Conversion of binary data into a bitmap image
  • Conversion of a bitmap image into binary data

Representing sound

  • analogue sound
  • digital sound
  • sampling rate
  • sample resolution
  • sound file sizes calculation

Data compression

  • Lossy compression
  • Lossless compression
  • Huffman trees
  • Run-length encoding (RLE)

Hardware and software

  • Hardware
  • Software

Boolean logic

  • Logic gates and truth tables:
    • NOT
    • AND
    • OR
    • XOR
  • logic circuit diagrams
  • simple Boolean expressions

Software classification

  • system software
  • application software
  • operating systems (OS)
  • utility programs
  • OS management of the:
    • processor(s)
    • memory
    • input/output (I/O) devices
    • applications
    • security

Classification of programming languages and translators

  • low-level language
  • high-level language
  • machine code
  • assembly language
  • types of program translator:
    • interpreter
    • compiler
    • assembler

Systems architecture

  • main memory
  • central processing unit (CPU)
  • Von Neumann architecture
  • arithmetic logic unit
  • control unit
  • clock
  • register
  • bus
  • clock speed
  • number of processor cores
  • cache size
  • the Fetch-Execute cycle
  • types of memory within a computer:
    • RAM
    • ROM
    • Cache
    • Register
  • secondary storage
  • solid-state storage
  • optical storage
  • magnetic storage
  • cloud storage
  • embedded system

computer network

  • Personal Area Network (PAN)
  • Local Area Network (LAN)
  • Wide Area Network (WAN)
  • wired or wireless networks

Network topologies

  • LAN networking topologies:
    • star topology
    • bus topology

Network protocols

  • network protocols:
    • Ethernet
    • Wi-Fi
    • TCP (Transmission Control Protocol)
    • UDP (User Datagram Protocol)
    • IP (Internet Protocol)
    • HTTP (Hypertext Transfer Protocol)
    • HTTPS (Hypertext Transfer Protocol Secure)
    • FTP (File Transfer Protocol)
    • email protocols:
      • SMTP (Simple Mail Transfer Protocol)
      • IMAP (Internet Message Access Protocol)

Network security

  • methods of network security:
    • authentication
    • encryption
    • firewall
    • MAC address filtering
  • the 4 layer TCP/IP model:
    • application layer
    • transport layer
    • internet layer
    • link-layer

  • the term cyber security
  • the main purposes of cyber security

Cyber security threats

  • social engineering techniques
  • malicious code (malware)
  • pharming
  • weak and default passwords
  • misconfigured access rights
  • removable media
  • unpatched and/or outdated software
  • penetration testing

Social engineering

  • the term social engineering
  • forms of social engineering:
    • blagging (pretexting)
    • phishing
    • shouldering (or shoulder surfing)

Malicious code (malware)

  • the term malware
  • forms of malware:
    • computer virus
    • trojan
    • spyware

Methods to detect and prevent cyber security threats

  • biometric measures (particularly for mobile devices)
  • password systems
  • CAPTCHA (or similar)
  • using email confirmations to confirm a user’s identity
  • automatic software updates

Relational databases

  • the concept of a database
  • the concept of relational database
  • database concepts:
    • table
    • record
    • field
    • primary key
    • foreign key
  • data inconsistency
  • data redundancy

Structured query language (SQL)

  • the commands:
    • SELECT
    • FROM
    • WHERE
    • ORDER BY…ASC | DESC
  • inserting data into a relational database

  • ethical, legal and environmental impacts and risks of digital technology
  • data privacy issues
  • ethical, legal and environmental issues within:
    • cyber security
    • mobile technologies
    • wireless networking
    • cloud storage
    • hacking (unauthorised access to a computer system)
    • wearable technologies
    • computer-based implants
    • autonomous vehicles
  • governments and security services:
    • terrorism and other forms of attacks
    • data privacy

  • printable booklets
  • printable activities
  • printable tests

  • Our questions are offered in an exam style, so you can get used to what to expect from your test.

No Content

coming soon

  • Pay by Bank transfer
  • Pay by debit and credit card
  • Monthly Payment Facility
  • Pay Later with Afterpay or Klarna
  • Pay with Paypal
  • Pay with Pix

Take the next step

General information

On average it takes our students 12 months to complete this course, however you have up to 24 months.

Study completely online using our award-winning learning platform, My CS Insideout.

Specification

Data types

  • integer
  • real/float
  • Boolean
  • character
  • string
  • date/time
  • records (or equivalent)
  • arrays (or equivalent)
  • user-defined data types
  • language-defined (built-in) data types

 

Programming concepts

  • variable declaration
  • constant declaration
  • assignment
  • iteration
  • selection
  • subroutine (procedure/function)
  • definite (count controlled)
  • indefinite interaction (condition controlled)
  • nested selection
  • nested iteration
  • meaningful identifier

 

Arithmetic operations in a programming language

  • addition
  • subtraction
  • multiplication
  • real division
  • integer division, including remainders
  • exponentiation
  • rounding
  • truncation

 

Relational operations in a programming language

  • equal to
  • not equal to
  • less than
  • greater than
  • less than or equal to
  • greater than or equal to

Boolean operations in a programming language

  • NOT
  • AND
  • OR
  • XOR

 

Constants and variables in a programming language

  • Constants
  • Variables

 

String-handling operations in a programming language

  • length
  • position
  • substring
  • concatenation
  • character → character code
  • character code → character
  • string conversion operations:
    • string to integer
    • string to float
    • integer to string
    • float to string
    • date/time to string
    • string to date/time

 

Random number generation in a programming language

  • The use of random number generation

 

Exception handling

  • the concept of exception handling
  • the use of exception handling

 

Subroutines (procedures/functions)

  • subroutines
  • the advantages of using subroutines

 

Parameters of subroutines

  • the use of parameters of subroutines
  • the use subroutines with interfaces

 

Returning a value/values from a subroutine

  • the use subroutines that return values to the calling routine

 

Local variables in subroutines

  • the use of local variables within a subroutines

 

Global variables in a programming language

  • contrasting local variables with global variables

 

Procedural-oriented programming

Structured programming

  • the structured approach to program design and construction
  • construction and use of hierarchy charts when designing programs
  • the advantages of the structured approach

Arrays

  • the concept of data structures
  • arrays (or equivalent)
  • multi-dimensional arrays (or equivalent)

Fields, records and files

  • read/write from/to a text file
  • read/write data from/to a binary (non-text) file

Aspects of software development

  • Analysis
  • Design
  • Implementation
  • Testing
  • Evaluation

Abstraction and automation

  • Problem-solving

    • to develop solutions to simple logic problems
    • to check solutions to simple logic problems
  • Following and writing algorithms

    • the term algorithm
    • pseudo-code
    • constructs:
      • sequence
      • assignment
      • selection
      • iteration
    • hand-tracing algorithms
    • conversion of an algorithm from pseudo-code into high-level language program code
    • the use of logical reasoning, test data and user feedback

Abstraction

  • the concept of abstraction
  • representational abstraction
  • abstraction by generalisation or categorisation

Information hiding

  • the process of hiding not essential details of an object

Procedural abstraction

  • computational pattern or computational method - a procedure

Functional abstraction

  • procedural abstraction
  • functional abstraction

Data abstraction

  • details of how data are actually represented are hidden, allowing new kinds of data objects to be constructed from previously defined types of data objects

Problem abstraction/reduction

  • how details are removed until the problem is represented in a way that is possible to solve because the problem reduces to one that has already been solved

Decomposition

  • procedural decomposition

Composition

  • build a composition abstraction by combining procedures to form compound procedures
  • build data abstractions by combining data objects to form compound data, for example tree data structure

Automation

  • automation requires putting models (abstraction of real-world objects/phenomena) into action to solve problems
  • This is achieved by:
    • creating algorithms
    • implementing the algorithms in program code (instructions)
    • implementing the models in data structures
    • executing the code

Finite state machines (FSMs) without output

  •  draw and interpret simple state transition diagrams and state transition tables for FSMs with no output

  • Number bases

    • decimal (base 10)
    • binary (base 2)
    • hexadecimal (base 16)
    • The use of binary to represent all data and instructions
    • The use of hexadecimal in computing

    Converting between number bases

    • the use of binary to represent whole numbers
    • the use of hexadecimal to represent whole numbers
    • convert in both directions between:
      • binary and decimal
      • binary and hexadecimal
      • decimal and hexadecimal

    Units of information

    • bit
    • kilobyte
    • megabyte
    • gigabyte
    • terabyte

Unsigned binary

  • the difference between unsigned binary and signed binary

Unsigned binary arithmetic

  • add two unsigned binary integers
  • multiply two unsigned binary integers

Signed binary using two’s complement

  • signed binary can be used to represent negative integers and that one possible coding scheme is two’s complement
  • represent negative and positive integers in two’s complement
  • perform subtraction using two’s complement
  • calculate the range of a given number of bits, n

Numbers with a fractional part

  • numbers with a fractional part can be represented in:
    • fixed point form in binary in a given number of bits
  • convertion for each representation form:
    • decimal to a binary of a given number of bits
    • binary to decimal of a given number of bits

Information coding systems

  • Character form of a decimal digit
  • ASCII and Unicode
  • Error checking and correction

Representing images, sound and other data

  • Bit patterns, images, sound and other data
  • Analogue and digital
  • Analogue/digital conversion
    • analogue to digital converter (ADC)
    • digital to analogue converter (DAC)
  • Bitmapped graphics
    • resolution
    • colour depth
    • size in pixels
    • metadata

Digital representation of sound

  • sample resolution
  • sampling rate and the Nyquist theorem
  • Calculating sound sample sizes in bytes

Musical Instrument Digital Interface (MIDI)

  • the purpose of MIDI
  • the advantages of using MIDI files for representing music

Data compression

  • lossless and lossy compression
  • run-length encoding (RLE)
  • dictionary-based methods

Encryption

  • the concept of encryption
  • the use of Caesar cypher to encrypt a plaintext message and decrypt a ciphertext
  • the use of  Vernam cypher or one-time-pad to encrypt a plaintext message and decrypt a ciphertext

Relationship between hardware and software

  • hardware
  • software

Classification of software

  • system software
  • application software

System software

  • operating systems (OSs)
  • utility programs
  • libraries
  • translators (compiler, assembler, interpreter)

Role of an operating system (OS)

  • the role of the operating system
  • the OS resource management:
    • managing hardware to allocate processors
    • memories and I/O devices among competing processes

Classification of programming languages

  •  types of programming languages
    • low-level languages
    • high-level languages
  • machine-code
  • assembly language

Types of program translator

  • assembler
  • compiler
  • interpreter
  • the difference between source and object (executable) code

Logic gates

  • Logic gates and truth tables for:
    • NOT
    • AND
    • OR
    • XOR
    • NAND
    • NOR
  • circuit diagrams
  • Boolean expression

Boolean algebra

  • Boolean identities
  • De Morgan’s laws
  • Boolean expressions

Internal hardware components of a computer

  • the basic internal components of a computer system
  • processor
  • main memory
  • address bus
  • data bus
  • control bus
  • I/O controllers
  • the communication between components
  • The Von Neumann
  • Harvard architectures
  • the concept of addressable memory

The stored program concept

  • machine code instructions stored in main memory are fetched and executed serially by a processor that performs arithmetic and logical operations

The processor and its components

  • the role and operation of a processor and its major components:
    • arithmetic logic unit
    • control unit
    • clock
    • general-purpose registers
    • dedicated registers, including:
      • program counter
      • current instruction register
      • memory address register
      • memory buffer register
      • status register
  • the Fetch-Execute cycle
  • the processor instruction set
  • instructions consist of an opcode and one or more operands (value, memory address or register)

Addressing modes

  • immediate and direct addressing modes
  • Immediate addressing: the operand is the datum.
  • Direct addressing: the operand is the address of the datum. Address to be interpreted as meaning either main memory or register

Machine-code/assembly language operations

  • the basic machine-code operations of:
    • load
    • add
    • subtract
    • store
    • branching (conditional and unconditional)
    • compare
    • logical bitwise operators (AND, OR, NOT, XOR)
    • logical
      • shift right
      • shift left
    • halt.
  • machine-code instructions are expressed in mnemonic form- assembly language, using immediate and direct addressing

Factors affecting processor performance

  • the effect on processor performance of:
    • multiple cores
    • cache memory
    • clock speed
    • word length
    • address bus width
    • data bus width

Input and output devices

  • the main characteristics, purposes and suitability of the devices and understand their principles of operation:
    • barcode reader
    • digital camera
    • laser printer
    • RFID

Secondary storage devices

  • the need for secondary storage within a computer system
  • the main characteristics, purposes, suitability and understanding of the principles of operation of the following devices:
    • hard disk
    • optical disk
    • solid-state disk (SSD)
  • the capacity and speed of access of various media

  • awareness of current individual (moral), social (ethical), legal and cultural opportunities and risks of computing
  • developments in computer science and the digital technologies have dramatically altered the shape of communications and information flows in societies, enabling massive transformations in the capacity to:
    • monitor behaviour
    • amass and analyse personal information
    • distribute, publish, communicate and disseminate personal information.
  • computer scientists and software engineers therefore have power, as well as the responsibilities that go with it, in the algorithms that they devise and the code that they deploy.
  • software and their algorithms embed moral and cultural values.
  • the issue of scale, for software the whole world over, creates a potential for individual computer scientists and software engineers to produce great good, but with it comes the ability to cause great harm.
  • the challenges facing legislators in the digital age

Communication methods

  • serial and parallel transmission methods
  • synchronous and asynchronous data transmission
  • the purpose of start and stop bits in asynchronous data transmission

Communication basics

  • baud rate
  • bit rate
  • bandwidth
  • latency
  • protocol
  • the relationship between bit rate and bandwidth

Network topology

  • physical star topology
  • logical bus network topology

 

Types of networking between hosts

  • peer-to-peer networking
  • client-server networking

 

Wireless networking

  • the purpose of WiFi
  •  the components required for wireless networking
  • how wireless networks are secured
  • the wireless protocol Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) with and without Request to Send/Clear to Send (RTS/CTS)
  • the purpose of Service Set Identifier (SSID)

  • printable booklets
  • printable activities
  • printable tests

  • Our questions are offered in an exam style, so you can get used to what to expect from your test.

No Content

coming soon

  • Pay by Bank transfer
  • Pay by debit and credit card
  • Monthly Payment Facility
  • Pay Later with Afterpay or Klarna
  • Pay with Paypal
  • Pay with Pix

 

Take the next step

General information

On average it takes our students 12 months to complete this course, however you have up to 24 months.

Study completely online using our award-winning learning platform, My CS Insideout.

Specification

Data types

  • the concept of a data type
  • use the following appropriately:
    • integer
    • real/float
    • Boolean
    • character
    • string
    • date/time
    • pointer/reference
    • records (or equivalent)
    • arrays (or equivalent)
  • use user-defined data types
  • language-defined (built-in) data types

Programming concepts

  • variable declaration
  • constant declaration
  • assignment
  • iteration
  • selection
  • subroutine (procedure/function)
  • definite and indefinite iteration, including indefinite iteration with the condition(s) at the start or the end of the iterative structure
  • nested selection and nested iteration structures
  • meaningful identifier names

Arithmetic operations in a programming language

  • addition
  • subtraction
  • multiplication
  • real/float division
  • integer division, including remainders
  • exponentiation
  • rounding
  • truncation

Relational operations in a programming language

  • equal to
  • not equal to
  • less than
  • greater than
  • less than or equal to
  • greater than or equal to

Boolean operations in a programming language

  • NOT
  • AND
  • OR
  • XOR

Constants and variables in a programming language

  • the differences between a variable and a constant
  • the advantages of using named constants

String-handling operations in a programming language

  • length
  • position
  • substring
  • concatenation
  • character → character code
  • character code → character
  • string conversion operation:
    • string to integer
    • string to float
    • integer to string
    • float to string
    • date/time to string
    • string to date/time

Random number generation in a programming language

  • random number generation

Exception handling

  • the concept of exception handling
  • the use of exception handling in a programming language with which students are familiar

Subroutines (procedures/functions)

  • the use of subroutines
  • a subroutine is a named ‘out of line’ block of code that may be executed (called) by simply writing its name in a program statement
  • the advantages of using subroutines in programs

Parameters of subroutines

  • the use of parameters to pass data within programs
  • the use of subroutines with interfaces

Returning a value/values from a subroutine

  • the use subroutines that return values to the calling routine

Local variables in subroutines

  • subroutines may declare their own variables, called local variables, and that local variable:
    • exist only while the subroutine is executing
    • are accessible only within the subroutine
  • the use local variables and explain why it is good practice to do so

Global variables in a programming language

  • contrast local variables with global variables

Role of stack frames in subroutine calls

  • how a stack frame is used with subroutine calls to store:
    • return addresses
    • parameters
    • local variables

Recursive techniques

  • the use of recursive techniques in programming languages
  • solving simple problems using recursion

Programming paradigms

  • characteristics of the procedural- and object-oriented programming paradigms

Procedural-oriented programming

  • the structured approach to program design and construction
  • construct and use hierarchy charts when designing programs
  • the advantages of the structured approach

Object-oriented programming

  • class
  • object
  • instantiation
  • encapsulation
  • inheritance
  • aggregation
  • composition
  • polymorphism
  • overriding
  • the object-oriented paradigm
  • object-oriented design principles:
    • encapsulate what varies
    • favour composition over inheritance
    • program to interfaces, not implementation
  • writing object-oriented programs
  • drawing and interpreting class diagrams

Data structures and abstract data types

  • the concept of data structures

Single- and multi-dimensional arrays (or equivalent)

  • arrays (or equivalent)
  • multi-dimensional arrays (or equivalent)

Fields, records and files

  • read/write from/to a text file
  • read/write data from/to a binary (non-text) file

Abstract data types/data structures

  • queue
  • stack
  • graph
  • tree
  • hash table
  • dictionary
  • vector
  • static and dynamic structures
  • creation and maintenance of data within:
    • queues (linear, circular, priority)
    • stacks
    • hash tables

Queues

  • linear queues, circular queues and priority queues:
    • add an item
    • remove an item
    • test for an empty queue
    • test for a full queue

Stacks

  • apply the following operations:
    • push
    • pop
    • peek or top
    • test for an empty stack
    • test for stack full

Graphs

  • a graph as a data structure used to represent more complex relationships
  • the terms:
    • graph
    • weighted graph
    • vertex/node
    • edge/arc
    • undirected graph
    • directed graph
  • adjacency matrix
  • adjacency lists

Trees (including binary trees)

  • a tree is a connected, undirected graph with no cycles
  • a binary tree is a rooted tree in which each node has at most two children
  • the uses for rooted trees

Hash tables

  • the concept of a hash table and its uses
  • simple hashing algorithms
  • the concept of a collision and how collisions are handled using rehashing

Dictionaries

  • the concept of a dictionary
  • simple applications of dictionaries

Vectors

  • the concept of a vector and the following notations for specifying a vector:
    • [2.0, 3.14159, -1.0, 2.718281828]
    • 4-vector over ℝ written as ℝ4
    • function interpretation
      • 0 ↦ 2.0
      • 1 ↦ 3.14159
      • 2 ↦ -1.0
      • 3 ↦ 2.718281828
      • ↦ means maps to
  • Dictionary representation of a vector
  • List representation of a vector
  • 1-D array representation of a vector
  • Visualising a vector as an arrow
  • Vector addition and scalar-vector multiplication
  • Convex combination of two vectors, u and v
  • Dot or scalar product of two vectors
  • Applications of dot product

Simple graph-traversal algorithms

  • breadth-first search
  • depth-first search

Simple tree-traversal algorithms

  • the tree-traversal algorithms:
    • pre-order
    • post-order
    • in-order
  • the uses of tree-traversal algorithms

Reverse Polish – infix transformations

  • simple expressions in infix form
  • Reverse Polish notation (RPN) form

  • trace and analyse the complexity of the linear search algorithm
  • The Time complexity of a linear search

  • trace and analyse the time complexity of the binary search algorithm
  • The Time complexity of a Binary search

  •  trace and analyse the time complexity of the binary tree search algorithm
  • The Time complexity of a Binary tree search

Bubble sort

  • trace and analyse the time complexity of the bubble sort algorithm
  • The Time complexity of a Bubble sort

Merge sort

  • trace and analyse the time complexity of the merge sort algorithm
  • Merge sort is a "Divide and Conquer" approach to problem-solving
  • The time complexity of Merge sort

Dijkstra’s shortest path algorithm

  • to trace Dijkstra’s shortest path algorithm
  • applications of shortest path algorithm

Abstraction and automation

  • develop solutions to simple logic problems
  • check solutions to simple logic problems

Following and writing algorithms

  • the term algorithm
  • the solution to a simple problem as an algorithm using pseudo-code, with the standard constructs:
    • sequence
    • assignment
    • selection
    • iteration
  • hand-trace algorithms
  • converting an algorithm from pseudo-code into high-level language program code
  • correctness and its efficiency using logical reasoning, test data and user feedback

Abstraction

  • the concept of abstraction as used in computations
  • representational abstraction
  • abstraction by generalisation or categorisation

Information hiding

  • the process of hiding all details of an object that do not contribute to its essential characteristics

Procedural abstraction

  • procedural abstraction represents a computational method

Functional abstraction

  • procedural abstraction
  • functional abstraction

Data abstraction

  • hoe data are actually represented are hidden, allowing new kinds of data objects to be constructed from previously defined types of data objects

Problem abstraction/reduction

  • details are removed until the problem is represented in a way that is possible to solve, because the problem reduces to one that has already been solved

Decomposition

  • procedural decomposition

Composition

  • building a composition abstraction by combining procedures to form compound procedures
  • building data abstractions by combining data objects to form compound data, for example, tree data structure

Automation

  • automation requires putting models (abstraction of real world objects/phenomena) into action to solve problems. This is achieved by:
    • creating algorithms
    • implementing the algorithms in program code (instructions)
    • implementing the models in data structures
    • executing the code

Finite state machines (FSMs) with and without output

  • interpreting simple state transition diagrams and state transition tables for FSMs with no output and with output (Mealy machines only)

Maths for regular expressions

  • the concept of a set and the following notations for specifying a set:
  • A = {1, 2, 3, 4, 5 }
  • or set comprehension:
  • A = {x | x ∈ ℕ ∧ x ≥ 1 }
  • where A is the set consisting of those objects x such that x ∈ ℕ and x ≥ 1 is true.
  • the empty set, {}, is the set with no elements. Know that an alternative symbol for the empty set is Ø.
  • the compact representation of a set, for example, the set {0n1n | n ≥ 1}. This set contains all strings with an equal number of 0 s and 1s.
  • the concept of:
    • finite sets
    • infinite sets
    • countably infinite sets
    • the cardinality of a finite set
    • Cartesian product of sets
  • the meaning of the term:
    • subset
    • proper subset
    • countable set
  • the set operations:
    • membership
    • union
    • intersection
    • difference

Regular expressions

  • a regular expression is simply a way of describing a set and that regular expressions allow particular types of languages to be described in a convenient shorthand notation
  • form and use simple regular expressions for string manipulation and matching
  • describe the relationship between regular expressions and FSMs
  • write a regular expression to recognise the same language as a given FSM and vice versa

Regular language

  • a language is called regular if it can be represented by a regular expression

Context-free languages

Backus-Naur Form (BNF)/syntax diagrams

  • checking language syntax by referring to BNF or syntax diagrams and formulating simple production rules
  • explain why BNF can represent some languages that cannot be represented using regular expressions

Comparing algorithms

  • algorithms can be compared by expressing their complexity as a function relative to the size of the problem
  • the size of the problem is the key issue
  • some algorithms are more efficient:
    • time-wise than other algorithms
    • space-wise than other algorithms

Maths for understanding Big-0 notation

  • mathematical concept of a function as a mapping from one set of values, the domain, to another set of values, drawn from the co-domain, for example ℕ → ℕ.
  • the concept of:
    • a linear function, for example y = 2x
    • a polynomial function, for example y = 2x2
    • an exponential function, for example y = 2x
    • a logarithmic function, for exampley = log10 x.
  • the notion of permutation of a set of objects or values, for example, the letters of a word and that the number of permutations of n distinct objects is n factorial (n!)

Order of complexity

  • the Big-O notation
  • constant time
  • logarithmic time
  • linear time
  • polynomial time
  • exponential time
  • to derive the time complexity of an algorithm

Limits of computation

  • the algorithmic complexity and hardware impose limits on what can be computed

Classification of algorithmic problems

  • algorithms may be classified as being either:
    • tractable - problems that have a polynomial (or less) time solution are called tractable problems.
    • intractable - problems that have no polynomial (or less) time solution are called intractable problems
  • Heuristic methods are often used when tackling intractable problems

Computable and non-computable problems

  • some problems cannot be solved algorithmically

Halting problem

  • the Halting problem (but not prove it), is the unsolvable problem of determining whether any program will eventually stop if given a particular input
  • the significance of the Halting problem for computation

Turing machine

  • the structure and use of Turing machines that perform simple computations
  • a Turing machine can be viewed as a computer with a single fixed program, expressed using:
    • a finite set of states in a state transition diagram
    • a finite alphabet of symbols
    • an infinite tape with marked-off squares
    • a sensing read-write head that can travel along with the tape, one square at a time
  • the state is called a start state and states that have no outgoing transitions are called halting states
  • the equivalence between a transition function and a state transition diagram
  • represent transition rules using a transition function
  • represent transition rules using a state transition diagram
  • hand-trace simple Turing machines
  • explaining the importance of Turing machines and the Universal Turing machine to the subject of computation

No Content

  • printable booklets
  • printable activities
  • printable tests

  • Our questions are offered in an exam style, so you can get used to what to expect from your test.

No Content

 

coming soon

  • Pay by Bank transfer
  • Pay by debit and credit card
  • Monthly Payment Facility
  • Pay Later with Afterpay or Klarna
  • Pay with Paypal
  • Pay with Pix

 

Take the next step

Edexcel

  • printable booklets
  • printable activities
  • printable tests

  • Our questions are offered in an exam style, so you can get used to what to expect from your test.

No Content

No Content

  • Pay by Bank transfer
  • Pay by debit and credit card
  • Monthly Payment Facility
  • Pay Later with Afterpay or Klarna
  • Pay with Paypal
  • Pay with Pix

  • printable booklets
  • printable activities
  • printable tests

  • Our questions are offered in an exam style, so you can get used to what to expect from your test.

No Content

No Content

  • Pay by Bank transfer
  • Pay by debit and credit card
  • Monthly Payment Facility
  • Pay Later with Afterpay or Klarna
  • Pay with Paypal
  • Pay with Pix

  • printable booklets
  • printable activities
  • printable tests

  • Our questions are offered in an exam style, so you can get used to what to expect from your test.

No Content

No Content

  • Pay by Bank transfer
  • Pay by debit and credit card
  • Monthly Payment Facility
  • Pay Later with Afterpay or Klarna
  • Pay with Paypal
  • Pay with Pix

Eduqas

  • printable booklets
  • printable activities
  • printable tests

  • Our questions are offered in an exam style, so you can get used to what to expect from your test.

No Content

No Content

  • Pay by Bank transfer
  • Pay by debit and credit card
  • Monthly Payment Facility
  • Pay Later with Afterpay or Klarna
  • Pay with Paypal
  • Pay with Pix

  • printable booklets
  • printable activities
  • printable tests

  • Our questions are offered in an exam style, so you can get used to what to expect from your test.

No Content

No Content

  • Pay by Bank transfer
  • Pay by debit and credit card
  • Monthly Payment Facility
  • Pay Later with Afterpay or Klarna
  • Pay with Paypal
  • Pay with Pix

  • printable booklets
  • printable activities
  • printable tests

  • Our questions are offered in an exam style, so you can get used to what to expect from your test.

No Content

No Content

  • Pay by Bank transfer
  • Pay by debit and credit card
  • Monthly Payment Facility
  • Pay Later with Afterpay or Klarna
  • Pay with Paypal
  • Pay with Pix

IB

OCR

  • printable booklets
  • printable activities
  • printable tests

  • Our questions are offered in an exam style, so you can get used to what to expect from your test.

No Content

No Content

  • Pay by Bank transfer
  • Pay by debit and credit card
  • Monthly Payment Facility
  • Pay Later with Afterpay or Klarna
  • Pay with Paypal
  • Pay with Pix

  • printable booklets
  • printable activities
  • printable tests

  • Our questions are offered in an exam style, so you can get used to what to expect from your test.

No Content

No Content

  • Pay by Bank transfer
  • Pay by debit and credit card
  • Monthly Payment Facility
  • Pay Later with Afterpay or Klarna
  • Pay with Paypal
  • Pay with Pix

SQA

  • printable booklets
  • printable activities
  • printable tests

  • Our questions are offered in an exam style, so you can get used to what to expect from your test.

No Content

No Content

  • Pay by Bank transfer
  • Pay by debit and credit card
  • Monthly Payment Facility
  • Pay Later with Afterpay or Klarna
  • Pay with Paypal
  • Pay with Pix

WJEC

Pearson

Programming