CS 199 EMP

Hosted by Jackie Chan and Akhila Ashokan

Topics: Lists, Algorithm Analysis, Maps

Resources

For today, we'll try and work through some challenging modifications to linked lists. You can do it!

We'll also practice algorithm analysis more.

If we have time, we'll touch on maps.

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/

A Linked List With No End

We're going to modify linked lists so that they're cyclical. Given a linked list, convert it so it's a cycle, i.e. the last Item doesn't reference null, but instead references the start.

It's whacky I know, but give it a try! The next slides illustrate the difference.

Cyclical Linked List Problem Statement

With the starter code, change it so it's a cycle! Also write a print function that prints that will loop nn times (a parameter you give it). In short:

  • Convert the implementation to a cycle (15 minutes w/ hint @ 7 minutes)

  • Code toStringCycle(int n) which will print the cycle nn times. (10 minutes)

Cyclical Linked List Starter Code

public class LinkedList {
  
  public Item start;
  public int length;
  
  LinkedList() {
    this.start = null;
    this.length = 0;
  }
  
  public class Item {
    public int value;
    public Item next;
    
    Item(int setValue, Item setNext) {
      this.value = setValue;
      this.next = setNext;
    }
  }
  
  public void add(int value, int index) {
    assert index >= 0 && index <= this.length;
    int step = 1;
    
    if (index == 0) {

      this.start = new Item(value, this.start);

    } else {

      for (Item i = this.start; i != null; i = i.next) {
        if (index == step) {
          Item addition = new Item(value, i.next);
          i.next = addition;
        }
        step++;
      }

    }

    this.length++;
  }
  
  @Override
  public String toString() {
    String buffer = "";
    
    for (Item i = this.start; i != null; i = i.next) {
      buffer += i.value + " -> ";
    }
    
    return buffer + "null";
  }
  
  public String toStringCycle(int n) {
    return "";
  }
  
}

Tests for Cyclical Linked Lists

For cyclical implementation.

LinkedList ls = new LinkedList();
ls.add(1, 0);
ls.add(2, 0);
ls.add(3, 0);
System.out.println(ls);
System.out.println(ls.start);
// If correct, should print the same String as above.
System.out.println(ls.start.next.next.next);

For cyclical print.

System.out.println(ls.toStringCycle(3));
// Should print: 3 -> 2 -> 1 -> 3 -> 2 -> 1 -> ...

Are You Still Alive?

That was more tough than I thought it would be, hopefully you got something out of it though. I may or may not (definely) got lost a few times writing this up. - Jackie

Linked Lists are hard. Draw them out, it'll save you some mental stress.

Algorithm Analysis Practice

  • Ms. Lovelace is trying to line up the students for lunch. She wrote an algorithm to see all possible lines for her nn students. What's the runtime here? I.e. how many lines will there be?

  • Mr. Babbage is looking for a particular screw in his cabinet. To accomplish this, he picks up each screw, compares it to all other n−1n-1 screws until he's gone through all nn screws. What's the runtime here? How many comparisons does he need to do?

Algorithm Analysis Practice

Mr. Ramanujan is looking for a new coat. He doesn't know where his size is in the rack, so he starts in the middle. Because the rack is ordered, if the size he's checking is smaller, he can look left. If bigger, look right. With the correct half, he'll look in the respective middle of that half. (Round up if fraction.)

Hint: He cuts his search space in half each time. Good to remember high school algebra.

coat 0
coat 1 <- (3) too big
coat 2 <- (4) just right
coat 3 <- (2) too small
coat 4 
coat 5 <- (1) start, too small
coat 6
coat 7
coat 8

"I'm the map!" - Map (10 minutes)

We're going to be working with HashMap. Because HashMap has hash like hash browns, you're going to work at McDonald's.

You just got hired at McDonalds! (As a software engineer.) Your job is to implement a HashMap where the keys are orders, stored as String, and prices, stored as double.

Once you have the menu declared, implement this function to calculate the total for an order.

Menu items include:

"Egg McMuffin" -> 2.79
"Sausage McGriddles - Meal" -> 4.49
"Hot 'N Spicy McChicken Biscuit" -> 2.99
"Big Breakfast with Hot Cakes" -> 5.49

McDonald's Starter Code

import java.util.Map;
import java.util.HashMap;

double computeTotal(String[] order, Map<datatype, datatype> menu) {
  // Your code here.
}

Map<datatype, datatype> menu = // your declaration.

// Add menu items.

String[] order = new String[]{"Egg McMuffin", "Big Breakfast with Hot Cakes"}
System.out.println(computeTotal(order, menu));
// Should print out: 8.28 or 8.280000000000001 because Java...

That's all for today!

Don't worry if the cyclical linked list problem with difficult. Honestly, it could've been a technical interview question for an actual job. But you're close to getting to that point!

Other than linked list, we strengthen your ability to assess runtimes and played with maps!

As always, happy Friday. Have a good, safe time. Do something fun!

Solution Section

Cyclical Linked Lists Solution

Revamped add(). Also add public Item end; to the class.

public void add(int value, int index) {
  assert index >= 0 && index <= this.length;
  
  if (this.length == 0) {
    
    this.start = new Item(value, null);
    this.start.next = this.start;
    this.end = this.start;
    
  } else if (index == 0) {
    
    this.start = new Item(value, this.start);
    this.end.next = this.start;
    
  } else {
    
    int step = 1;
    
    for (Item i = this.start; step <= this.length; i = i.next) {
      
      if (index == step) {
        Item addition = new Item(value, i.next);
        i.next = addition;
        return;
      }
      
      step++;
    }
  }
  this.length++;
}

Cyclical Linked Lists Solution (Cont.)

Printing cycles.

public String toStringCycle(int n) {
  String buffer = "";
  int passes = 0;
  
  for (Item i = this.start; passes < n; i = i.next) {
    buffer += i.value + " -> ";
    
    if (i == this.end) {
      passes++;
    }
  }
  
  return buffer + "...";
}

Algorithm Analysis Solution

  • Ms. Lovelace will need to produce n!n! different lines, so the runtime should be O(n!)O(n!).

  • Mr. Babbage will need to do n×nn \times n comparisons, making his runtime O(n2)O(n^2).

  • Mr. Ramanujan is doing binary search! So the runtime will be O(logn)O(logn).

McDonald's Solution

import java.util.Map;
import java.util.HashMap;

double computeTotal(String[] order, Map<String, Double> menu) {
  
  double total = 0;
  
  for (String item : order) {
    double price = menu.getOrDefault(item, 0.0);
    if (price == 0) {
      System.out.println("Didn't find " + item + ".");
    }
    total += price;
  }
  
  return total;
}

Map<String, Double> menu = new HashMap<>();

// Add menu items.
menu.put("Egg McMuffin", 2.79);
menu.put("Sausage McGriddles - Meal", 4.49);
menu.put("Hot 'N Spicy McChicken Biscuit", 2.99);
menu.put("Big Breakfast with Hot Cakes", 5.49);

String[] order = new String[]{"Egg McMuffin", "Big Breakfast with Hot Cakes"};
System.out.println(computeTotal(order, menu));
// Should print out: 8.28 or 8.280000000000001 because Java...