KotlinCS 124 LogoJava
PrevIndexNext
Kotlin
Java
  • Implementing a Map : 04/26/2024

  • Streams : 04/25/2024

  • Generics : 04/24/2024

  • Hashing : 04/23/2024

  • Binary Search : 04/22/2024

  • MP3: Course Ratings : 04/19/2024

  • Quicksort : 04/18/2024

  • Merge Sort : 04/17/2024

  • Sorting Algorithms : 04/16/2024

  • MP Debugging Part 1 : 04/15/2024

  • MP2: Course Activity : 04/12/2024

  • Practice with Recursion : 04/11/2024

  • MP Debugging Part 0 : 04/10/2024

  • MP2: API Client : 04/09/2024

  • MP2: API Server : 04/08/2024

  • Trees and Recursion : 04/05/2024

  • Trees : 04/04/2024

  • Recursion : 04/03/2024

  • MP1: Filtering and Search : 04/02/2024

  • MP1: Loading and Sorting : 04/01/2024

  • Lists Review and Performance : 03/29/2024

  • Linked Lists : 03/28/2024

  • Algorithms and Lists : 03/27/2024

  • Continuing MP0 : 03/26/2024

  • Getting Started with MP0 : 03/25/2024

  • Lambda Expressions : 03/22/2024

  • Anonymous Classes : 03/21/2024

  • Practice with Interfaces : 03/20/2024

  • Implementing Interfaces : 03/19/2024

  • Using Interfaces : 03/18/2024

  • Working with Exceptions : 03/08/2024

  • Throwing Exceptions : 03/07/2024

  • Catching Exceptions : 03/06/2024

  • References and Polymorphism : 03/05/2024

  • References : 03/04/2024

  • Data Modeling 2 : 03/01/2024

  • Equality and Object Copying : 02/29/2024

  • Polymorphism : 02/28/2024

  • Inheritance : 02/27/2024

  • Data Modeling 1 : 02/26/2024

  • Static : 02/23/2024

  • Encapsulation : 02/22/2024

  • Constructors : 02/21/2024

  • Objects, Continued : 02/20/2024

  • Introduction to Objects : 02/19/2024

  • Compilation and Type Inference : 02/16/2024

  • Practice with Collections : 02/15/2024

  • Maps and Sets : 02/14/2024

  • Lists and Type Parameters : 02/13/2024

  • Imports and Libraries : 02/12/2024

  • Multidimensional Arrays : 02/09/2024

  • Practice with Strings : 02/08/2024

  • null : 02/07/2024

  • Algorithms and Strings : 02/06/2024

  • Strings : 02/05/2024

  • Functions and Algorithms : 02/02/2024

  • Practice with Functions : 02/01/2024

  • More About Functions : 01/31/2024

  • Errors and Debugging : 01/30/2024

  • Functions : 01/29/2024

  • Practice with Loops and Algorithms : 01/26/2024

  • Algorithms : 01/25/2024

  • Loops : 01/24/2024

  • Arrays : 01/23/2024

  • Compound Conditionals : 01/22/2024

  • Conditional Expressions and Statements : 01/19/2024

  • Operations on Variables : 01/18/2024

  • Variables and Types : 01/17/2024

  • Welcome to CS 124 : 01/16/2024

Algorithms

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

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
Algorithms v. Implementations

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.

Our First Algorithm: Simple Search
Our 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: Design
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.

// Design your algorithm here

Step 1: Implementation
Step 1: Implementation

Now that we have our algorithm 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.

// Translate our design into running code

Practice: Largest of Three

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 Blocks
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 Length
Array Length

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:

int[] values = {1, 2, 4};
System.out.println(values.length);

The syntax is array name + .length. 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 System.out.println.

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

double[] temperatures = {88.2, 78.3, 90.9};
for (int i = 0; i < temperatures.length; i++) {
System.out.println(temperatures[i]);
}

Loops and arrays—a match made in computer heaven.

Practice: 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.)

break
break

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

for (int i = 0; i < 24; i++) {
System.out.println(i);
if (i > 8) {
break;
}
}

Homework: Number of Digits Snippet

Created By: Geoffrey Challen
/ Version: 2022.8.0

Given a number between 0 and 999,999, inclusive, write a snippet of code (not a method) to determine how many digits it has. The number is stored in an int variable value. You should declare a int variable count and set it to the number of digits in value. For example, given the value 124 you would set count to 3. Given the number 8008, you would set count to 4. Do not modify the value of value.

There are several ways to approach this problem. Don't overthink it!

CS People: Katherine Johnson
CS 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.