AQA COMP3 - Key Notes

An eight page document with information on every point in the AQA COMP 3 (COMP3) specification.

Includes notes on: Turing Machines, BigO Notation, Programming Paradigms, Stacks & Queues, Graphs and Trees and their transveral methods, Sorting, Floating Point Numbers, Operating Systems, Database and Normalising (to 3NF), Communication and Networking and more.

All the information is completed to what I have learnt, there might be the odd error. Some images are from notes and wikipedia.

If you want the original word document instead of the PDF just message me.


Change: 13/06/2014 Order of Compexity Table, Thanks freddie_barbour

HideShow resource information
  • Created by: Charlie
  • Created on: 09-05-14 20:33
Preview of AQA COMP3 - Key Notes

First 604 words of the document:

Comparing Algorithms Big-O Notation
Time Complexity ­ How long an algorithm Uses Worst Case to analysis time complexity referred
takes to complete to as the order of complexity.
Complexity Form
Space Complexity ­ How much Memory an Exponential O(an)
algorithm needs to complete Polynomial O(na)
Linear O(n)
Logarithmic O( log(n) )
Table ordered in worst to best
Intractable Problems
Arithmetic Rules for Big-O Notation
A problem that can be computed but not in a
reasonable time for large inputs.
Property Example and Answer
An exponential complexity is not reasonable. Product The Product of the two functions is used.
O(H) * O(J) = O(HJ)
The Travelling Salesman Problem Sum The bigger function is used.
O(J) + O(T2 ) = O(T2 )
Well Known Problem. Finding the shortest distance to
travel though as many different towns.
Constant Constants are ignored
kO(H) = O(H)
It is a NP-Hard Problem and cannot be solved in a
polynomial time in any known way.
Heuristic Approach:
The nearest neighbour approach is a `smart' way of NP Problems
calculating the Travelling Salesman problem, with a list of A NP problem is a set of decision problem if I can be verified by a
cities each path with the closest distance is chosen till all polynomial time O(na).
cities are visited. Note that this is probably not the best
option and a quicker router can usually be found. P means the problem can be solved in a polynomial time using a
It is simple and fast but does not guarantee to give a Turing machine.
NP-Complete: Every problem in NP can be reduced to X.
The Halting Problem NP-Hard: Non-Deterministic Polynomial Time shows a problem is
An unsolvable problem that means you cannot not solvable in a realistic time.
determine if the program will stop given a particular input.
Turing Machines
A Turing machine is a hypothetical machine that can determine if something is
computable. Anything a modern computer can do, so can a Turing machine.
It consists of: An infinitely long tape, a header and a transition table.
The Turing machine header can move left and right. These are denoted by the
symbols << and >>. An empty square means empty space. A # separates the list.
Using the diagram and state transition it can be decided if an algorithm can be
A universal Turing machine can simulate other Turing machines, with this concept
any machine can be built with a UTM and executes the given data. An interrupter.
Finite State Machines
A state transition diagram is where the nodes represent states and the transition is
labelled "a|b" where the b part denotes an output and the represent input.
A transition table tabulates the states and next states during progression.
In a mealy machine the state is changed during the transition. In the state circles
are the state indicators.
In a Moore machine states of the outputs are represented inside the state circle. So
the output is only changed when the state has changed.
Finite State automaton produce a Boolean once the final state has been reached.
A non-deterministic FSA is where a transition can have two different paths.
2014- Charlie Knight

Other pages in this set

Page 2

Preview of page 2

Here's a taster:

Regular Expressions Reverse Polish Notation
Regular Expressions are a way of matching an input Known as Post-Fix Notation.
to a pattern by describing a set of valid string. Allows expressions to be written without brackets by
adding the operation at the end of the op-ands. It uses
Components of a Regular Expression
a stack which is Last-In-First-Out Operations.
Symbol Meaning Example When a symbol is read then it gets pushed on the stack.…read more

Page 3

Preview of page 3

Here's a taster:

Recursion Abstract Data Type
Recursion is where a procedure calls itself. Data types that are not defined by implementation but by
how the structure operators. There are four type to know
Usually a recursive function has a parameter in
Name Definition
which changes on each call. Linked Lists Each item contains a pointer to another
node. More flexible than an array.
Queues A FIFO (First in First Out) type structure.…read more

Page 4

Preview of page 4

Here's a taster:

Graphs Trees
A graph has a set of vertices (nodes) and edges that join the A tree is a type of undirected graph, but contains no cycles.
vertices. A labelled graph has the vertices associated with a Each vertex can only be reached using one path.
label. This means there is: n-1 edges (when n is vertices)
A directional graph means that the connecting edges have a
direction arrow point towards the vertices.…read more

Page 5

Preview of page 5

Here's a taster:

Calculating Floating Point Numbers
Floating point numbers are a representation of numbers in binary form. The range of floating point
numbers is far larger than fixed point. The use base two exponents and mantissas.
Precision & Significant Figures Errors caused by Floating Point Numbers
The precision is due to the limited size of memory. There are two types of errors.
Which compromises the accuracy of numbers.…read more

Page 6

Preview of page 6

Here's a taster:

Modelling an Database Normalising a Database
A conceptual model is a representation of data Normalisation is a technique used to normalise
requirements that is independent of any software. entities which means removing redundant or
duplicate data. There are three `normal' forms.…read more

Page 7

Preview of page 7

Here's a taster:

Communication Methods Local Area Network (LAN)
Serial Transmission: Binary signals are transmitted Local area networks are linked computers in close
one after each other. There are three types proximity. A LAN covers a small area in building in
Name Definition which storage, peripherals and printers are shared
Simplex One direction only. Single Channel between one another.
Half-Duplex Both direction but one single channel.…read more

Page 8

Preview of page 8

Here's a taster:

Network Types Wireless Networking
Segmenting a network means splitting up several WIFI is a wireless technology that allows computers
parts. and devices to connect together wirelessly. Using
Peer-to-peer networking is a network that has no various technologies (A, B, G, N) it is found
central server. Each node has the same rights. This commonly in homes. They are usually slower than
type of networking is widely used to download a physical connection and vulnerable to attack.
files.…read more


freddie barbour

Really useful and to the point. First computing revision notes that I've seen where the author understands that 63 PAGES OF TEXT is not a REVISION GUIDE. From what I can see it covers (almost) everything one actually needs to know, without all the useless filler ****. Bravo sir!

EDIT: Just found an error, in Big-O complexity table, logarithmic is more efficient than linear.


I think you meant to write traversal rather than transversal XD


Quite a few errors but best material I've found yet!



Thanks for your feedback, If you notice any errors do let me know (PM or as a Comment) - I don't mind updating this resource even tho I'm done with COMP3.

Good luck in your exams.


Have all the errors been corrected? :)

Similar Computing resources:

See all Computing resources »See all resources »