In mathematics, problem-solving flows through a series of steps, otherwise known as a formula or algorithm. It’s helpful to visualize algorithms before trying to implement them — it’s a safer and more efficient design route than simply trying to plan a process in your head.
An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.
Think of how you would program a method to do division without using your programming languages built-in divide keyword (or method) /. You’ll find the easiest way to figure it out is to “go back to the drawing board” and write out an example to see each step you will need to implement. Numbers don’t just add themselves; there are algorithms at work.
Algorithms can be built on top of each other; they’re building blocks for higher problem solving. The more you use them, the more you’ll start to see patterns and find more efficient ways to do things. For example, let’s visualize how an algorithm works to produce the word-wrapped formatting of this text you’re reading right now.
Word Wrapping
With word wrapping, there are certain rules you must determine. Ask yourself “what does it mean to word wrap” and use your answers as a rule guide.
For instance, you know that word wrapping needs to occur when the given text reaches the maximum length of the allowed width, at which point a new line break is put in. The simplest word wrap would be to break the text at the max length with a new line and optionally hyphenate the word. Let’s word wrap some text to six characters wide in this way.
# before The rain in Spain stays mainly in the plain # after The r- ain i- n Spa- in st- ays m- ainly in the plain
Looking at the visual representation we can conclude the rules for this algorithm come down to: If there is a space character at the fifth or sixth position, then insert a new line character, otherwise hyphenate the word and insert a new line character.
Let’s say we don’t want to hyphenate words. How can we best visualize what needs to be done here? We’ll go for seven characters wide in this example.
T h e r a i n i n S p a i n
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
-------------------->?
Y<----------X
S->0->1->2->3->4->5->6->?
Y
S->0->1->2->3->4->
Here we go to the maximum length for our word wrap and see if we have an empty space to substitute with a new line character. Since we don’t, we need to backtrack to before the current word and find where the empty space is. Once we’ve found it, we can mark it for substituting that space character.
Next we want to start counting seven characters after our new offset and check for an empty space again. We repeat the process until we have no more text. This illustration will help us grasp the steps needed to implement working code and makes it easier for us to determine potential issues or edge cases.
The range of inputs for which an algorithm works has to be specified carefully.
What if we have a word that’s more than seven characters long in our last example? Our visual aid for our algorithm doesn’t take that into account. As it stands, our algorithm seeks seven characters into the word and then goes back to the beginning and fails to find what we told it to seek for.
If we implemented an algorithm just as we’ve illustrated, we now have a rule for our input that each word must be less than 8 characters in length for it to work. If this algorithm provides the desired output for our problem, then we’re done here. Otherwise our algorithm is incomplete and needs to be revised.
Efficiency
Visualizing algorithms can also help you find ways to write them more efficiently. Division is a good example of this.
If you have a computer perform (2 * 8)/(3 * 8), it will perform both multiplication algorithms before performing the division algorithm. But what we’re taught in school is that when you have the same number being multiplied in both the numerator and the denominator, they cancel themselves out. Therefore, the 8 would cancel out of both and the value is 2/3.
If we were to write a cancellation algorithm that recognizes the same multipliers being divided and have it remove them before the math gets calculated, we may improve performance speed. A perfect example for implementing this kind of efficiency is dividing factorials. The factorial algorithm is written as:
n! = n(n-1) · · · 2 * 1
All factorial does is multiply the given number times every number from it down to one. You will often find programming examples of this written with a recursive method.
# ruby example
def fact(n)
if n == 0
1
else
n * fact(n-1)
end
end
If you just wanted to calculate the result of factorial, then this is fine. But if we do something with division, as in our earlier example, with factorials we’d be very inefficient if we didn’t apply cancellation between common multipliers for both the numerator and denominator. For example:
8!/6! # without cancellation 8*7*6*5*4*3*2*1/6*5*4*3*2*1 = 40320/720 = 56 # with cancellation 8*7/1 = 56/1 = 56
When you do 8!/6! without cancellation, it performs multiplication twelve times and division once. When you apply cancellation to 8!/6!, you multiply once and you don’t even need to divide. Anything divided by one is itself. So with cancellation and dropping a denominator of one, we reduced the computer’s effort of running thirteen basic math algorithms down to just one.
This brings huge improvement in efficiency performance when you can use cancellation in division, but this requires that the multipliers given to division not be evaluated yet.
In Ruby, this can be written as:
# numerator of factorial multipliers n = 8.downto(1).to_a # => [8, 7, 6, 5, 4, 3, 2, 1] # denominator of factorial multipliers d = 6.downto(1).to_a # => [6, 5, 4, 3, 2, 1] # cancellation for Arrays containing multipliers def c(a,b) (a - b) + [1] # anything times 1 is itself end num = c(n,d) # => [8, 7, 1] den = c(d,n) # => [1] num.reduce(:*) / den.reduce(:*) # => 56
Factorials are used often when calculating odds and probabilities. If you want to calculate the probability of getting a winning poker hand, for example, you will use the mathematical field of combinatorics, which includes dividing factorials. By visualizing the steps of what’s being done, we can find a way to write a more efficient algorithm and to better calculate the probability of getting a winning poker hand.
Summary
Drawing a visual representation of an algorithm is the safest and most efficient path for designing a proper implementation. On the other hand, trying to solve things in your head will most often be the cause of mistakes and oversights.
Algorithms need to be visualized while you’re learning and discovering the process for your desired result. Over time, reusing algorithms will lead to a more solid understanding of their use. Once you know it well enough, you won’t need to draw it — you can simply refer to it by name. At that point, it’s become a simple building block in your experience in applying algorithms.
But as with our division example, you may discover alternative and possibly more efficient ways to implement new algorithms once you write it out. The best mathematicians in the world write out their formulae; it would be wise to follow their example. Any time you’re looking for efficiency, simplicity, or grasping newer ideas and concepts, it’s best to write out a visual representation of the steps to get the big picture of what’s going on.
| Reference: | Visualizing Algorithms Before Implementation from our WCG partner Daniel P. Clark at the Codeship Blog blog. |
