Unit 9. Big Oh and A*

Big Oh notation is a way of categorizing and comparing algorithms in terms of how their run-time changes as the inputs change. We will only spend a day on this topic.

A* is a common path-finding algorithm. After we discuss how it works and do some short exercises, you will complete a program where a creature is chasing the user through a maze.   Here are links to some supplementary material about A*.

Comparison of A* to Dijkstra's algorithm

Step by step discussion of applying A* in a grid (though it does allow movement along a diagonal).

Very good 11 minute video on A*