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.

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

How about this?

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?

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?

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.

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

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.

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

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

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

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 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)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)O(n). Loops through the list to find five.

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

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

Song List Solution

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

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

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.

interface Filter {
  boolean include(Song s);
}

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

Print the songs in the playlist.

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.

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;
}