---
marp: true
title: 1 Dec 2020
---

# <!-- fit --> CS 199 EMP

## <!-- fit --> Even More Practice

---

# <!-- fit --> Attendance Link:

https://forms.gle/8yto1LvJ4hntiKNu7

---

# 2 meetings every week Tuesday and Thursday

* Early CST - Early risers and Eastern timezones

* Evening CST - Western timezones (and really late Eastern folks)

* Calendar contains zoom links

* Attend 7 sessions for credit, attendence via google form.

---

# Format

* 3 practice problems every session

* focused on practical understanding of concepts covered recently in class

* slides and material available after both sessions

--- 

# How to follow along

* Small breakout rooms of working together 

* Work for 10-15 minutes together, feel free to use paper, whiteboards, online share tools.

* Use the code playground on the 125 homepage for the interactive running

---

# Arrays, Lists and Maps

aka the 3 data structures you'll use the most and stuff you can do more or less anything with

---

# <!-- fit --> Arrays

---

# What are arrays

* Blocks of continous data stored in memory.

* Fixed in size and single data type - makes arrays super fast.

* $O(1)$ get and set a value `array[i] = 5` or `System.out.println(array[i])`

* $O(1)$ get length `array.length`

* You can have arrays nested inside arrays - these are called multidimensional arrays. `double[][] matrix` is an example of a 2d double array.

---

# Reivew: For loops

Arrays go hand in hand with for loops

* For single dimensional arrays, often it pairs well with a single `for` loop

* For many dimensions we can use multiple nested `for` loops. 

* Loop variables we conventionally use `i`, `j`, `k`...

```java
int[][] vals = {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}};
for (int i = 0; i < vals.length; i++) {
  for (int j = 0; j < vals[i].length; j++) {
    System.out.print(vals[i][j] + " ");
  }
  System.out.println(); // newline
}
```

--- 

# Reivew: For each loop/Enhanced

Sometimes when we don't need `i`, `j` or other counter variables we can use for each loops. This makes readability nicer.

```java
int[][] vals = {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}};
for (int[] subArr: vals) {
  for (int item: subArr) {
    System.out.print(item + " ");
  }
  System.out.println(); // newline
}
```

---

# Problem (5 minutes)

* Take a dot product of two arrays that represent vectors.

* If both arrays are not the same length, or either array is `null` throw an `IllegalArgumentException` 

* Recall that the dot product is multiplying each component and summing it up. 

* So if $a = <1, 2, 3>$ and $b = <1, 10, 100>$ then $a \dot b = 1 * 1 + 2*10 + 3*100 = 321$

---

```java
int dot(int[] a, int[] b) {
  return 0;
}

int[] a = {1, 2, 3};
int[] b = {1, 10, 100};
int[] c = {1, 2, 3, 4};
int[] d = null;
assert dot(a, b) == 321;
try {
  dot(b, c);
  dot(b, d);
} catch (IllegalArgumentException e) {
  System.out.println("This should happen");
}
```
---

# <!-- fit --> Lists

---

# Lists

* They're like arrays, except not fixed size.

* This means they're often slower, but the flexibility is worth it quite often. 

* It's $O(n)$ to add but most of the time you're only adding to the start or end, and those can be optimized.

* This is an abstract class so you have to use either `ArrayList` or `LinkedList` (or make your own hehe)

---

# Review: ArrayList 

* Here we implement `List` by just using an `Array` on the inside.

* Which works great since we can just implement almost all our functionality just using what arrays can already do

* `get(i)` is just `array[i]` - $O(1)$

* `set(i, element)` is just `array[i] = element` - $O(1)$

* `size()` is just `array.length` - $O(1)$

* For specific code refer to the 125 lectures.

---

# Review: Array List add resize

* Resizing gets more complicated 

* When you add elements you have to resize a new array which is larger and copy everything over.

* a) Copy everything as is till the index you want to insert at b

* b) At the index insert it in

* c) After that resume copying (make sure to account for offsets)

* For reference: Look at the `ArrayList` homework.

* Due to the loops this has the complexity $O(n)$

---

# Review: LinkedList

* A list that is connected by different elements that link to each other.

* `'a' -> 'b' -> 'd' -> 'c' -> 'e' -> null` 

* We just have to store the `start` point and know how to go to the `next` point. 

* To do anything we always need to start at `start` and then traverse till we find the node we're looking for.

* `get(i)` - go through the elements till you get to element `i` - $O(n)$

