Edexcel A Level Computer Science 2024
Exam Comprehensive Review Questions
and Answers
Abstraction - Answer>>Representation that is arrived at by
removing unnecessary details
Computational complexity of algorithms - Answer>>Measures
how economical the algorithm is with time and space
Time complexity of algorithms - Answer>>Indicates how fast an
algorithm runs
Space complexity of algorithms - Answer>>Indicates how much
memory an algorithm needs
Big O notation - Answer>>Order of complexity of an algorithm
Exponential time algorithm - Answer>>An algorithm whose
execution time grows exponentially with input size
Polynomial time algorithm - Answer>>An algorithm whose
execution time grows as a polynomial of input size
Linear time algorithm - Answer>>A polynomial time algorithm
that executes in O(n) time
Non-computable problems - Answer>>Describes an algorithmic
problem that admits no algorithm
Intractable problems - Answer>>Problems for which no
reasonable (polynomial) time solution has yet been found (e.g.
Travelling Salesman)
, Tractable problems - Answer>>Problems that have reasonable
(polynomial) time solutions as the size of input increases
Heuristic approach - Answer>>Uses know-how and experience
to make informed guesses that assist in finding a polynomial time
solution as an approximation to an intractable problem
Halting problem - Answer>>The unsolvable problem of
determining whether any program will eventually stop given
particular input
Turing Machine - Answer>>A Finite State Machine that control
one or more tapes, where at least one tape is of infinite length
Universal Turing Machine - Answer>>An interpreter that reads
the description of any arbitrary Turing Machine and faithfully
executes operations on data
Finite State Automata - Answer>>FSM with no output
Mealey machine - Answer>>FSM with output, where output is
associated with a transition
Moore machine - Answer>>FSM with output, where output is
associated with a state
State transition diagram - Answer>>A directed graph whose
nodes represent the states, and the transitons are labelled with
the inputs and outputs (if any)
Regular expressions - Answer>>A notation for defining all the
valid strings of a formal language or a special text string for
describing a search pattern
Exam Comprehensive Review Questions
and Answers
Abstraction - Answer>>Representation that is arrived at by
removing unnecessary details
Computational complexity of algorithms - Answer>>Measures
how economical the algorithm is with time and space
Time complexity of algorithms - Answer>>Indicates how fast an
algorithm runs
Space complexity of algorithms - Answer>>Indicates how much
memory an algorithm needs
Big O notation - Answer>>Order of complexity of an algorithm
Exponential time algorithm - Answer>>An algorithm whose
execution time grows exponentially with input size
Polynomial time algorithm - Answer>>An algorithm whose
execution time grows as a polynomial of input size
Linear time algorithm - Answer>>A polynomial time algorithm
that executes in O(n) time
Non-computable problems - Answer>>Describes an algorithmic
problem that admits no algorithm
Intractable problems - Answer>>Problems for which no
reasonable (polynomial) time solution has yet been found (e.g.
Travelling Salesman)
, Tractable problems - Answer>>Problems that have reasonable
(polynomial) time solutions as the size of input increases
Heuristic approach - Answer>>Uses know-how and experience
to make informed guesses that assist in finding a polynomial time
solution as an approximation to an intractable problem
Halting problem - Answer>>The unsolvable problem of
determining whether any program will eventually stop given
particular input
Turing Machine - Answer>>A Finite State Machine that control
one or more tapes, where at least one tape is of infinite length
Universal Turing Machine - Answer>>An interpreter that reads
the description of any arbitrary Turing Machine and faithfully
executes operations on data
Finite State Automata - Answer>>FSM with no output
Mealey machine - Answer>>FSM with output, where output is
associated with a transition
Moore machine - Answer>>FSM with output, where output is
associated with a state
State transition diagram - Answer>>A directed graph whose
nodes represent the states, and the transitons are labelled with
the inputs and outputs (if any)
Regular expressions - Answer>>A notation for defining all the
valid strings of a formal language or a special text string for
describing a search pattern
