cheatsheet2071.docx

**[Week 1:]** - The Arithmetic Logic Unit (ALU): This is the component that performs all necessary calculations on the data that the CPU handles. - The control unit: This dictates how instructions are executed. It does this by sending control signals to other parts of the CPU. - The...

**[Week 1:]** - The Arithmetic Logic Unit (ALU): This is the component that performs all necessary calculations on the data that the CPU handles. - The control unit: This dictates how instructions are executed. It does this by sending control signals to other parts of the CPU. - The registers: Registers are a type of memory that have very fast access times, and generally hold information required by the CPU during calculations. - Memory: This is where program data, as well as program instructions are stored. **[Week 2:]** Passing Arrays to Functions - When passing an array to a function, it is passed by reference - the function knows where the original array is stored in memory, and will be able to modify the contents of the array. Often when passing arrays to functions, it is necessary to also pass the length of the array, as otherwise the function will not know how long the array is. - In the definition of the function, an array is declared as follows: String Methods: **[Week 3:]** Pointers - A pointer is the data type we would use if we wanted to create a variable that stores the address of another variable. We can declare a pointer using \* (the asterisk) as part of the data type. You should always declare pointer variables with a space. We also need to specify what type of variable it will point to (e.g., an int, float, char, etc.), as seen in the example declaration below: - We would read this aloud as \"some\_pointer is a pointer to an integer\". Note the space, as this should be read as \"int pointer called some\_pointer\", and allows us to declare multiple pointers in the same line. - If we want some\_pointer to contain the address of some\_variable, we can assign it like so: - If the address of some\_variable was memory address 0x16b61f308, then the value of some\_pointer is 0x16b61f308, and our memory table might look like the following: Memory Allocation - So far, when we have created variables to hold values, memory has been allocated (marked as in use) and de-allocated or freed (marked as not in use) automatically for us. The compiler figured out how much memory space would need to be used at any point in time for the variables we created. It efficiently stored values without leaving gaps between them in memory. This automatically managed section of memory is called the stack, and there is only a limited amount of memory available for the stack. - We can manually allocate larger amount of memory to be stored in the section of memory that is called the heap. The function to do this is called malloc. - The malloc function is part of the C standard library, which we can include in our program using the line: \#include \ - malloc takes in a single argument, which is the number of bytes we wish to allocate. We can use the sizeof function to determine the number of bytes used for a given data type. malloc returns a void pointer, so it is conventional to cast the pointer into the correct type. - To allocate space for 10,000 integers, we can use the following line: - The malloc function returns a pointer to the start of the allocated space. Once we no longer need the memory allocated on the heap, we should call the free function to allow that memory to be used by other calls to malloc, or by other programs on the computer. It is very important to remember to \'free\' your memory once you are done with it, as otherwise you will introduce the very common (and bad) problem know as a \"memory leak\". Arrays are Pointers - You may have noticed that arrays in C are significantly less powerful than in other languages such as Python. The reason for this is that in C, \'arrays\' are just contiguous blocks of memory - just like what we get when we make a call to malloc! - In C, other than where in memory the space is created, and how the memory will be freed, the two lines are virtually equivalent: int long\_list\_1\[10000\];int \*long\_list\_2 = (int\*)malloc(10000 \* sizeof(int)); - Accessing the values in each block of memory is also equivalent: - The notation using square brackets is called array notation, and the notation using the dereference operator is called pointer offset notation. - As we have already touched on, in C, strings are arrays, and since we now know that arrays are pointers, this answers the riddle of why we never needed to use the address-of operator when using scanf to read in a string - we were already providing scanf with a memory address! **[Week 5:]** The Algorithms we have just introduced to you have the following time complexities: Quick Sort -- O(Nlog(N)) \* (on average, worst case is O(N\^2) too) Bubble Sort - O(N\^2) Linear Search - O(N) Binary Search is O(log(N)) **[Week 6:]** Static testing: Dynamic Testing: What is evaluation? 1. Express integer component as bits. 2. For floating point, keep multiplying it by 2 until the decimal point becomes 0. Each time it isn't 0. Add 0 as a bit. Your final product is the 0.(bitsequence) 3. Add the integer bit and decimal bit parts together. Then shift the decimal place by 2\^n until the decimal point is before the first integer. N + 127 in bit is the value of your exponent. 4. The rest of the decimals after the first decimal point is the value of your mantissa, add leftover 0 where needed. 5. Make the sign bit 1 if it's negative or 0 if it's positive.