data structures and algorithms

data structure

way of structing data inside the ram

random access memory

where all the data is stored longterm

what does the random indicate in RAM?

can jump to any address in the same amount of time

what is ram measured in

bytes

a byte is how many bits?

8

bit

a position that can store either 1 or 0

Integers are represented with how many bytes

4 bytes or 32 bits ex:1 is represented by 31 0s and one 1

address

value stored in distinct location

arrays are stored in RAM in what way?

Contiguous

ASCII characters take up how many bytes?

one byte

address = start +(index*size) is what time complexity

o(1) because it plugs the index of desired into the formula and automatically gets it

linked list are stored in what way?

non-contiguous( stored across address with pointers connecting them

call stack

region of ram that tracks where you are in the programs chain of function calls

what happens in the call stack when a function is called?

pushes a stack frame onto the call stack

StackOverFlow

recursion with no base case

Heap

holds dynamically allocated data that needs to outlive the function that created it

CPU(central processing unit)

brain of computer

register

handful of storage spots (16- 32) built directly into the cpu

ALU(arithmetic logic unit)

does actual math and logic

control unit

located in the cpu; reads instruction one at a time and orchestrates everything

clock

a timer that paces every step in the cpu

cache locality

pool of memory that sits between the CPU and RAM

L1 cache

tiny(tens of KB) 1ns access

L2 cache

biggers than L1(hundreds of KB) 3-10ns access

L3 Cache

bigger than L2 cache (severalMB) and 10-20ns access

how much time does it take to access RAM

100ns access

how many bytes of data does the CPU fetch and then store in cache

64 bytes

when grabing arr[0] it also grabs arr[0] to arr[7] what does this explain

why sequential is faster

what flavor of cache locality has to do with pulling data near what you just accessed?

spatial locality

what flavor of cache locality has to do with accessing same data again

temporal locality