Visit Paul's website
The book From Computing to
can be ordered at: computize.org
The universe and the world around us work with rhythm and repetition. Sunrise and sunset; the seasons; you get out of bed, go to work or school, come back home and go to bed at night. Many things repeat regularly— songs and music have reprises, visual arts and architecture designs also use repetition of patterns, animals breath in and out, their hearts go on beating.
All that is not surprising. But, what if I tell you that repetition is also a powerful way to solve problems? This article focuses on repetition or “iteration” and formalizes it as a systematic way for problem solving through the lens of computational thinking (CT). By doing this we hope to gain a deeper understanding of the nature of iteration in procedures and to realize that iteration can be applied to solve problems in many ways and in different areas including computing and daily living.
This post is part of our CT blog (computize.org) where you can find many other interesting and useful articles.
A Simple Example
Often we need to arrange data items in a certain order to make them easy to use. For example words in a dictionary are in alphabetical order. Personnel records are ordered by names. Numbers are arranged in ascending or descending order, and so on.
To begin, let’s see how iteration is applied to rearrange a list of, say, grades of eight students, into ascending order. Here is the list of grades:
67.5, 59.5, 82, 93.5, 77, 45.5, 100, 76.5
And we want to rearrange them into
45.5, 59.5, 67.5, 76.5, 77, 82, 93.5, 100
The method is simple, find the highest grade and move it to the last position of the list. Then, repeat the operation on the rest of the list (now with one less grade) and so on, until no more grades are left. The list is now in ascending order. This method is actually called bubble sort because in computing sorting means putting items into order.
Problem Solving with Iteration
Iteration is a powerful tool for problem solving. The tool can be applied if a problem, any problem, fits the following iteration paradigm.
If the answer is yes to all three questions, you can apply iteration to solve that problem.
Walking to a destination, for example, can be solved by iteration because
Applying the Iteration Paradigm
Let’s examine a couple of daily tasks that can be performed by iteration. First the diﬀicult task of eating a bowl of soup. Here the simplest or trivial case is that the bowl is already empty or almost empty. We just need to do nothing or finish it directly and stop.
However, if the bowl is full, we can take a spoonful (surprise) thus reducing the size of the task. The resulting problem is a smaller task of the same nature, that is to finish the remaining soup. Because the problem fits the paradigm, we can be sure that repeatedly taking spoonfuls will work fine :-)
Another example is delivering newspapers on a paper route which is not unfamiliar to many of us. The task is to drop off today’s newspaper at a list of locations in a neighborhood, usually by riding a bicycle.
Here is how that task fits the iteration paradigm. If the location list is empty or of length one, then we simply finish the task directly. For a long list of locations, we can reduce the list by riding to one of the locations. The list is shortened and the remaining task is still of the same exact nature. Obviously by repeatedly riding to another location we can complete the task.
While the iteration stays the same, the order in which the locations are visited can make the task easier or harder. Ingenuity can lie in picking which location to visit next, especially when the number of locations increase and their distances vary.
Iteration Paradigm in Bubble Sort
Now let’s revisit bubble sort to reveal the iteration paradigm and the repeated operations in it.
If the list to be sorted contains just one element, then we are finished by doing nothing. In general, the list will have more than one element. Then, bubble sort pushes the largest (or smallest) element to the end of list for ascending (descending) order. The list is now reduced by one element and the smaller problem is still a list of elements to be ordered.
The actual pushing of the largest (smallest) element to the end of the list is again done by iteration. The pushing task fits the iteration paradigm (you can figure this out).
The iteration repeats a number of compare-exchange (CE) operations. Each CE operation compares two adjacent elements of the list, and exchanges (swaps) them when necessary so that the latter element is larger (or smaller for descending order).
Let’s see how exactly it sorts a sequence of eight elements, a0, a2, ..., a7.
Bubble sort makes multiple passes to complete its job.
Pass 1 repeats CE operation seven times: CE(a0, a1), CE(a1, a2), CE(a2, a3), CE(a3, a4), CE(a4, a5), CE(a5, a6), and CE(a6, a7) and moves the largest value to a7.
In a similar manner, pass 2 repeats CE operation six times and moves the largest value of a0, a1, ..., a6 up into a6; pass 3 repeats CE operation five times and moves the largest value of a0, a1, ..., a5 up into a5; and so on, until, finally, pass 7 repeats CE operation one last time and moves the largest value of a0 and a1 into a1 to complete the sorting.
To employ iteration in any application, we need to precisely control and execute all the necessary repetitions. We can look at an iteration abstractly as a construct, taking it out of the context of any particular application. We see that every iteration consists of the following elements:
Let’s put bubble sort in algorithmic form so as to clearly identify these elements. We assume the list of grades have been placed in an array of numbers a, ... a[n-1] and the array length is n (the total number of grades).
Recall that bubble sort repeats a number of phases and each phase repeats a number of CE operations. Here is a flowchart illustrating the procedure for each single phase:
Every iteration requires control to manage the repetitions and to start, continue, and end the repetitions correctly. Here are the essential elements of iteration control in the flowchart.
Following the flowchart we see clearly one complete phase of CE operations and the largest value being pushed to the end. In the flowchart, CE uses a temporary variable temp to swap the values of two elements.
To complete the bubble sort, we need to perform all phases, starting with the full array of elements. By reducing the value of end by one, we ensure that the next phase will work on a shorter array.
Thus, we have two iterations one nested within the other. The outer iteration repeats the inner iteration to execute each phase. It updates n, n=n-1, just before the next phase. And each individual phase is performed by the inner iteration which repeats CE operations.
Iterations Are Not Created Equal
Even though the speed of modern computers can help us use brute-force to iterate over large amounts of data, the eﬀiciency of an algorithm is still very important.
Bubble sort is ineﬀicient and seldom used in practice. This is because the number of phases grows linearly as the length of the array to be sorted grows and the array in each phase is only shortened by one element.
A much better algorithm is quicksort which still applies iteration but much more cleverly.
With quicksort the idea is to split the array to be sorted into two parts, smaller elements to the left and larger elements to the right. This is called the partition operation, which first picks an arbitrary element of the array as the partition element pe. By exchanging elements, the array can be arranged so all elements to the right of pe are greater than or equal to pe. Also, all elements to the left of pe are less than or equal to pe. The location of pe is called the partition point.
After partitioning, we have cut the array into two parts, one to the left of pe and one to the right of pe. The same partition method is now repeated on each of the two parts. When the size of a part becomes less than 2, the partition stops. When all partitions stop, the task is done.
Quicksort is eﬀicient in practice, because it often reduces the length of the array to be sorted quickly, basically cutting the array length in half after each partition.
We often hear the adage “if it works do it again.” Iteration certainly follows that principle.
Iteration has wide applications, in computing and in daily living. Any problem that fits the iteration paradigm is a candidate.
Each iteration involves initialization, continuation, and termination. Controlling how these are performed is important when specifying an iteration for a particular application. While an iteration is straightforward, ingenuity often lies in the way to reduce a task to small ones. In the end, iteration is not only a method to solve problems but also a new way of thinking.
When we face a new problem or task, we may have various ways to tackle it. What iteration teaches us is that we can consider vastly simplified cases to get some insight which can lead us to ways to cut the task down. As soon as we reduced the problem to one or more smaller job of the same nature, we have the problem solved already!
Isn’t that almost magical?
A Ph.D. and faculty member from MIT, Paul Wang (王 士 弘) became a Computer Science professor (Kent State University) in 1981, and served as a Director at the Institute for Computational Mathematics at Kent from 1986 to 2011. He retired in 2012 and is now professor emeritus at Kent State University.
Paul is a leading expert in Symbolic and Algebraic Computation (SAC). He has conducted over forty research projects funded by government and industry, authored many well-regarded Computer Science textbooks, most also translated into foreign languages, and released many software tools. He received the Ohio Governor's Award for University Faculty Entrepreneurship (2001). Paul supervised 14 Ph.D. and over 26 Master-degree students.
His Ph.D. dissertation, advised by Joel Moses, was on Evaluation of Definite Integrals by Symbolic Manipulation. Paul's main research interests include Symbolic and Algebraic Computation (SAC), polynomial factoring and GCD algorithms, automatic code generation, Internet Accessible Mathematical Computation (IAMC), enabling technologies for and classroom delivery of Web-based Mathematics Education (WME), as well as parallel and distributed SAC. Paul has made significant contributions to many parts of the MAXIMA computer algebra system. See these online demos for an experience with MAXIMA.
Paul continues to work jointly with others nationally and internationally in computer science teaching and research, write textbooks, IT consult as sofpower.com, and manage his Web development business webtong.com