S03- Fundamentals of algorithms

Depth first grpah traversal

Explore as far down a path before backtracking and going down the next path. Uses recursion and a stack

Algorithm

A sequence of steps to complete a task that always terminates

Applications of depth-first traversal

Job scheduling, finding a path between two vertices

Breadth first graph traversal

Explore all neighbours of the current vertex, then neighbours of each of those vertices. Each discovered neighbour of current vertex is added to the rear of the queue

Applications of breadth first traversal

Shortest path algorithm, web crawler, social networking

Pre-order

root-L-R

In-order

L-root-R

Post-order

L-R-root

Use of pre-order tree traversal

Copying a tree

Use of in-order tree traversal

Binary search tree; output contents of a tree in a specific order

Use of post-order tree traversal

infix to RPN conversion; emptying a tree

Why is RPN used

Eliminates need for brackets, makes evaluation simpler and faster

Applications of Optimisation Algorithms

Packet switching, circuit board design, GPS, game strategy, project management

Dijkstra’s Shortest Path Algorithm

Graph search algorithm that finds the shortest path from a starting node to all other nodes in a weighted graph

Steps of Dijkstra’s Shortest Path (optional)

Sets the distance at the starting node to 0 and the distance of all other nodes to infinity. Mark all nodes as unvisited. Select the unvisited node with the smallest distance. For the current node, calculate the distance to each neighbouring node. If the calculated distance is less than the known distance, update the shortest distance. Repeat this process for all neighbouring nodes and mark the current node as visited. Continue until all nodes have been visited

Uses of Dijkstra’s Shortest Path

Finding the shortest/cheapest route over the Internet data transmission; planning circuit boards; finding shortest route between cities

Bubble sort implementation- best solution

Outer loop should be a WHILE loop where the condition is based on a ‘swap’ flag, set to TRUE if a swap of items was performed, and initialised with FALSE before the inner FOR loop

Merge sort steps

1. Divide unsorted list into n sub lists, each containing one element

2. Repeatedly merge two sub lists at a tiime to produce new sorted sub lists until there is only two sub lists

3. When there are two sub lists, compare the first elements of both sub lists and smaller one goes to the merged list

Binary search steps

1. Examine middle item of the list

2. If this is the item you’re searching for, return the index

3. If not, eliminate half the list depending on whether the item sought is greater or less than the middle item

4. Repeat until the item is found or is proved to be not in the list