Cool Algorithms

bogosort

>>8884780
Combsort: O(n^2) average case but keeps up with Merge/Heap/Quicksort which proves CS is worthless.

>>8884799
I don't think you understand CS if you think comb sort keeps up with quick sort or merge sort

>>8884780
sum=0
for i in range(0, infinity):
sum+=i

print(sum)

output:-1/12

>>8884809
True that

>>8884809

Code it up and see. It's within a factor of 2~4 of the other algorithms when n is well into the hundreds of millions.

This is what you get for ignoring constant factors in the real world.

>>8884784
Can I get a quick rundown on bogosort?

>>8884821
>Efficient sorts bow down to it

>>8884819
If you're trying to make a comment about O(n) analysis, it's a measure of how the function grows, not the actual efficiency.

>>8884819
>2-4 times slower than a real algorithm

I'm supposed to be impressed?

>>8884821
>consider an array of numbers
>find random permutations of the numbers
>that is, till you find one that is sorted.
>there's your answer.

>>8884799

False. The better performance you see in practice can be seen when you consider the asymptotic average-case analysis of the algorithm. The body of techniques within the sub-field of algorithmic analysis is more than robust enough to encompass this phenomenon. Just because you aren't educated enough to know of these techniques doesn't mean that they don't exist, and it certainly doesn't mean that "CS is worthless."

By the way, there are also models of computational analysis which are, in fact, sensitive to constants.

I think the ellipsoid method of solving convex optimization problems is pretty interesting. In addition to being the first strongly polynomial-time algorithm for solving linear programs in the general case, it's pretty neat in that it lends itself so well to such an intuitive geometric interpretation.

File: Capture.jpg (109KB, 1088x455px) Image search: [Google]

109KB, 1088x455px

>>8884780
Damerau–Levenshtein distance because pic related.

What it does: https://en.wikipedia.org/wiki/Edit_distance

+ I used it to make my first auto correct, and I was super excited about it. (not the best way for making an auto correct btw)

>>8884831
>The better performance you see in practice can be seen when you consider the asymptotic average-case analysis of the algorithm

Average case [math]IS[/math] what he was referring to.

http://stackoverflow.com/questions/22595728/what-is-the-running-time-of-comb-sort

>>8884780
https://en.wikipedia.org/wiki/Fast_inverse_square_root