---
marp: true
title: 26 March 2021
theme: default
paginate: true
---
# <!-- fit --> CS 199 EMP

### Hosted by Jackie Chan and Akhila Ashokan

**Topics:** List and Implementations of Lists, Algorithm Analysis, Lambda Expressions

---

# Today's Learning Objectives

- Lists and Implementations of Lists

- Algorithm Analysis

- Lambda Expressions

Write code on the homepage or any playground on the site!
https://cs125.cs.illinois.edu/

Slides are on the course site!
https://cs199emp.netlify.app/

---

# Before Lists

Let's review arrays through the *actions* you can perform on an array and the runtime/algorithm analysis of these operations.

What are some actions you can do with an array?

- Declare
- Store
- Retrieve

That's basically it. From your perspective, these operations are constant, i.e. the time it takes to declare, store, and retrieve values from an array is constant no matter the size.

---

# Let's Get Some Practice w/ Analysis (5 minutes)

What's the runtime for the second line? All arrays are subject to change.

```java
int[] arr = new int[]{1, 2, 3};
System.out.println(arr[0]);
```

How about this?

```java
int[] arr = new int[]{1, 2, 3, 4, 5, 6};
for (int i = 0; i < arr.length; i++) {
  if (arr[i] == 5) {
    System.out.println("Found five!");
  }
}
```

---

# Continued

And this?

```java
int[] arr = new int[]{1, 2, 3, 4, 5, 6};
for (int i = 0; i < arr.length; i++) {
  if (arr[i] == 1) {
    System.out.println("Found one!");
  }
}
```

And lastly?

```java
int[] arr = new int[]{1, 2, 3, 4, 5, 6};
int[][] metaArr = new int[6][];
for (int i = 0; i < arr.length; i++) {
  metaArr[i] = new int[arr.length - i];
  for (int j = i; j < arr.length; j++) {
    metaArr[i][arr.length - 1 - j] = arr[j];
  }
}
```
---

# "What about lists?"

What are some actions you expect to be able to do with a list? Spoiler [documentation for lists](https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/util/List.html).

With lists, there are *multiple implementations*. They have their tradeoffs and the particular implementation you want may depend on what you want to do/prioritize, e.g. I want to be able to store stuff quickly.

The implementations of a List determine the runtime for the operations. We'll focus on the `ArrayList` implementation.

---

# Practice with `ArrayList` (10 minutes)

You'll probably want [the documentation](https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/util/List.html) in front of you. You'll be manipulating a list of `Song` objects, a class I'll code for you.

1. Add three of your favorite songs, no judgment.

2. Print out `true`/`false` based on whether your list contains `new Song("Enchanted", "Taylor Swift")`. You need to `@Override` the `public boolean equals(Object o)` function for it to work properly.

3. Create two playlists and combined them.

---

# Song List Starter Code

```java
import java.util.ArrayList;

public class Song {
  public String title;
  public String artist;

  Song(String setTitle, String setArtist) {
    this.title = setTitle;
    this.artist = setArtist;
  }
}

ArrayList<Song> playlist = new ArrayList<>();
```

---

# "Gross, Greek letters...": Lambda Exressions

Lambda expressions allow you to write functions like variables.

```java
interface Modify {
  int modify(int value);
}

Modify first = (value) -> value + 1;
```

Pretty neat! Other programming languages allow you to do this more elegantly, but regardless it's a cool tool.

The syntax is pretty weird though, lambda expressions use arrow notation to define the parameters and the body of the function.

---

# Example of Anonymous Class to Lambda Expression

```java
// A functional interface.
interface SayHello {
  void sayHello();
}

// An anonymous class.
SayHello jackie = new SayHello() {
  @Override
  public void sayHello() {
    System.out.println("Hey Jackie!");
  }
};

jackie.sayHello();

// A lambda expression, no parameters here.
SayHello akhila = () -> System.out.println("Hey Akhila!");

akhila.sayHello();
```

---

# Customized Playlist Filters (20 minutes)

Here, we will use lambda expressions to make filters for playlists on the fly.

- We'll define a function called `public ArrayList<Song> filter(ArrayList<Song> original, Filter f)`. Don't change the original list, make a new list with the songs we didn't filter out.

