At this point, we’ve built up enough of a foundation of core computer capabilities that we can actually start solving problems! And so we’ll do that by implementing a simple search.
But first, we have a new word to add to our vocabulary: algorithm. Wikipedia defines an algorithm as:
In mathematics and computer science, an algorithm is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always unambiguous and are used as specifications for performing calculations, data processing, automated reasoning, and other tasks.
Let’s break down this definition just like we would break down a piece of code.
While algorithm is an old word, it’s highly associated with a new field: computer science. Here’s a cool graph showing the use of the world algorithm over time based on data collected by the Google Books project:
You can see usage picking up in the 50s and 60s—right when people were starting to invent the first modern computers. Interestingly, you can also pick out the first tech boom and bust in the early 00s, and a recent uptick again. (If you want to explore the usage of other words over time, the Google Books ngram viewer is a very cool tool!)
So while on some level algorithms can refer to a general purpose but unambiguous problem solving strategy, we’ll almost always drop the “computer” from “computer algorithms”.
We’re going to get a lot of practice implementing simple algorithms this semester. That’s what you’ll be doing on most of the homework problems, and on most parts of the machine project. So this first time we’re going to slow down and do things one step at a time and very deliberately.
One important distinction is between an algorithm and an implementation:
An easy way to keep things straight is to remember that code is never an algorithm. Code implements an algorithm. But the same algorithm could be implemented using another language and look somewhat different.
We’ll spend the rest of this lesson developing and implementing a simple algorithm. If an array contains a value, it will print “Found!“. If not, it will not print anything. This is one of many different types of search algorithm, and perhaps the simplest.
Whenever we design and implement an algorithm we’ll focus on the design first. To do that, we’ll only write comments initially describing what we want our code to do in English. Then, we’ll fill those in with code one step at a time until the algorithm is complete.
Let’s write down in English using comments exactly what we want our code to accomplish. Keep in mind that computers are very literal, so we need to be very specific.
Now that we have our algortihm outlined, it’s time to turn it into Java code. This is usually the hard part when you are just getting started! Many students lament that they know exactly how to solve a problem, but not how to translate it into running code. But don’t worry—you’ll get lots of practice at this.
Please review this walkthrough carefully, since on the way to our solution we’ll also introduce a few new bits of Java syntax.
Completing our search algorithm above required a few new array and loop concepts. We introduced them in passing in the walkthrough, but present them separately here. Please don’t let this backwards approach throw you off! This isn’t the last time that we’ll introduce a new piece of syntax where it’s needed, and then explain it afterward.
As we saw in the implementation walkthrough above, Java arrays know how long they are. This make it much easier to work with them using loops. We use the following syntax to access their length:
The syntax is array name +
Dot syntax is something that we’re going to work with a lot later in the course.
But for now it will just have to remain mysterious and useful, just like
We most frequently see array length used in this type of
Loops and arrays—a match made in computer heaven.
Our second new piece of Java syntax is the
break causes a loop to exit.
The first computers weren’t machines—they were humans, tasked with performing complex mathematical calculations of incredible importance with equally-incredible precision.
Katherine Johnson was a mathematician and human computer who performed calculations that were critical to the early success of the American space program. As a Black female scientist, she overcame incredible societal prejudice and outright discrimination on her way to make lasting contributions to space exploration. Her example inspired many others, and I get inspired every time I hear her talk about her work. Persistence and determination will take you a long way in life:
Katherine Johnson’s story—along with the story of other Black female mathematicians who contribute to the space program—was dramatized in the excellent movie “Hidden Figures”. If you haven’t seen it, it’s worth watching.
Need more practice? Head over to the practice page.