Graphs have many different applications and can be applied to many different problems. While there are basic answers, like a map routing you from one place to another, there are far more complex answers, like social networks connecting you to friends, or a corporation connecting their suppliers and distributors to each other to optimize truck space and shipping costs.

Graphs can contain information that traditionally would not be expected in graph form, and this allows it to be more versatile. In the example in the shortened answer, power companies can use graphs to map out possibilities of where to lay…

Divide and Conquer algorithms are more efficient because of the number of comparisons made. In a sorting example, selection sort has to review every single element n² times because of the way it is implemented; no amount of optimization of the algorithm will fix that its best-case runtime is (n²). Meanwhile, with a divide and conquer algorithm like merge sort, it will run in (n lg n) time no matter what. Because of the way merge sort, and other divide and conquer methods are implemented, it cannot end up worse than (n lg n) runtime. This is because merge sort…

Heuristics, as a general term, are where the code is designed to find a more optimal solution to a problem. Optimal could be defined as a more accurate solution, or as a quicker solution that is still fairly accurate. For example, in program 1, where we had to find the optimal way to maximize space and profit of paintings on a given wall, my heuristic function divided the price by the total area of the painting. Other heuristic functions could be made, such as taking the price of a painting and only dividing by one dimension for example. Both of…

This post discusses A*, pronounced A Star, one of the most used pathfinding algorithms. It sees a wide range of use in video games, as well as other graph traversal uses.

Before we get into the backstory of A*, we should discuss Dijkstra briefly. Dijkstra was created in 1956, and then published in 1959. It operates on a wide, breadth first search, that goes down every path until the shortest path is already ending in the goal node. This is a very useful strategy; however, it can be time consuming, and can be improved upon. The original use of A*…