Topic 3 - Fundamentals of algorithms

2 types of graph traversal

Depth-first

Breadth-first

What graph traversal is this?

Breadth first

What graph traversal is this?

Depth first

Fill in the blanks:

Depth first traversal uses a _____. Breadth first traversal uses a _____

Stack

Queue

3 types of tree traversal

Pre-order

In-order

Post-order

What tree traversal is this?

Pre-order

What tree traversal is this?

In-order

What tree traversal is this?

Post-order

Pre order traversal

Used for copying a tree

Can be performed on any tree

In-order traversal

Used for a binary search

Can only be performed on binary trees

Post-order traversal

Used for Reverse Polish and emptying a tree

Can be performed on any tree

Reverse Polish definition

A postfix way of writing expressions that eliminates the need for brackets and confusion over order of execution

Linear search

Checks each item until the target is found or list ends

Can be conducted on any list

Time complexity of O(N)

Binary search

Looks at midpoint of list and determines if target is higher or lower, then repeats

Can be used on any ordered list

Time complexity of O(logN)

Binary tree search

Looks at parent node value and goes left if target is smaller, or right if target is larger

Can be used on any binary tree

Time complexity of O(logN)

Bubble sort

Swaps the positions of adjacent items to order them

Time complexity of O(n²)

Merge sort

Splits the array into smaller lists, then reforms them into the sorted order

Time complexity of O(logN)

Dijkstras algorithm

Used to find the shortest path betwene 2 nodes in a weighted graph