* `set(i, value)` - go through the elements till you get to element `i` and then set that. - $O(n)$

* `size()` - go through all elements while incrementing a counter - $O(n)$

* Alternatively you can implement a variable to store `length` as well to make `size()` $O(1)$ but then you increase the storage space. This is fine in _most_ cases

---

# Review: LinkedList resize add

* In the last slide, it seems that linked lists are basically awful. Why even use them?

* It makes adding and resizing pretty fine. ArrayLists you have to constantly copy over and create new arrays when things are added.

* `add(i, value)` - go through elements till you get to the one you want then create a new `Node` with the old `next` as the `next` of that Node. The previous `next` will become linked to the new `Node`

* This is can be $O(n)$ because even if the addition is $O(1)$, the time to find that node can still take $O(n)$

* But in some special cases, adding can be $O(1)$ like if you add to the `start`.

* If you store a variable for the `end` of the list then you can do $O(1)$ addition there. 

* Adding to the start and end is the most common when adding items to the list, so these special cases make it quite worthwhile. 

---

# Problem (10 minutes)

* Get the size of a linked list

* Make sure to handle empty lists as well

---

```java
public class Node {
  int value;
  Node next;
  public Node(int setValue, Node setNext) {
    value = setValue;
    next = setNext;
  }
}

int size(Node list) {
  return 0;
}

var list = new Node(5, new Node(6, new Node(7, null)));
var oneItem = new Node(10, null);
Node emptyList = null;
assert size(list) == 3;
assert size(oneItem) == 1;
assert size(emptyList) == 0;
```

---

# <!-- fit --> Maps

---

# Maps

* These are like arrays, except instead of indexes we can have objects as the keys

* One key points to one value

* In java we commonly use hashmaps that convert the key into a number using a hash function.

* Maps have really fast read and writes, and so it's convinient for lots of things.

* Sometimes we use maps to store already computed results in a process called memoization. 

* In your MP you've realized that JSON is also another type of map

---

# Review: Hashing

```java
@Override public int hashCode() {
  return Objects.hash(x, y, z);
}
```

* (From Lecture) A hash function is any function that can be used to map data of arbitrary size to fixed-size values.
* Every input in a hash function should produce a unique hash, otherwise, we have a **hash collision**
  * Birthday Paradox
  * The larger the hash, the less likley we are to have hash collisions (exponential)
  * Git uses a 160 bit hash function

---

# Problem (15 minutes)

* Suppose I have a map of `<String, Integer>` of student grades in a class and I want to understand how things went in a covid19 remote semester.

* Print the name of the student who scored the most points. 

* Print the number of students who need a CR, that is students in the range of $[70, 83)$

* Print the average score of the class

---

```java
import java.util.HashMap;

var grades = new HashMap<String, Integer>();
grades.put("Alice", 71);
grades.put("Bob", 43);
grades.put("Clara", 94);

int maxScore = -1; // or some impossible value
var maxName = "";
double scoreSum = 0;
int peopleWhoNeedCr = 0;

System.out.println("Best student: " + maxName);
System.out.println("Average: " + average);
System.out.println("Students who need CR: " + peopleWhoNeedCr);
```


---

#  <!-- fit --> Solutions 
## <!-- fit --> (no peeking, it's for your own good!)

---

## <!-- fit --> (no seriously, attempt the problems with your groupmates first!)

---

### 1)

```java
int dot(int[] a, int[] b) {
  if (a == null || b == null || a.length != b.length) {
    throw new IllegalArgumentException();
  }
  int sum = 0;
  for (int i = 0; i < a.length; i++) {
    sum += a[i] * b[i];
  }
  return sum;
}
```

---

### 2)

```java
int size(Node list) {
  int count = 0;
  while (list != null) {
    list = list.next;
    count++;
  }
  return count;
}
```

---

### 3)

```java
import java.util.HashMap;

var grades = new HashMap<String, Integer>();
grades.put("Alice", 71);
grades.put("Bob", 43);
grades.put("Clara", 94);

int maxScore = -1; // or some impossible value
var maxName = "";
double scoreSum = 0;
int peopleWhoNeedCr = 0;
for (var entry : grades.entrySet()) {
  var name = entry.getKey();
  var score = entry.getValue(); 
  scoreSum += score;
  if (maxScore < score) {
    maxScore = score;
    maxName = name;
  }
  if (score >= 70 && score < 83) {
    peopleWhoNeedCr++;
  }
}
double average = scoreSum / grades.size();
```