1. Introduction

An important class of algorithms in computer science deals with this question:

If there are a several ways to arrive at a goal, and there are choices to be made along the way, what are the best set of choices and how do we find that optimal solution?

This is called a path-finding problem and it happens in many fields. For example:

• Navigation. What is the best path to get from A to B along a transport network
• The internet. What is the most efficient route to get a packet of data to its destination
• Speech recognition - a computer needs to parse a spoken command with many possibilities
• Image recognition - being able to classify/recognise an image from a huge set of possibilities
• Artificial Intelligence - training neural nets to work out an optimal strategy e.g playing chess
• Robotics 2D - controlling their path from A to B
• Robotics 3D - finding the optimal path for a robotic arm to move in 3D space
• Gaming - path finding and NPC control in game worlds
• Finance - help make optimal investment choices
• Military - unmanned drones can use it to plan a route without external commands
• Social network analysis - friendship networks, influencers, meme propagation

For this syllabus, two popular algorithms will be covered namely the Dijkstra's algorithm and the A* algorithm