A2 Keywords

You should know the definition of all these terms and examples to illustrate them.

3.1.1: Information Hiding

3.1.2: Algorithms

Algorithm

Computational complexity

Time complexity of an algorithm

Space complexity of an algorithm

Worst-case complexity

Best-case complexity

Average-case complexity

Basic operation

Order of growth

Sum of n numbers e.g. 1-10

Asymptotic

Big O notation

Behaviour of log 2 n, n2 quadratic, polynomial), n3 (cubic, polynomial), 2n (exponential), n! (factorial)

Exponential time

Polynomial time

Linear time

3.1.3: Finite State Machines

State transition diagram

Finite state machine

Transition function

Transition table

Deterministic FSM

Non-deterministic FSM

Halting state

FSM with output

Finite state automaton

3.1.4: Turing Machines

3.1.5: Intractable Problems

3.1.6: Regular Expressions, BNF & RPN

3.2.1: Programming Paradigms

Imperative programming (changes state)

Functional programming (does not use change of state)

Logic programming

3.2.2: Recursion

3.2.3: Lists & Pointers

3.2.4: Stacks & Queues

3.2.5: Graphs & Trees

3.2.6: Searching & Sorting

3.2.7: Simulation