Kotlin
Java

Algorithms and Lists
Java

Created By: Geoffrey Challen
/ Updated: 2021-10-10

Welcome back! The rest of the semester is incredibly exciting material. As you begin work on the machine project, we begin building and analyzing new data structures and algorithms. We'll also introduce new bits of Java syntax along the way.

Algorithms and Data Structures

Algorithms and data structures comprise the core conceptual concerns of computer science. Algorithms are how we do things. Data structures are how we represent things.

The two topics are intertwined. We will implement data structures to support certain algorithms. And we will design algorithms that utilize specific data structure capabilties.

Algorithm Analysis

As we proceed, we will spend more time talking about how long certain algorithms take and why—or performing algorithm analysis. To do this we use something called Big-O notation to describe the behavior of algorithms. Let's define those terms:

Algorithm analysis: the determination of the computational complexity of algorithms, that is the amount of time, storage and/or other resources necessary to execute them.

Big-O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

Discuss algorithm and Big-O terminology.

Complexity Categories

We'll take a very high-level view of Big-O as we get started with algorithm analysis. Let's provide an overview of the different complexity categories that we'll learn to identify, and some of the code features that are associated with them.

Look at different complexity categories, their limiting behavior, and code features associated with them.

Array Lists

To get some practice with algorithm analysis, over the next few lessons we'll be implementing a data structure known as a list. You've already been working with Java's built-in Lists, so this will give you a peek at how they are actually implemented.

Lists store a sequence of elements. We already know how to do that using arrays, and we can build an implementation of lists on top of an array. Let's see how!

Show how to get started implementing lists using an array internally. Introduce the SimpleList interface. Implement get and set.

Remove

OK, this is good start. But so far all we have is a wrapper around an array! That's not particularly interesting.

Indeed, the key difference between a Java array and list is that the size of the list can change. But doing this using a list that maintains are array internally requires more work. Let's see how, starting with the remove operation. (You get to implement add as today's homework.)

Demonstrate how to do remove. Add a few tests for fun.

Algorithm Analysis

Next, let's take a look at our core list functions and see how they perform. We're going to use our new big-O vocabulary and try to understand the performance of get, set, and remove.

Perform both static and dynamic performance analysis for our list class.

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