AQA Computer Science A-Level Algorithms

How is a breadth first search performed?

-Mark first node as visited at root
-Check all adjacent nodes of currently working nodes by adding them to a queue
-Update currently working node by checking first node in the queue and remove it from the queue.
-When no adjacent nodes update queue and currently working node to first in sequence
-Repeat for all other nodes

How is a depth first search performed?

-Start at root node,add it to the stack and mark as visited.
-Add adjacent nodes to top of stack and mark them as visited
-Change currently working node, if it has no adjacent nodes remvoe it from the stack
-Otherwise add next adjacent nodes to the stack and set that to currently working node
-repeat till all nodes have been visited and stack is empty.

What is a depth first search?

A search that starts at the root and follows a branch as far as it will go then backtracks

What is a breadth first search?

A search that starts at the root then scans every node connected and then continues scanning left to right

What are some applications for a depth first search?

Navigating to the end of each chain
Good for use in mazes due to removing the need to traverse each way more than once in each direction

What is an application of a breadth first search?

Vertices visited in order of distance.
Always finds the shortest possible path (with respect to the number of edges)
Used in search engines

How would a pre order traversal be completed?

1. If Binary tree empty do nothing
2. Otherwise
   a. Visit the root
   b. traverse the left subtree in pre-order
   c. traverse the right subtree in pre-order

How would a in order traversal be completed?

1. If Binary tree empty do nothing
2. Otherwise
   a. traverse the left subtree in in-order
   b.Visit the root
   c. traverse the right subtree in in-order

How would post order traversal be completed?

1. If Binary tree empty do nothing
2. Otherwise
   a. traverse the left subtree in post-order
   b.traverse the right subtree in post-order
   c. Visit the root

What is a use of pre-order traversal?

Copying a tree:
Pre order should be used when copying a tree as taking the root first means the tree order is maintained

What is a use of in order traversal?

Binary tree search:
In-order traversal is used as it supplies nodes data in ascending order

what is a use of post order traversal?

Infix to Reverse Polish Notation:
Makes sure correct operands and operators are placed in the correct place.

Empty a tree:
Trees need to be deleted before roots so post order is used.

What is the time complexity of a linear search?

The time complexity of a linear search is O(n)

How does a linear search work?

Checks each item then moves to the next item and repeats.

What is the time complexity of a binary search?

The time complexity of a binary search is O(log(n))

How does a binary search work?

A binary search starts by checking the middle value, then breaks the data being searched down into halves and checks the middle value again, until the value is found.

What are the goals of an algorithm?

-Run as quickly as possible
-Take up as little memory as possible

efficiency is seen as the complexity of the problem relative to the size of the problem.

What is big O notation?

O(n) notation classifies algorithms based on how computation time grows as inputs size grows.

How can efficiency be measured?

Algorithms can be measured by efficiency:

• This is measured through time complexity and space complexity.

What is a function?

A function maps a set of inputs to a set of outputs:
Domain:All possible inputs
Range: Set of all outputs
Codomain: All possible values that can be outputted

What is complexity?

Time and space complexity are related to the number of steps and memory space used by an algorithm

How is complexity calculated?

Most significant expression so 4+3n+1 has a representation of 3n and can be written as O(n)

What are the different types of complexity and what is their big O notation?

Linear complexity O(n) grows at the same rate as input size grows
Polynomial Complexity O(n^x) grows at the rate of n^x
Logarithmic complexity O(log(n)) an algorithm that halves each set of passes
Constant Complexity O(1) Always takes the same time to run
Exponential complexity O(2^n) doubles each additional value

What is spatical partitioning?

Spacial Partitioning separates different items into their own "quadrants" in this way time complexity is significantly reduced as there are much fewer tests that need to happen in each quadrant so the time complexity which would previously have been O(n^2) is now O(n)