GrailSort

hods have to be employed to guarantee a polynomial bit length. [4] * Fast Fourier Transform. How many bits do you need? When does using 64-bit floating point fail and why? The bit complexity is polynomial and understood but it turns out the most straight forward methods to figure this out uses modular arithmetic to get a handle on the complexity. Also, what's minimum known bit complexity? I'm not sure I know what's bleeding edge for this. [5] * Dynamic programming. Only recently has it been shown that, unless P=NP, O(n^2) is basically optimal. [6] Also, what if you're comparing similar strings? What are the best algorithms in terms of edit distance and other efficiencies. Ukkonnen [7] Hirschberg [8] and checkpointing [9], but boy did it take me a while to get a good description of all of them, with checkpointing still unclear to me. I've heard, and agree with, that 95% of programming doesn't require any deep CS knowledge. The flip side of that is 5% of the time you will and for those 1/20 times you encounter a problem that requires theory, you're dead in the water unless you know how to identify it, how to solve it or where to look for solutions to it. These are just a few. The more I learn the more I realize how little I actually know. [1] https://en.wikipedia.org/wiki/Sorting_algorithm#Stability [2] https://github.com/Mrrl/GrailSort [3] https://github.com/BonzaiThePenguin/WikiSort [4] Chee K. Yap, "Fundamental Problems in Algorithmic Algebra", Chapter 10, Linear Systems, 10.3 Matrix Inversion [5] Chee K. Yap, "Fundamental Problems in Algorithmic Algebra", Chapter 1, Arithmetic, 1.4 Modular Fast Fourier Transform [6] https://rjlipton.wordpress.com/2015/06/01/puzzling-evidence/ [7] https://www.cs.helsinki.fi/u/ukkonen/InfCont85.PDF [8] https://en.wikipedia.org/wiki/Hirschberg%27s_algorithm [9] https://github.com/drpowell/sequence-alignment-checkpointing