- Write a function that prints out the songs in the `ArrayList`. Override `toString()` in the `Song` class.

- Implement the `Filter` functional interface to filter out, say Taylor Swift songs :(

---

# Filter Playlist Starter Code

```java
import java.util.ArrayList;

public class Song {
  public String title;
  public String artist;

  Song(String setTitle, String setArtist) {
    this.title = setTitle;
    this.artist = setArtist;
  }
}

interface Filter {
  boolean include(Song s);
}

public ArrayList<Song> filter(ArrayList<Song> original, Filter f) {
  // Your code here.
}

public void printSongs(ArrayList<Song> pl) {
  // Your code here.
}
```

---

# Example Playlist

```java
ArrayList<Song> pl = new ArrayList<>();

pl.add(new Song("Ain't It Fun", "Paramore"));
pl.add(new Song("Hannah Hunt", "Vampire Weekend"));
pl.add(new Song("tolerate it", "Taylor Swift"));
pl.add(new Song("Teenage Dream", "Katy Perry"));
pl.add(new Song("Enchanted", "Taylor Swift"));
pl.add(new Song("Hey, Soul Sister", "Train"));
pl.add(new Song("Fireflies", "Owl City"));
```

---

# "That's everything I got for today!"

We covered a lot. Particularly, we did some practice on *runtime analysis*, *lists* (specfically the `ArrayList` implementation), and *lambda expressions* through the playlist filter.

Let us know if you have any questions!

Fill out the [feedback form](https://forms.gle/54tRoxwNM79J7nAu5) if you have anything to say! Have a good, safe weekend! Get vaccinated if you can.

---

# Solution Section

---

# Runtime Analysis Solutions

1. Constant time, $O(1)$. If that notation doesn't make sense, doesn't matter. Retrieve a value with an index is constant for arrays.

2. Linear time, $O(n)$. Loops through the list to find five.

3. Linear time, $O(n)$. Tried to trick you. Should be linear cause who knows where $1$ is for a random array.

4. Polynomial time, specifically $O(n^2)$. You can tell because there are two for loops going through the size of the array.

---

# Song List Solution

```java
ArrayList<Song> playlist = new ArrayList<>();

playlist.add(new Song("Teenage Dream", "Katy Perry"));
playlist.add(new Song("Hey, Soul Sister", "Train"));
playlist.add(new Song("Fireflies", "Owl City"));

System.out.println(playlist.contains(new Song("Fireflies", "Owl City")));

ArrayList<Song> anotherPlaylist = new ArrayList<>();
anotherPlaylist.add(new Song("Royals", "Lorde"));
anotherPlaylist.add(new Song("The Lazy Song", "Bruno Mars"));

playlist.addAll(anotherPlaylist);

System.out.println(playlist.size());
```

---

# Song List Solution, `@Override` in `Song` Class

```java
@Override
public boolean equals(Object o) {
  assert o instanceof Song;
  
  Song s = (Song) o;
  
  if (this.title.equals(s.title) && this.artist.equals(s.artist)) {
    return true;
  } else {
    return false;
  }
}
```

---

# Song Filtering Solution Part 1

Overriding the `toString()` method.

```java
public class Song {
  public String title;
  public String artist;

  Song(String setTitle, String setArtist) {
    this.title = setTitle;
    this.artist = setArtist;
  }
  
  @Override
  public String toString() {
    return this.title + " by " + this.artist;
  }
}
```

---

# Song Filtering Solution Part 2

Taylor Swift filter.

```java
interface Filter {
  boolean include(Song s);
}

Filter taylor = (s) -> !s.artist.equals("Taylor Swift");
```

Print the songs in the playlist.

```java
public void printSongs(ArrayList<Song> pl) {
  for (int i = 0; i < pl.size(); i++) {
    System.out.println((i + 1) + ": " + pl.get(i));
  }
}
```

---

# Song Filtering Solution Part 3

Filter the playlist without changing the original.

```java
public ArrayList<Song> filter(ArrayList<Song> original, Filter f) {
  ArrayList<Song> filtered = new ArrayList<>();
  
  for (int i = 0; i < original.size(); i++) {
    if (f.include(original.get(i))) {
      filtered.add(original.get(i));
    }
  }
  
  return filtered;
}
```