Data Structures

Question 1

Random Access Memory (RAM)

Answer 1

Defintion:
When a computer is running code, it needs to keep track of variables (numbers, strings, arrays, etc.).

Variables are stored in random access memory (RAM). We sometimes call RAM “working memory” or just “memory.”

Think of RAM like a really tall bookcase with a lot of shelves. Like, billions of shelves.

Example:
RAM is not where mp3s and apps get stored. In addition to “memory,” your computer has storage (sometimes called “persistent storage” or “disc”). While memory is where we keep the variables our functions allocate as they crunch data for us, storage is where we keep files like mp3s, videos, Word documents, and even executable programs or apps.

Memory (or RAM) is faster but has less space, while storage (or “disc”) is slower but has more space. A modern laptop might have ~500GB of storage but only ~16GB of RAM.

Question 2

memory controller

Answer 2

The memory controller does the actual reading and writing to and from RAM. It has a direct connection to each shelf of RAM.

Example: It means we can access address 0 and then immediately access address 918,873 without having to “climb down” our massive bookshelf of RAM

Question 3

binary number

Answer 3

A binary number is a number expressed in the binary numeral system, which represents numbers using two digits: 0 and 1.

Question 4

Bits and Bytes

Answer 4

Computers are very good at determining if a switch is on or off. This can be considered akin to a digit being set as 0 or 1. Because of this and the fact that any number can be represented in binary, computers usually use bits (0s and 1s) to store data.

\large 10110110
10110110

A byte is composed of eight bits; an example byte is shown above. What is the largest number possible (in base 10) of a byte

Question 5

unsigned integer

Answer 5

non-negative, and “integer” means a whole number, not a fraction or decimal

Question 6

fixed-width integers space complexity

Answer 6

fixed-width integers take up constant space or O(1)O(1) space.

Question 7

Abstract data types, commonly abbreviated ADTs

Answer 7

The way of classifying data structures based on how they are used and the behaviors they provide.

Since abstract data types don’t specify an implementation, this means it’s also incorrect to talk about the time complexity of a given abstract data type

Question 8

Big O notation

Answer 8

The notation used when talking about growth rates. It formalizes the notion that two functions “grow at the same rate,” or one function “grows faster than the other,” and such

Question 9

Big O notation Landau Notation

Answer 9

1. f=O(g) (big-oh) if eventually if grows slower than some multiple of g;g;
2. f = o(g)f=o(g) (little-oh) if eventually if grows slower than any multiple of g;g;
3. f = Omega(g)f=Ω(g) (big-omega) if eventually if grows faster than some multiple of g;g;
4. f = omega(g)f=ω(g) (little-omega) if eventually if grows faster than any multiple of g;g;
5. f = Theta(g)f=Θ(g) (theta) if eventually if grows at the same rate as g.g.

Question 10

Big O notation meaning

Answer 10

y, if we have functions f, g such that ff eventually grows slower than some multiple of gg, we say “f = O(g).”“f=O(g).”

Question 11

Fixed-width integers

Answer 11

What happens if we have the number 255 in an 8-bit unsigned integer (1111 1111 in binary) and we add 1? The answer (256) needs a 9th bit (1 0000 0000). But we only have 8 bits!

This is called an integer overflow. At best, we might just get an error. At worst, our computer might compute the correct answer but then just throw out the 9th bit, giving us zero (0000 0000) instead of 256 (1 0000 0000)! (Python actually notices that the result won’t fit and automatically allocates more bits to store the larger number.)