Binary Representation, Matrices, Algorithms, and Sorting
Binary Repartition
Binary Representation:
- Signed Magnitude: The first bit determines if the number is negative (the sign bit). The rest of the bits represent the magnitude (mantissa).
- One’s Complement: Similar to signed magnitude, but if the number is negative, all bits in the magnitude are inverted.
- Two’s Complement: Similar to one’s complement, but 1 is added to the inverted magnitude if the number is negative.
- Biased Representation: Similar to signed magnitude, but a bias is added to the target number.
IE754 Binary Representation
To calculate the bias, determine the number of exponent bits, subtract 1, and raise 2 to that power. Then, subtract 1 from the result. This is your bias.
Matrices
When multiplying matrices, for the first resulting element, you only multiply from the first row of the first matrix and the first column of the second matrix. This is why the entire top row in the example uses 2 and 4 for multiplication.
To check if two matrices can be multiplied, the number of columns in the first matrix must equal the number of rows in the second matrix. In the example, the first matrix is 3×2, and the second is 2×4. Since both have a ‘2’, they can be multiplied.
For matrix addition, the matrices must have the exact same dimensions. You can verify the result by observing how the corresponding elements are added, going down the rows and then along the columns.
Reductions
Reduction involves breaking down an algorithm into two connected parts, a smaller one (B) and a larger one (A).
Algorithm A is broken down into A and B, with A being the larger one. The correctness of B is checked by seeing if A works. If A doesn’t work, then B cannot work.
Halting Problem
The halting problem occurs when two algorithms rely on each other to terminate. Algorithm A needs algorithm B to stop, but algorithm B needs algorithm A to stop, resulting in neither algorithm working.
Recursion is when an algorithm calls upon itself.
Asymptotic Notation
Multiple notations can be true. For example, if A grows faster than B, it means A can grow at least as fast and at the same rate as B. This is used for predicting speed.
Worst-Case and Best-Case Analysis
Insertion sort with binary search has a worst-case time complexity of O(n log n) and a best-case time complexity of O(n). N is O(1) is incorrect. Space complexity refers to the amount of memory used.
Pivot Search / Quick Sort
- Pick a number to be the pivot. This is moved to the end.
- Select an item from the left that is greater than the pivot, and then an item from the right that is smaller than the pivot.
- Swap the selected items and continue until the right index is smaller than the left index.
Often, the middle element is chosen as the pivot.
Quick Select
Quick select is based on quick sort, where you find an element of a specific type, such as the second smallest element.
The difference is that once you’ve partitioned the array into two sub-arrays around the pivot, you only look at the partition that contains the desired element, such as the smaller partition if you’re looking for a smaller element.
Turing Machine
Insertion Sort
Insertion sort goes from left to right, comparing each element to its neighbors.
Insertion Binary
Start sorting the array. When you move to a new number, compare it to the already sorted portion. Check if it’s greater than the middle element of the sorted portion and move accordingly. Then, find a new middle. If there are only 1-2 elements left, this process helps determine the correct placement.
Heap Sort
Create a binary tree from the array, going from left to right. Reorder the tree from highest to lowest. Remove the highest element, add it to a new array, and repeat until the tree is empty.
Merge Sort
Break down the array into smaller sub-arrays. Once fully broken down, begin to reassemble them in sorted order. The intermediate steps (often represented by grey blocks) are usually ignored as a single step.
Selection Sort
- Go through the array to find the lowest value.
- Move the lowest value to the front of the unsorted part of the array.
- Repeat steps 1 and 2 for the remaining unsorted portion of the array until the entire array is sorted.