There is no substring method in Ruby. We must rely on ranges and expressions.
# Index 0 = c # Index 1 = r # Index 2 = u # Index 3 = s # Index 4 = t value = "crust" # Get substring at indexes 0 through 3. sub1 = value[0..3] # Get substring at indexes 3 through 4. sub2 = value[2..3] # Get substring past index three through end of string. sub3 = value[3..-1] puts sub1 puts sub2 puts sub3 # Output crus us st
The method of solving problems exhibiting the properties or overlapping subproblems.[1] Real-world applications that have been solved using dynamic programming: the magnet selection tool in Photoshop uses dynamic programming.[2]
Also called left-to-right binary exponentiation or square-and-multiply[3].
25. In binary it is 110011001 and then replace each remaining 1 with the pair of letters “sx” and each 0 with the letter “s” to get: sx s s sx (remember, using 1001)In general, binary exponentiation (or square-and-multiply as learned in class) will take less than 2log(n)/log(2) multiplications.
There is also a right-to-left binary exponentiation. It is easier to program but takes more storage.[3]
Fermat’s Little Theorem (non-deterministic) – if p is prime, then 2p divides 2p-2.
Sieve of Eratosthenes (deterministic)
Better to use when you are dealing with a certain range of numbers.
Incrementally testing up to sqrt(n) (deterministic)
Fermat primality test and Miller-Rabin primality test (non-deterministic)
Miller-Rabin has a deterministic variant but you have to balance time complexity and accuracy.
A mapping of keys to values in an efficient manner. Data structure is referred to as a hash-map, hash-table, or dictionary. Choosing the proper hash function depends on the scenario.
Binary Search: Efficient search on sorted data with time complexity of O(log2N). Continue to divide the portion of the list that could have it in half until it is narrowed down to one possible item.
Depth/Breadth First Search: tree/graph traversing and searching.
Merge sort: When you need a stable, O(N log N) sort, this is about your only option. The only downsides to it are that it uses O(N) auxiliary space and has a slightly larger constant than a quick sort. There are some in-place merge sorts, but AFAIK they are all either not stable or worse than O(N log N). Even the O(N log N) in place sorts have so much larger a constant than the plain old merge sort that they’re more theoretical curiosities than useful algorithms.
Quick sort: When you don’t need a stable sort and average case performance matters more than worst case performance. A quick sort is O(N log N) on average, O(N^2) in the worst case. A good implementation uses O(log N) auxiliary storage in the form of stack space for recursion.
Bucket sort: When you can guarantee that your input is approximately uniformly distributed.
Heap sort: When you don’t need a stable sort and you care more about worst case performance than average case performance. It’s guaranteed to be O(N log N), and uses O(1) auxiliary space, meaning that you won’t unexpectedly run out of heap or stack space on very large inputs.
Counting sort: When you are sorting integers with a limited range.
Bubble sort, selection sort: When you’re doing something quick and dirty and for some reason you can’t just use the standard library’s sorting algorithm. The only advantage these have over insertion sort is being slightly easier to implement.
Bogosort: In computer science, bogosort (also known as permutation sort, stupid sort, slowsort, shotgun sort, or monkey sort) is a highly inefficient sorting algorithm based on the generate and test paradigm. The function successively generates permutations of its input until it finds one that is sorted. It is not useful for sorting, but may be used for educational purposes, to contrast it with more efficient algorithms.
[1] https://en.wikiversity.org/wiki/Dynamic_programming
[2] https://www.quora.com/What-are-some-real-world-problems-that-have-been-solved-with-dynamic-programming
[3] https://primes.utm.edu/glossary/page.php?sort=BinaryExponentiation