• Shortest Path Algorithms

    BACK: Minimum Spanning Trees Suppose I wanted to know the fastest possible road to get from one place to another. I could spin around the block 50 times before I decide to actually leave the neighborhood and go to Costco–that would technically be a path to get to Costco. But...

  • Minimum Spanning Trees

    BACK: Graphs Basics A minimum spanning tree is an tree (acyclic) in the graph that is able to connect every node with each other with the least amount of cost. For things like circuits or a set of friend’s houses, you might want to know the least amount of wire...

  • Graphs Basics

    BACK: Greedy Programming We’ve seen graphs in previous classes: a network of nodes or vertices that connect to each other through their edges. We try to turn every problem that we have into a graph: Maps for planning and perception, the Internet, social media, our friends, … We can represent...

  • Greedy Programming

    BACK: Dynamic Programming Think of greedy programming as like a gradient descent method. We want to find a the correct direction of where we should go and then take a small step into that direction, in hopes that it will lead to a globally optimal solution. However, we may get...

  • Dynamic Programming

    BACK: Divide and Conquer When I first heard about dynamic programming, I thought it was going to be a really cool programming technique that would change the code as it runs. I was greatly disappointed when it just meant that we’re storing solutions to our subproblems in some table. Essentially,...

  • Divide and Conquer

    BACK: Data Structures With most of the groundwork laid out, we can start discussing different algorithmic techniques: one of which are divide and conquer strategies. We’ve already seen an example of the divide and conquer being used in merge sort. The big idea behind this strategy is to recursively divide...

  • Data Structures

    BACK: Sorting Algorithms Hash Tables Binary Search Tree Maps NEXT: Divide and Conquer

  • Sorting Algorithms

    BACK: Growth of Functions Definitions In-Place New memory is never allocated for the algorithm to run. I.e: Insertion sort is in-place, while merge sort is not. Running Times Merge Sort Pseudocode: pg 31, 34. Split the array in half until you are left with arrays of size 1. Since arrays...