CS 199 EMP

Even More Practice

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

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(n) ~ O(5n)O(5n) ~ O(41525235n)O(41525235n)

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

  • O(logn)O(log n) - logarithmc time - the number of operations incrases in a loglog pattern.

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

  • O(n2)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.

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

In this case O(n3)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

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

// 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
int a = 5;
int b = 123;
int c = a + b;

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

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

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

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

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)O(1)

  • set(i, element) is just array[i] = element - O(1)O(1)

  • size() is just array.length - O(1)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)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 bigObig O time nature of your solution.

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;

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)O(n)

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

  • size() - go through all elements while incrementing a counter - O(n)O(n)

  • Alternatively you can implement a variable to store length as well to make size() O(1)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)O(n) because even if the addition is O(1)O(1), the time to find that node can still take O(n)O(n)

  • But in some special cases, adding can be O(1)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)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 bigObig O time nature of your solution.

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

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

Solutions

(no peeking, it's for your own good!)

(no seriously, attempt the problems with your groupmates first!)

1)

1. O(1)O(1)

2. O(n)O(n)

3. O(n2)O(n^2)

4. O(n)O(n)

5. O(log n)O(log n)

2)

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)

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