Aghori_Sadhu's blog

Most Difficult Algorithm

By Aghori_Sadhu, 9 years ago, In English

Which algorithm is considered the most difficult Algorithm to understand in computer science ? :D
Is it fft or something else ?
p.s just wanna see the limits of computer programming.

  • Vote: I like it
  • +16
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It depends but linear time planarity testing is really difficult.

→ Reply
»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it

The notion of difficulty is quite subjective. Most of the algorithms used in competitive programming are quite general, in that most of them don't require a person to have specialized knowledge in certain domains to understand the algorithms. The amount of prior knowledge required to understand these algorithms isn't that big.

But things get different as you go deeper and deeper into a specific domain. Now you actually require a lot of preliminary knowledge to actually understand these concepts. For instance, it may be the case that a person working in computer vision research has no idea how an NLP algorithm works. But this doesn't imply computer vision is easier to understand than NLP, it's just that the area of specialization is different.

Even in pure theoretical computer science, there are a lot of areas of specialization, so I don't think it's going to be much different.

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I'd go with fast matrix multiplication algorithm — Coppersmith-Winograd algorithm (1990), improved then by Stothers (2010), Williams (2011) and Le Gall (2014). It depends heavily on abstract algebra (mostly tensor products and powers) and its complexity depends on solution of optimization problem.

You may look at the Le Gall's paper and find out there's some heavy math inside :). I haven't heard of anyone who implemented that. There are two reasons for that — firstly, probably very few people understand what really happens there; secondly, although theoretical complexity, O(n2.3728639), is quite good when compared to O(n3) trivial algorithm, it'll turn out to be very slow when implemented.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Well I've heard before about fast matrix multiplication but never thought it would be that difficult. Thanx for the info and this is really interesting stuff.

    → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It's really easy to implement fft (harder to understand). I agree with k790alex and mnbvmar about their algorithms, but I think that the most difficult one is an algorithm to find max flow in planar graph in linear time.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I will never understand how people are able to implement something without fully understanding what is going on. Maybe somehow that's the case when there's some heavy proof behind some for example greedy idea, but I guess that it's impossible to implement FFT without understanding it.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      They either copy implementations from other sources or they copy it from memory. FFT for example takes just a few lines of code so is really easy to remember or look up. A red black tree on the other hand is conceptually very easy but the implementation is a huge chore.

      → Reply
»
9 years ago, # |
  Vote: I like it +12 Vote: I do not like it

is considered

By whom? If you ask for a personal opinion, nearly every one will be different. If it's a widely held opinion, I'd wager that there's none, but even if there was, personal responses aren't suited to answer that.

For me, the most difficult algorithm is one — or many — which I haven't heard of yet. In long contests (like on Codechef), there tend to be hard problems derived from research papers; after seeing some, I'm fairly certain there are papers with very complex algorithms, even for problems I've seen before.

FFT is still reasonably easy, a large part of FT's mathematical background (especially continuous FT) is taught in schools. Then there's this shit.

→ Reply
»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Algorithms created by researchers nowadays are far far far beyond what one can meet or even heard about when doing CP. FFT is literally absolutely nothing when compared to them.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

just wanna see the limits of computer programming

Go science then, you'll watch them permanently (as well as their advancement).

The most difficult to understand algorithm is the most poorly explained one. It holds for almost any fresh result in CS. Luckily, there are people who constantly try to improve explanations, which sometimes even yields to more simple and practical algorithms.

And here's the quote from “Twenty Questions for Donald Knuth”, which shows these “most difficult algorithms” are up to no good:

Two years ago I needed an algorithm to decide whether G is a so-called comparability graph, and was disappointed by what had been published. I believe that all of the supposedly “most efficient” algorithms for that problem are too complicated to be trustworthy, even if I had a year to implement one of them.

Thus I think the present state of research in algorithm design misunderstands the true nature of efficiency. The literature exhibits a dangerous trend in contemporary views of what deserves to be published.

→ Reply