@Gigili A problem is undecidable if no algorithm, no matter how sophisticated and not matter what runtime is allowed, can always give the correct solutions. You probably notice that there are many angles to restrict the situation.
Is there any "natural" language which is undecidable?
by "Natural" I mean a language defined directly by properties of strings, and not via machines and their equivalent. In other words, if the language looks like
$$ L = \{ \langle M \rangle \mid .... \}$$
where $M$ is a TM, DFA (or regular-exp)...
The current favicon(s) are a menace to society.
They don't sufficiently reflect the purpose of the sites to me. I look at them and I don't immediately think "Computer Science."
I think we should put more effort into this, regardless of the fact that it's still in beta, let alone private beta. E...
I've not gone much deep into CS. So, please forgive me if the question is not good or out of scope for this site.
I've seen in many sites and books, the big-O notations like $O(n)$ which tell the time taken by an algorithm. I've read a few articles about it, but I'm still not able to understand ...
@Gigili You're welcome. Note that what I gave is not a formal definition by any account but an interpretation that is intended to build intuition.
@Gilles I though along similar lines but it got very messy. The important think is considering only singleton alphabets; otherwise you can have many circles. :-/ Therefores, your answer is easy a posteriori, but you have to have the fundamental insight/idea, otherwise it is much harder.
I have been working on dynamic programming in a general setting for some time. The canonical way to evaluate a dynamic programming recursion is by creating a table of all necessary values and filling it row by row. See for example Cormen, Leiserson et al: "Introduction to Algorithms" for an intro...
@Gilles If you have a precise analysis in the sense of operation counts, you can easily concretise your analysis by plugging in numbers. I think this is very useful.
@Raphael @uli “While it is possible to do an exact analysis it is usually more involved to arrive at an exact result. It is nice if such an analysis is possible but it is not always necessary. Because small inputs are not much of a problem, you want to learn what happens when the input size n gets large. Knowing that the algorithm’s complexity is bounded by 5n2+3n−2log(n) is nice but overkill”
and the point of the uniform cost model is similar: you count elementary operations, without having to define in excruciating detail what the elementary operations are for your particular problem
For example, suppose you've defined a precise cost model for the operations involved in a problem statement. Then your solution involves an auxiliary data structure that doesn't fit in the cost model. How do you measure its cost?
@Gilles I know that too, I was merly requesting that “runs in time n^2” should be clarified to either “needs n^2 exchanges” or “needs n^2 comparisons”, by providing a “unit” to avoid guessing.
@uli and I disagree. “Runs in time n^2” means “performs O(n^2) elementary operations”. You don't need to spell out what the elementary operations are if it's not interesting.
@Gilles Oh you have to, especillay in this exam question setting. The task “find an sorting algorithm that runs in time O(n)” is unsolveable when the unit is comparisons but solvable when other elementary operations are counted. You have to specifie it.
If you insist on counting a particular operation, you're open to solutions that do not have the requested cost, because they spend a lot of time doing other stuff
For example, a sort that needs O(n) exchanges but Theta(n!) comparisons is not a linear-time sort
Hm, somebody downvoted my latest question without telling me why. :-/ I was not sure wether is was a good question to ask on SE, but thought I should try it.
so if you asked for a linear-time sort but specified the number of exchanges as the measure, you might get an answer that's true but does not meet the intended requirements
grins I like things being precise, when you do an analysis you do pick operations that you count and others that you dont coun’t, so why not telling it?
It's called abstraction: some problem details matter, others don't. If you pay attention to all the details over time, you can't see the forest for the tree, and you never make any progress
@uli you have 2 minutes to edit your messages (click on the left arrow and select edit)
@uli No! When you do an analysis, often, what's important is the asymptotic behavior of the run time of an actual implementation
@Gilles for asymptotic runtime, it is sufficient to count the dominating operations. Figuring out the dominating ones is part of the analysis then, though.
Take an analysis from Knuth’s TAoCP, he does a lot of work, comes up with results and then throws away the information by only saying “runs in time ...”? No he gives the precise results.
Taking the tree compression as an example: I could say that my solution traverses the source tree exactly once. So in terms of the elementary operations present in the problem statement, I make n operations.
Yet my solution has Theta(n*log(n)) average running time, because I perform operations on each element that do not take constant times. But since I “invented” these operations, they cannot be in the original detailed cost model.
@uli That's not asymptotic behavior. That's a more precise analysis. It wasn't asked there.
In the tree compression question, if you ask for a more precise analysis, you're soon going to need to analyse your environment's memory management operations
@Gilles Perhaps we are looking at things from a different angle. When you do an analysis of an algorithm. Can we agree that it is basically about counting the ops one has selected?
@uli Yes, but only if you look at it from the right angle. Somewhere down the lines, what you want to know is (more or less) how many processor instructions it takes (for a non-distributed algorithm)
Now me, I used to work on program correctness. I was lucky when my problems were decidable, and even elementary techniques tended to be super-exponential in the worst case (fortunately nobody writes programs that trigger worst-case behavior)
And now I'm in industry, where asymptotic behavior is something we keep at the back of our minds, but the really important thing is running time (or other resource consumption) on typical inputs
@Gilles The elementary ops counted can be rather coarse, if dfs is viewed as a black box. The executions of dfs can be counted, but I won’t called it an elementary operation any more.
@Gilles an requesting a uniform cost model only means that you don’t care about the size of the numbers involved. It doesn’t tell you on which operation the emphasis was put on.
@uli you're not answering: why put emphasis on a particular operation?
@uli then I'm not going to ask the running time but the number of times that particular operation is performed. Different question.
If the question is how much time the sort takes, answering with just the number of comparisons is wrong, unless you also show the connection between the running time and the number of comparisons
If the question is the number of comparisons, then of course the answer is the number of comparisons
@Gilles A know we found the needle in the haystack. “The Running Time” in my small world is determined by the operations the contribute to it, that is why I look at them.
@uli and if you're doing algorithm analysis and someone asks you what the running time of an algorithm is, then it's your job to find out what the different operations are, and count them up
the operation breakdown is part of your proof/report, it's not the concise answer to the running time
If we agree that books like TAoCP or CLR or Sedgewick’s Algorithms provide results on “the runnning time“ of algorithms, then what you find there are bounds on the counts of the ops. What else should be “the running time”?
@uli more or less, yes. If you're only looking at asymptotic behavior up to a constant factor, it's equivalent to processor instructions, or elementary operations.
Very early on in university we were cautioned not to focus on actual time units. “the running time” was always used as an abstract concept for all the things you like to focus on. Sometimes as detailed as individual processor operations or as coarse as calling whole other algorithms like dfs.
Let $L_1$, $L_2$, $L_3$, $\dots$ be an infinite sequence of context-free languages, each of
which is defined over a common alphabet $Σ$. Let $L$ be the infinite union of $L_1$, $L_2$, $L_3$, $\dots $;
i.e., $L = L_1 + L_2 + L_3 + \dots $.
Is it always the case that L is a context-free language? Do...
@uli An elementary operation for a modern PC may be any one assembly instruction that is executed (ignoring IO and the like) - we can't say exactly how long such an instruction takes to execute, but we can say that it won't take longer than some constant number (fractions probably) of seconds.
@uli As individual operations take an extremely short time, this only starts taking long if we do a great many of these operations. For just about any algorithm of interest, we only start doing a great number of operations when the input is really large
@uli Hence, we nearly always analyze algorithms on its behavior when the input gets large. We are not interested in exactly how many operations an algorithm does, as we don't even know how long every individual operation takes, but we are interested what kind of behavior the number of operations it takes exhibits when the input becomes large
@uli Even if we can halve the number of comparisons, swaps, xors, or some other operation, that won't matter nearly as much as going from O(n^2) to O(n) if n=1e9. For small n, this may matter, but everything is fast for small n, so this is still uninteresting.
I asked a question on the main site. One of the users suggested to edit it and delete some parts which are covered by a Wikipedia article. When I did it, one of the answerers complained that by the new version half of his answer is not useful and is irrelevant somehow.
I'm not sure what should I...
Why in computer science any complexity which is at most polynomial is considered efficient?
For any practical application(a), algorithms with complexity $n^{\log n}$ are way faster than algorithms that run in time, say, $n^{80}$, but the first is considered inefficient while the latter is effici...
The current favicon(s) are a menace to society.
They don't sufficiently reflect the purpose of the sites to me. I look at them and I don't immediately think "Computer Science."
I think we should put more effort into this, regardless of the fact that it's still in beta, let alone private beta. E...
