Kotlin
Java

Algorithms I
Kotlin

Created By: Geoffrey Challen
/ Updated: 2021-08-30

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.

Algorithms

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.

Describe what an algorithm using the Wikipedia definition as as starting point. Discuss the fact that computers have to implement it, and discuss how literal they are. Also discuss the non-ambiguity.

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".

Algorithms v. Implementations

Describe the first step of algorithm development, which involves outlining the algorithm itself. Emphasize the difference between an algorithm and code that implements the algorithm.

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 algorithm is the set of steps that a computer takes to solve a problem.
  • An implementation is the computer code that expresses those steps in a particular programming language.

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.

Our First Algorithm: Simple Search

We'll spend the rest of today's 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.

Step 0: Design

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.

Walk through the design of the search algorithm very slowly. The goal is to get to a comment skeleton that we'll fill in in the next walkthrough.

Step 1: Implementation

Now that we have our algortihm outlined, it's time to turn it into Kotlin 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 Kotlin syntax.

Walk through the implementation based on the design that was reached above. (This video should be recorded in parallel with the previous one.) Start with the comment skeleton and fill in things one by one.

A Few New Building Blocks

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.

Array Size

As we saw in the implementation walkthrough above, Kotlin 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 + .size. 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.

We most frequently see array length used in this type of for loop:

Loops and arrays—a match made in computer heaven.

break

Our second new piece of Kotlin syntax is the break statement. break causes a loop to exit. Immediately! Right away.

Describe break.

Show how to complete the homework problem above. Feel free to cover multiple approaches!

Solution Walkthrough

Show how to complete the homework problem above. Feel free to cover multiple approaches!

Solution Walkthrough