Combinatorial Explosions

• Exponential Growth: How Folding Paper Can Get You to the Moon (Youtube) https://youtu.be/AmFMJC45f1Q

• Combinatorial Explosions: How many ways can you arrange a deck of cards? (Youtube) https://youtu.be/uNS1QvDzCVw

Problem Classes

Solving the Tantrix Puzzle is an example of a hard problem: http://www.cs4fn.org/complexity/tantrixpnp.php 

youtube video clips for further explanations on problem complexity classes:

• P vs NP - An Introduction (Youtube) https://youtu.be/OY41QYPI8cw

• P vs NP and the Computational Complexity Zoo (Youtube) https://youtu.be/YX40hbAHx3s

• P Vs NP on TV - Computerphile (Youtube) https://youtu.be/dJUEkjxylBw

Some famous NP Problems studied in computer science include: 

• Travelling Salesman problem  

• Knapsack problem

• Integer Factorisation

• Hamiltonian Path

• Minimum Number of Colours for Graph Colouring

Graph Colouring

• There is more information on this famous problem, including its historic origins at the "Maths is fun website" here https://www.mathsisfun.com/activity/coloring.html

• Try out this interactive 3 map colour activity http://csvoss.scripts.mit.edu/np/

• this short youtube video clip shows how a map of adjacent regions is converted to a connected graph for the Map/Graph colouring problem.https://youtu.be/otjOaczA2n4

Travelling Salesman (TSP)

• Here is a more detailed description of what is the Travelling salesman problem: https://youtu.be/1pmBjIZ20pE

• This youtube video explores finding the optimal solution for the Traveling Salesman problem using brute force methods.https://youtu.be/7bpfXh8u6Uk

• Travelling Salesman problem (TSP) solved by various heuristics visualisation:https://youtu.be/SC5CX8drAtU

Kahoot Time Complexity Quiz - play solo

Greedy Heuristics

Nearest Neighbour as the name implies is a greedy heuristic method for solving the Travelling Salesman problem that at each decision point chooses the closest unvisited neighbouring option.

• Here is an example of Nearest neighbour being used https://youtu.be/R_IfyticWKQ

• How to use the Nearest Neighbour for the TSP https://youtu.be/wRvQSLtRnz0

Hill Climbing Heuristic

• youtube Hill climbing video clip https://youtu.be/kOFBnKDGtJM

General Heuristics

• More examples of heuristic approaches to explore here https://www.101computing.net/heuristic-approaches-to-problem-solving/

• "TSP when good enough beats perfect" for a quick recap of the heuristic methods https://youtu.be/GiDsjIBOVoA

• Try this online A* worked example https://www.101computing.net/a-star-search-algorithm/

• Explore this interactive application for solving the N-Puzzle using a range of different search algorithms including A* http://www.cs.rmit.edu.au/AI-Search/2015/