Remember, "the answer" is only half of it! Also, make sure everyone in your group can explain why.

We will use this Gradescope Online Assignment as our worksheet for in-class work. These problems are coded as being worth points for our simplicity, but will not impact your grade in the course.

Question 2

Question 2.1 CPU

RAM and CPU serve entirely different functions of the computer. CPU is the "brain" that executes instructions while RAM is a place to store data we are working with.

Question 2.2 Disk

Both RAM and Disk store data, but they generally store it for different purposes. RAM is the "working memory" of the computer to store values necessary for running a program, while Disk is the "long term memory" of the computer for things that should stick around forever (e.g. your documents). Disk is much slower than RAM in terms of data access times, but can generally store a much larger amount of data.

Question 2.3 Cache

Both RAM and the Cache act as the place to store values used in computation. Caches tend to be much smaller than RAM in terms of space, but they are much quicker in terms of access time. The Cache "sits between" the CPU and RAM to store recently accessed values.

Question 3

Question 3.1

public void sum(int[] arr, int loc, int target) {
   for (int i = 0; i < target; i++) {
      arr[loc] += i;
   }
}

Temporal locality because we are accessing the same piece of data (arr[loc]) over and over again to sum up the values.

Question 3.2

public void addTwo(int[] arr) {
   for (int i = 0; i < arr.length; i++) {
      arr[i]+= 2;
   }
}

Spatial locality because when an address is accessed from the RAM it is pulling the nearby addresses also up to the cache, and since arrays are contiguous you can access those other addresses also from the cache

Question 3.3

public class MyLinkedList<T> {
   private Node<T> front;
   private static class Node<T> {
      public final T data;
      public Node<T> next;

         // constructors omitted for space
   }

	// we are looking at the following method that uses the MyLinkedList class
	public void removeFront(int k) {
	   Node<T> curr = this.front;
	   Node<T> prev = null;
	   for (int i = 0; i < k; i++) {
	      prev = curr;
	      curr = curr.next;
	      prev.next = null;
	   }
	   this.front = curr;
	}
}

Neither. This is using a linkedlist, a linked list is not stored continuously in RAM so when we access one element from the list, other elements that come after are not accessed and put in the cache, therefore you are making many trips to RAM which take longer than trips to the cache

Question 4