KotlinJava

← Prev

Index

Next →

Kotlin
Java

# Algorithms I

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.

## AlgorithmsAlgorithms

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

### Algorithms v. ImplementationsAlgorithms v. Implementations

We’re going to get a lot of practice implementing simple algorithms. 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 SearchOur First Algorithm: Simple Search

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.

### Step 0: DesignStep 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.

### Step 1: ImplementationStep 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.

## Solve: Largest of Three (Practice)

Created By: Geoffrey Challen
/ Version: 2020.8.0

Let's use conditionals to perform a common task: finding the largest of, in this case, three numbers.

You can imagine using this kind of code in a lot of places. Maybe you're picking the next person for your pickup basketball team and have the heights of three possible teammates. Maybe you're choosing between three medications and want to choose the best based on the results of some study. Or maybe you're choosing a steak to cook for dinner and want the heaviest cut of meat at the same price. In all cases the logic is the same.

Assume you are working with three `Double` variable: `first`, `second`, and `third`. Your code should print the value of the largest of the three. (If two or more values tie for the largest, you can print any of the largest values.)

## A Few New Building BlocksA 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 SizeArray 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:

var values = intArrayOf(1, 2, 5)
println(values.size)

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:

var temperatures = doubleArrayOf(88.2, 78.3, 90.9)
for (i in 0 until temperatures.size) {
println(temperatures[i])
}

Loops and arrays—a match made in computer heaven.

### `break``break`

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

for (i in 0 until 24) {
println(i)
if (i > 8) {
break
}
}

## Solve: Game Tiebreaker Snippet

Created By: Geoffrey Challen
/ Version: 2021.8.0

Two players have completed a game. The score of Player 1 is saved in a `Int` variable `first`, and the score of Player 2 in an `Int` variable `second`. If either player scored more points than the other, they are the winner! However, if both players tie, then the player that played second is the winner. You also have access to a `boolean` variable `firstStarted` that is set to `true` if Player 1 played first and `false` otherwise.

Record the result of the game in an existing `Int` variable `winner`, which you should set to `1` if Player 1 won and `2` if Player 2 won. (Do not declare `winner`, simply set its value appropriately.)

## CS People: Katherine JohnsonCS People: Katherine Johnson

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.

## More Practice

Need more practice? Head over to the practice page.