Section 1
Preview this deck
Combinations
Front
| 5 | 0 | ||
| 4 | 0 | ||
| 3 | 0 | ||
| 2 | 0 | ||
| 1 | 0 |
Active users
0
All-time users
0
Favorites
0
Last updated
5 years ago
Date created
Mar 14, 2020
Cards (95)
Section 1
(50 cards)
Combinations
Repetition is Allowed: such as coins in your pocket (5,5,5,10,10) No Repetition: such as lottery numbers (2,14,15,27,30,33) https://www.mathsisfun.com/combinatorics/combinations-permutations.html
Advantages/Disadvantages of Common Sorting Algorithms
Internal Sorting
An internal sort is any data sorting process that takes place entirely within the main memory of a computer. This is possible whenever the data to be sorted is small enough to all be held in the main memory. For sorting larger datasets, it may be necessary to hold only a chunk of data in memory at a time, since it won't all fit. The rest of the data is normally held on some larger, but slower medium, like a hard-disk. Any reading or writing of data to and from this slower media can slow the sortation process considerably.
Bipartite Graph
Graph can be colored without conflicts while using only two colors.
Heuristics
Any approach to problem solving, learning, or discovery that employs a practical method not guaranteed to be optimal or perfect, but sufficient for the immediate goals. Where finding an optimal solution is impossible or impractical, heuristic methods can be used to speed up the process of finding a satisfactory solution. Heuristics can be mental shortcuts that ease the cognitive load of making a decision. Examples of this method include using a rule of thumb, an educated guess, an intuitive judgment, stereotyping, profiling, or common sense
Recurrence Relation
An equation that is defined in terms of itself. Any polynomial or exponential can be represented by a recurrence.
Divide-and-Conquer Recurrances
T(n) = aT(n/b) + f(n)
Vertex-coloring
Seeks to assign a label (or color) to each vertex of a graph such that no edge links any two vertices of the same color.
Big Oh Notation
Compute XOR of every bit in an integer
Similar to addition, XOR is associative and communicative, so, we need to XOR every bit together. First, XOR the top half with the bottom half. Then, XOR the top quarter of the bottom half with the bottom quarter of the bottom half... x ^= x >> 32 x ^= x >> 16 x ^= x >> 8 x ^= x >> 4 x ^= x >> 2 x ^= x >> 1 x = x & 1
Pre-Order Traversal
1. Process self. 2. Process left child. 3. Process right child.
Bit Array
A bit array is a mapping from some domain (almost always a range of integers) to values in the set {0, 1}. The values can be interpreted as dark/light, absent/present, locked/unlocked, valid/invalid, et cetera. The point is that there are only two possible values, so they can be stored in one bit. As with other arrays, the access to a single bit can be managed by applying an index to the array. Assuming its size (or length) to be n bits, the array can be used to specify a subset of the domain (e.g. {0, 1, 2, ..., n−1}), where a 1-bit indicates the presence and a 0-bit the absence of a number in the set. This set data structure uses about n/w words of space, where w is the number of bits in each machine word. Whether the least significant bit (of the word) or the most significant bit indicates the smallest-index number is largely irrelevant, but the former tends to be preferred (on little-endian machines).
Case Analysis
Analysis pattern. Split the input/execution into a number of cases and solve each case in isolation
Counting Sort
An algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently.[1][2][3] Because counting sort uses key values as indexes into an array, it is not a comparison sort, and the Ω(n log n) lower bound for comparison sorting does not apply to it.
Connected Component
In an undirected graph, a connected component is a maximal set of vertices such that there is a path between every pair of vertices (the example shows 3 connected components).
Recursion
Algorithm design patterns. If the structure of the input is defined in a recursive manner, design a recursive algorithm that follows the input definition.
One-Sided Binary Search
In the absence of an upper bound, we can repeatedly test larger intervals (A[1], A[2], A[4], A[8], A[16], etc) until we find an upper bound, the transition point, p, in at most 2[log p] comparisons. One sided binary search is most useful whenever we are looking for a key that lies close to our current position.
Compute x modulo a power of 2 (y)
x & (y - 1)
In-Order Traversal
1. Process left child. 2. Process self. 3. Process right child.
External Sorting
External sorting is a term for a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory (usually a hard drive). External sorting typically uses a hybrid sort-merge strategy. In the sorting phase, chunks of data small enough to fit in main memory are read, sorted, and written out to a temporary file. In the merge phase, the sorted subfiles are combined into a single larger file. Mergesort is typically preferred.
Geometric series
.
Standard data structure for solving complex bit manipulation
Lookup table
Greedy Algorithms
Algorithm design patterns. Compute a solution in stages, making choices that are local optimum at step; these choices are never undone.
Solving Divide-and-Conquer Recurrances
Case 1: Too many leaves. Case 2: Equal work per level. Case 3: Too expensive a root
Isolate the lowest bit that is 1 in x
x & ~(x - 1)
Permutations
A permutation is an ordered combination. Repetition is Allowed: such as the lock above. It could be "333". No Repetition: for example the first three people in a running race. You can't be first and second. https://www.mathsisfun.com/combinatorics/combinations-permutations.html
Stable Sorting Algorithm
Items with the same key are sorted based on their relative position in the original permutation
Sorting
Algorithm design patterns. Uncover some structure by sorting the input.
Selection Sort
An in-place comparison sort algorithm, O(n^2). The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right
memoization
An optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
Articulation Vertex
The weakest point in a graph
Hamming Weight
The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used (also called the population count, popcount or sideways sum). Algorithm: - Count the number of pairs, then quads, then octs, etc, adding and shifting. v = v - ((v>>1) & 0x55555555); v = (v & 0x33333333) + ((v>>2) & 0x33333333); int count = ((v + (v>>4) & 0xF0F0F0F) * 0x1010101) >> 24;
Depth-First Search
Explore newest unexplored vertices first. Placed discovered vertices in a stack (or used recursion). Partitions edges into two classes: tree edges and back edges. Tree edges discover new vertices; back edges are ancestors.
Replace the lowest bit that is 1 with 0
x & (x - 1)
Divide-and-conquer
Algorithm design patterns. Divide the problem into two or more smaller independent subproblems and solve the original problem using solutions to the subproblems.
Post-Order Traversal
1. Process left child. 2. Process right child. 3. Process self.
Trie
In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are not necessarily associated with every node. Rather, values tend only to be associated with leaves, and with some inner nodes that correspond to keys of interest. For the space-optimized presentation of prefix tree, see compact prefix tree.
Breadth-First Search
Explores the oldest unexplored vertices first. Places discovered vertices in a queue. In an undirected graph: Assigns a direction to each edge, from the discoverer to the discovered, and the discoverer is denoted to be the parent.
Typical runtime of a recursive function with multiple branches
O( branches^depth )
Reduction
Analysis pattern. Use a well-known solution to some other problem as a subroutine.
Arithmetic progressions
For p < -1, this sum always converges to a constant.
Iterative Refinement
Analysis pattern. Most problems can be solved using s brute-force approach. Find such a solution and improve upon it.
Topological Sort
A linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.
Right propagate the rightmost set bit in x
x | (x & ~(x - 1) - 1)
Concrete Examples
Analysis pattern. Manually solve concrete instances of the problem and then build a general solution
Dominance pecking order
Heapify (bubble down)
Swap a node with one of its children, calling bubble_down on the node again until it dominates its children. Each time, place a node that dominates the others as the parent node.
Graph Modeling
Analysis pattern. Describe the problem using a graph and solve it using an existing algorithm.
Adjacency Matrix vs Adjacency List
Invariants
Algorithm design patterns. Identify an invariant and use it to rule out potential solutions that are suboptimal/dominated by other solutions.
Section 2
(45 cards)