Visually Explained Algorithms The Greedy Method is an approach for solving certain types of optimization problems. The greedy algorithm chooses the optimum result at each stage. While this works the majority of the times, there are numerous examples where the greedy approach is not the correct approach. For example, let’s say that you’re taking the greedy algorithm approach to earning money at a certain point in your life. You graduate high school and have two options: Get a job that only requires a high school diploma Go to college and then get a job after you graduate from college The
Tag: Computer Science
Algorithms Visually Explained The Minimum Spanning Tree connects all vertices utilizing the minimum path. This is just a quick intro since we will cover MSTs in detail in a couple of later articles, but we’ll show a quick example of what an MST looks like. We’re not going to take any algorithmic approach, but instead use intuition in this example. We can see that there are two negative edges in this graph, so most likely they’ll be part of the minimum spanning tree. We’ll start by adding those edges. From there, we can add edges from vertices D, E, and
Visually Explained Algorithms Kruskal’s algorithm generates a minimum spanning tree. The way it works is that it keeps selecting the least costly edge until a minimum spanning tree is created. The only constraint is that a cycle doesn’t appear once the least costly edge is selected. Let’s look at an example. There are 10 vertices and each vertex has at least one edge connecting to it. We’ll look through the edges until we find the least costly edge. We can quickly see that edge F-I has the least costly edge, so we’ll include it first. Next, there are two edges
Visually Explained Algorithms Prim’s Algorithm is similar to Kruskal’s Algorithm. It’s a greedy algorithm that finds the MST (minimum spanning tree) for a weighted, undirected graph. Starting at an arbitrary ve rtex, the algorithm builds the MST one vertex at a time where each vertex takes the shortest path from the root node. Let’s move to our example. Although we can begin with any vertex, we’ll choose vertex A for this example. Vertex A has direct edges to B and I. The cost to vertex B is 7 and the cost to vertex I is 15. Since Prim’s algorithm is a greedy
Expanding Branches When inserting a node, remember this rule: nodes will only be added as leaves in the tree. Let’s assume we have the following tree. If we look at this tree, you’ll notice that at each node, values in the left subtree are smaller than the value of the node, and values in the right subtree are larger than the node’s value. Let’s say we wanted to insert the value 35. Can you predict where it would be in the tree? Let’s walk through it and see where it ends up. We start by comparing 35 to the root
Trimming Leaves Algorithmically When deleting a leaf in the tree, the structure of the tree does not change. If we examine the tree below, the outlined nodes can be deleted safely without changing the overall structure of the tree. The leaves circled in red can simply be removed without modifying the existing leaf structure. Nodes that pointed to the deleted leaf node will no longer point to that node. You thought this would be a tediously long explanation? Nope. Like I try to reiterate through my articles, simplicity is key. Don’t overthink it. Computer Science topics, especially Algorithms, can be
Trimming the Branches Exactly what it sounds like. We’ll be deleting a node from a tree that has only one child. Let’s look at our tree and examine which nodes have one child. In our example, only node 33 has one child. All other nodes have two children. If we removed node 47 from the list, we would have two nodes that have 1 child each; node 40 would have one immediate child and node 33 would have one immediate child. However, let’s keep the example as is. It is important for the reader to have this visual in their
Visual Explanation of Deleting a Node with Two Children What would happen if we wanted to remove node 40 from the tree below? Since node 40 has two children, we can’t simply point to its child and hope it works. There’s an algorithmic approach to this problem too. The way we remove this node is by replacing it with the next largest value. How do we get the next largest value? By going into the right subtree, and then following the left subtree until we get to the leaf node. Let’s look at that more closely. We enter node 40’s right
All-Pairs Shortest Path Matrix Multiplication You’re presented with a graph and your goal is to find all-pairs of shortest paths using dynamic programming. The first step is to create a matrix where the number of rows and columns equals the number of vertices and then to populate it with initial data. For each vertex that can be reached by one hop, you will populate it with the edge weight. If a vertex cannot be reached with one hop, you will populate it with infinity and if a vertex is trying to reach itself, you will populate it with zero. Let’s
A Visual Guide to Floyd-Warshall and Matrix Multiplication The goal of the Floyd-Warshall algorithm is to find the shortest paths in a tree using Dynamic Programming. Let’s get started with an example. The Floyd-Warshall algorithm starts by gathering the initial weights and placing them into a matrix. Since there are 4 vertices, the matrix will have 4 rows and 4 columns. Starting with vertex 1, the algorithm gathers the initial weights from 1 to the other 3 vertices. It will place a 0 for itself and infinity if there is no direct path. The edge weight from 1 to itself