# 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*

- Created by: Charlie
- Created on: 09-05-14 20:33

First 604 words of the document:

A2 COMPUTING COMP3 - KEY POINTS

SECTION 1: PROBLEM SOLVI NG

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.

solution

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

computable.

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

## Comments