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

Arrays, Lists and Maps

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

Arrays

What are arrays

  • Blocks of continous data stored in memory.

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

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

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

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.

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>a = <1, 2, 3> and b=<1,10,100>b = <1, 10, 100> then ab˙=1∗1+2∗10+3∗100=321a \dot b = 1 * 1 + 2*10 + 3*100 = 321

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

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

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

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)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 (10 minutes)

  • Get the size of a linked list

  • Make sure to handle empty lists as well

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;

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

@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)[70, 83)

  • Print the average score of the class

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

Solutions

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

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

1)

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)

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

3)

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