New answers tagged ds.algorithms
3
Breaking news! A fresh result dating back to Monday:
The Petri net reachibility problem was
shown to have an Ackermannian lower bound
(paper), which matches the complexity
of the best known algorithm. Thus, the latter algorithm is optimal (if
one ignores some function in the complexity that is much smaller than
Ackermann, making the difference between ...
6
There are plenty of places that need algorithmic research in practical applications. Just to give you some examples:
My current company makes a specialised machine learning supercomputer. Most of our engineers have primarily academic background; in fact, this is a particular challenge for us, since many of them are not used to doing software engineering, ...
5
In my experience (a few decades of "business" style IT, having studied CS myself) there were very few occasions where we actually programmed "interesting" algorithms, and a majority of my colleagues did not have a real CS background - if they studied it, then theoretical CS certainly did not interest them that much, judging by our non-...
1
For this question, Levin's universal search should be mentioned somewhere. This is an algorithm that is constant-factor optimal for some problems, although we generally do not know which problems nor how fast it runs.
The idea is to dovetail the computations of all possible Turing machines, weighted by $\exp(-$ description length $)$, checking each possible ...
11
It really depends on what you mean with "higher algorithms".
I work in game development, and we use graph theory, linear and nonlinear optimization, computational geometry, dynamic programming, and lots of other fun stuff.
If you work in robotics, simulations, industrial control software, aerospace industry, etc., there will be plenty of stuff that ...
21
A friend of mine works on the combinatorics of Sturmian words, and did so for years. A Sturmian word is typically obtained from a straight line drawn on a lattice: whenever the line crosses an horizontal edge of the lattice, output an 1; whenever it crosses a vertical edge, output a 0.
From my point of view, this is quite theoretical.
Yet, my friend was ...
2
The minimum spanning tree problem has an algorithm that was proven to be optimal by Pettie and Ramachandran, and they did so by essentially brute forcing decision trees corresponding to MSTs, and using them to construct the actual MST. However, the runtime is unknown, other than the fact that it is optimal.
Top 50 recent answers are included
