---
marp: true
title: 27 Oct 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

---

# <!-- fit --> Big O

---

# Time complexity

* We use Big O notation to describe the time complexity of how the time taken by algorithms scale.

* Typically we (and interviewers) are looking for the worst case complexity.

* Constants don't matter $O(n)$ ~ $O(5n)$ ~ $O(41525235n)$

* $O(1)$ - constant time - the number of operations stays about the same

* $O(log n)$ - logarithmc time - the number of operations incrases in a $log$ pattern.

* $O(n)$ - linear time - the number of operations scales linearly

* $O(n^2)$ - quadratic time - the number of operations scales with the square

---

# Worst instruction

Generally you're limited by the most complex instruction in your code. 

```java
int main() {
  var a = thing_a(); // O(n^3)
  var b = thing_b(); // O(n)
  return a + b;      // O(1)
}
```

In this case $O(n^3)$ is the worst line so that's the overall complexity.

---

# Loop nesting

A good rule of thumb is looking at the nesting of the loops

```java
// O(n)
while (current != null) {
  //
}
``` 

```java
// O(n^3)
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    for (int k = 0; k < n; k++) {
      //
    }
  }
}
```
---

# Problems (5 x 1 minute each)

* Given the code in the next few slides tell the complexity of each in terms of big O

---

```java
int a = 5;
int b = 123;
int c = a + b;
```

---

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

---

```java
var name = "Harsh";
for (int i = 0; i < name.length(); i++) {
  for (int j = 0; j < i; j++) {
    System.out.println(name.substring(j, i));
  }
}
```

---

```java
double[] vector = {3.6, 342.4, 32.1, 23.0};
for (double i = 0; i < vector.length /2; i++) {
  vector[i+vector.length/2] += vector[i];
}
```

---

```java
int n = 125;
for (int num = n; num > 0; num /= 10) {
  System.out.println(num % 10);
}
```

---

# <!-- fit --> ArrayList

---

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

---

# 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)$

---

# Problem (10 minutes)

* ArrayList `int delete(int index)`

* The return value will be what you deleted.

* The size should reduce by one

* Also comment on the $big O$ time nature of your solution. 

---

```java
import java.util.Arrays;
public class ArrayList {
  int[] array;
  public ArrayList(int[] setArray) {
    array = setArray;
  }
  public int delete(int index) {
    return 0; // TODO
  }
  public int size() {
    return 0; // TODO
  }
}
var l = new ArrayList(new int[]{10, 25, 35});
assert l.delete(1) == 25;
System.out.println(Arrays.toString(l.array)); // should be [10, 35]
assert l.size() == 2;
```

---

# <!-- fit --> LinkedList

---

# 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

---

# 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 (15 minutes)

* LinkedList `int delete(int index)`

* Similar to the ArrayList problem from earlier.

* The return value will be what you deleted.

* The size should reduce by one

* Also comment on the $big O$ time nature of your solution. 

---

```java
public class LinkedList {
  Node start;
  Node end;
  class Node {
    int value;
    Node next;
    Node(int setValue, Node setNext) {
      value = setValue;
      next = setNext;
    }
  }
  public int delete(int i) {
    return 0; // implement
  }
  public void addBack(int o) { }
  public String toString() { }
}
var l = new LinkedList();
l.addBack(1);
l.addBack(5);
l.addBack(3);
l.delete(1);
System.out.println(l); // 1 -> 3 ->
```

---

For debugging add this to your code

```java
  public void addBack(int o) {
    if (start == null) {
      start = new Node(o, null);
      end = start;
    } else {
      var prevEnd = end;
      var newEnd = new Node(o, null);
      prevEnd.next = newEnd;
      end = newEnd;
    }
  }
  public String toString() {
    var str = "";
    Node current = start;
    while (current != null) {
      str = str + current.value + " -> ";
      current = current.next;
    }
    return str;
  }
```

---

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

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

---

### 1)

1. $O(1)$

2. $O(n)$

3. $O(n^2)$

4. $O(n)$

5. $O(log n)$

---

### 2)

```java
public int delete(int index) {
    var newArr = new int[size() - 1];
    var deletedValue = array[index];
    for (int i = 0; i < index; i++) {
      newArr[i] = array[i];
    }
    for (int i = index + 1; i < array.length; i++) {
      newArr[i - 1] = array[i];
    }
    array = newArr;
    return deletedValue;
  }
  public int size() {
    return array.length; // TODO
  }
```

---

### 3)

```java
  public int delete(int index) {
    Node current = start;
    for (int i = index; i < index - 1; i++) {
      current = current.next;
    }
    var toReturn = current.next.value;
    current.next = current.next.next;
    return toReturn;
  }

```