Algorithms AQA

What is recursion?

What is recursion?

When a function calls itself

What are the 3 rules of a recursive function?

1) Base case (stopping condition)
2) It can reach the base case
3) The subroutine must call itself

What is Big-O notation?

A measure of the time complexity of an algorithm

What is time complexity?

The amount of time needed to solve a problem

What is space complexity?

The amount of resources needed to solve a problem (e.g. memory)

How does a linear search work?

Iterate through a list of items. Stop if you find what you are searching for. Otherwise keep going to the end

What is the time complexity of a linear search?

O(n)

How does a binary search work?

Check the middle value of the list. Compare your value to this value and if it is higher discard the bottom half of the list or vice versa. Keeps halving the list until you find your item or until there are no items left

What is required for a binary search to be able to take place on a list?

The list needs to be sorted

What is the time complexity of a binary search?

O(logn)

How does a bubble sort algorithm work?

Compare the first two elements and swap them if they aren't in the correct order. Keep going through the list comparing pairs of values and swapping if necessary. Repeat this process the number of times as the length of the list

What is the time complexity of a bubble sort?

O(n²)

How does a merge sort algorithm work?

Divide the unsorted list into sublists of each containing one element. Repeatedly merge two sublists at a time to produce new sorted sublists until there is only one sublist remaining

What is the time complexity of a merge sort?

O(nlogn)

What are the two types of graph-traversal algorithms?

Depth-first and breadth-first

How does a depth-first graph traversal algorithm work?

Go as far as you can down a path before backtracking and searching other paths

What data structure does a depth-first algorithm use?

A stack

How does a breadth-first graph traversal algorithm work?

Explore all neighbours of the current vertex, then the neighbours of each of those vertices and so on

What are possible applications of depth-first traversal?

Navigating a maze, Job scheduling where some jobs have to be completed before others begin

What are possible applications of breadth-first traversal?

Finding the shortest path between two points, A web crawler that analyses sites by following links randomly

What is the time complexity of depth-first and breadth-first searches?

In a sparse graph O(n) but if every vertex has the maximum number of edges it is O(n²) as every vertex must be searched and n number of edges from each vertex

What are the 3 different tree traversal algorithms?

Pre-order, in-order, post-order

Which order do you traverse a tree using the 3 (binary) tree traversal algorithms?

Pre-order) Root, Left, Right
In-order) Left, Root, Right
Post-order) Left, Right, Root

What is a use of pre-order?

Copying a tree

What is a use of in-order?

Outputting contents of a binary tree in ascending order

What is a use of post-order?

Emptying a tree

What algorithm can be used to find the shortest path between nodes on a graph?

Dijkstra's shortest path algorithm

What must be true about a graph for Dijkstra's algorithm to work?

It must be weighted

What supporting data structure does Dikjstra's algorithm use?

A priority queue

How does Dijkstra's algorithm work?

1) Set distance to starting node to 0 and all other nodes to infinity
2) Search all connected nodes to starting node and note their value down in priority queue
3) Remove starting node from queue and search all adjacent nodes to the next node in the queue
4) Update any values in the queue if there is a shorter path
5) Dequeue item
6) Repeat until no nodes left in queue

When is a problem defined as being computable?

If there is an algorithm that can solve every instance of it in a finite number of steps

What is a tractable problem?

A problem with a polynomial-time solution (or less)

What is an intractable problem?

A problem that does not have a polynomial-time solution e.g. time complexity O(2^n) and O(n!)

How do we attempt to solve intractable problems with computers?

Come up with heuristic approaches (an imperfect solution but does a good enough job)