--- marp: true title: 09 April 2021 theme: default paginate: true --- # 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. --- ![bg 80%](../../pics/linked_list.svg) --- ![bg 80%](../../pics/cyclic_list.svg) --- # 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 $n$ 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 $n$ times. (10 minutes) --- # Cyclical Linked List Starter Code java 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. java 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. java 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 $n$ 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-1$ screws until he's gone through all $n$ 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 java import java.util.Map; import java.util.HashMap; double computeTotal(String[] order, Map menu) { // Your code here. } Map 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. java 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. java 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!$ different lines, so the runtime should be $O(n!)$. - Mr. Babbage will need to do $n \times n$ comparisons, making his runtime $O(n^2)$. - Mr. Ramanujan is doing binary search! So the runtime will be $O(logn)$. --- # McDonald's Solution java import java.util.Map; import java.util.HashMap; double computeTotal(String[] order, Map 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 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...