All Questions
4,254
questions
194
votes
3
answers
25k
views
Is there a system behind the magic of algorithm analysis?
There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis). Many are similar, for instance those asking for a cost analysis ...
- 71.9k
94
votes
11
answers
28k
views
Solving or approximating recurrence relations for sequences of numbers
In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested ...
- 71.9k
41
votes
6
answers
19k
views
Sorting functions by asymptotic growth
Assume I have a list of functions, for example
$\qquad n^{\log \log(n)}, 2^n, n!, n^3, n \ln n, \dots$
How do I sort them asymptotically, i.e. after the relation defined by
$\qquad f \leq_O g \...
- 619
95
votes
10
answers
174k
views
How to prove that a language is not regular?
We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a ...
- 71.9k
325
votes
7
answers
155k
views
What is the definition of P, NP, NP-complete and NP-hard?
I'm in a course about computing and complexity, and am unable to understand what these terms mean.
All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea ...
- 4,249
53
votes
9
answers
123k
views
How to prove a language is regular?
There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular?
For instance, if I am given that $L$ is regular,
how can I prove that ...
- 879
98
votes
5
answers
101k
views
How to prove that a language is not context-free?
We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free....
- 71.9k
28
votes
2
answers
45k
views
How to prove that a language is context-free?
There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free?
What techniques are there to prove this? Obviously, one way is to exhibit ...
D.W.♦
- 154k
101
votes
3
answers
34k
views
How does one know which notation of time complexity analysis to use?
In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity.
However, there are ...
- 1,323
138
votes
4
answers
202k
views
How to convert finite automata to regular expressions?
Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and ...
- 71.9k
45
votes
4
answers
19k
views
What are common techniques for reducing problems to each other?
In computability and complexity theory (and maybe other fields), reductions are ubiquitous. There are many kinds, but the principle remains the same: show that one problem $L_1$ is at least as hard as ...
- 71.9k
25
votes
1
answer
9k
views
How to show that L = L(G)?
Specifying formal languages by giving formal grammars is a frequent task: we need grammars not only to describe languages, but also to parse them, or even do proper science. In all cases, it is ...
- 71.9k
79
votes
3
answers
52k
views
Express boolean logic operations in zero-one integer linear programming (ILP)
I have an integer linear program (ILP) with some variables $x_i$ that are intended to represent boolean values. The $x_i$'s are constrained to be integers and to hold either 0 or 1 ($0 \le x_i \le 1$)...
D.W.♦
- 154k
48
votes
6
answers
52k
views
How to prove greedy algorithm is correct
I have a greedy algorithm that I suspect might be correct, but I'm not sure. How do I check whether it is correct? What are the techniques to use for proving a greedy algorithm correct? Are there ...
D.W.♦
- 154k
146
votes
3
answers
19k
views
How can it be decidable whether $\pi$ has some sequence of digits?
We were given the following exercise.
Let
$\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$
...
- 71.9k
45
votes
2
answers
21k
views
How to show that a function is not computable? How to show a language is not computably enumerable?
I know that there exists a Turing Machine, if a function is computable. Then how to show that the function is not computable or there aren't any Turing Machine for that. Is there anything like a ...
- 2,181
49
votes
4
answers
70k
views
How do O and Ω relate to worst and best case?
Today we discussed in a lecture a very simple algorithm for finding an element in a sorted array using binary search. We were asked to determine its asymptotic complexity for an array of $n$ elements.
...
- 1,035
40
votes
5
answers
120k
views
How to come up with the runtime of algorithms? [duplicate]
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 ...
- 523
85
votes
6
answers
22k
views
How can we assume that basic operations on numbers take constant time?
Normally in algorithms we do not care about comparison, addition, or subtraction of numbers -- we assume they run in time $O(1)$. For example, we assume this when we say that comparison-based sorting ...
user742
37
votes
2
answers
17k
views
How do I construct reductions between problems to prove a problem is NP-complete?
I am taking a complexity course and I am having trouble with coming up with reductions between NPC problems. How can I find reductions between problems? Is there a general trick that I can use? How ...
- 371
53
votes
1
answer
23k
views
Show that { xy ∣ |x| = |y|, x ≠ y } is context-free
I remember coming across the following question about a language that supposedly is context-free, but I was unable to find a proof of the fact. Have I perhaps misremembered the question?
Anyway, here'...
- 20.2k
50
votes
2
answers
9k
views
What is the difference between an algorithm, a language and a problem?
It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and ...
- 29.6k
52
votes
6
answers
7k
views
Dealing with intractability: NP-complete problems
Assume that I am a programmer and I have an NP-complete problem that I need to solve it. What methods are available to deal with NPC problems? Is there a survey or something similar on this topic?
- 621
32
votes
3
answers
6k
views
Encoding 1-out-of-n constraint for SAT solvers
I'm using a SAT solver to encode a problem, and as part of the SAT instance, I have boolean variables $x_1,x_2,\dots,x_n$ where it is intended that exactly one of these should be true and the rest ...
D.W.♦
- 154k
25
votes
4
answers
3k
views
How to fool the plot inspection heuristic?
Over here, Dave Clarke proposed that in order to compare asymptotic growth you should plot the functions at hand. As a theoretically inclined computer scientist, I call(ed) this vodoo as a plot is ...
- 71.9k
70
votes
6
answers
20k
views
Are there minimum criteria for a programming language being Turing complete?
Does there exist a set of programming language constructs in a programming language in order for it to be considered Turing Complete?
From what I can tell from wikipedia, the language needs to ...
- 1,441
5
votes
2
answers
13k
views
How do I find a regular expression for a particular language?
I have a language, and I want to find a regular expression for the language. How do I do that? Is there a step-by-step, systematic procedure for that? Pretend I am just learning this topic; what ...
D.W.♦
- 154k
53
votes
4
answers
6k
views
What is the meaning of $O(m+n)$?
This is a basic question, but I'm thinking that $O(m+n)$ is the same as $O(\max(m,n))$, since the larger term should dominate as we go to infinity? Also, that would be different from $O(\min(m,n))$. ...
- 1,572
181
votes
13
answers
65k
views
Why, really, is the Halting Problem so important?
I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia article correctly explains that a deterministic machine ...
- 2,543
74
votes
4
answers
33k
views
(When) is hash table lookup O(1)?
It is often said that hash table lookup operates in constant time: you compute the hash value, which gives you an index for an array lookup. Yet this ignores collisions; in the worst case, every item ...
30
votes
2
answers
5k
views
Why are the total functions not enumerable?
We learned about the concept of enumerations of functions. In practice, they correspond to programming languages.
In a passing remark, the professor mentioned that the class of all total functions (i....
- 71.9k
24
votes
2
answers
4k
views
Reduce the following problem to SAT
Here is the problem. Given $k, n, T_1, \ldots, T_m$, where each $T_i \subseteq \{1, \ldots, n\}$. Is there a subset $S \subseteq \{1, \ldots, n\}$ with size at most $k$ such that $S \cap T_i \neq \...
- 1,121
33
votes
2
answers
14k
views
Optimization version of decision problems
It is known that each optimization/search problem has an equivalent decision problem. For example the shortest path problem
optimization/search version:
Given an undirected unweighted graph $G ...
bek
65
votes
2
answers
10k
views
Are there subexponential-time algorithms for NP-complete problems?
Are there NP-complete problems which have proven subexponential-time algorithms?
I am asking for the general case inputs, I am not talking about tractable special cases here.
By sub-exponential, I ...
- 781
34
votes
6
answers
14k
views
Differences and relationships between randomized and nondeterministic algorithms?
What differences and relationships are between randomized algorithms and nondeterministic algorithms?
From Wikipedia
A randomized algorithm is an algorithm which employs a degree of
randomness ...
- 4,825
75
votes
1
answer
15k
views
Language theoretic comparison of LL and LR grammars
People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over ...
- 71.9k
40
votes
3
answers
5k
views
Decision problems vs "real" problems that aren't yes-or-no
I read in many places that some problems are difficult to approximate (it is NP-hard to approximate them). But approximation is not a decision problem: the answer is a real number and not Yes or No. ...
- 20.6k
40
votes
7
answers
4k
views
Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms
In algorithms and complexity we focus on the asymptotic complexity of algorithms, i.e. the amount of resources an algorithm uses as the size of the input goes to infinity.
In practice, what is ...
- 22.1k
45
votes
2
answers
9k
views
Perplexed by Rice's theorem
Summary: According to Rice's theorem, everything is impossible. And yet, I do this supposedly impossible stuff all the time!
Of course, Rice's theorem doesn't simply say "everything is impossible". ...
25
votes
7
answers
6k
views
Justification for neglecting constant factors in Big O
Many a times if the complexities are having constants such as 3n, we neglect this constant and say O(n) and not O(3n). I am unable to understand how can we neglect such three fold change? Some thing ...
- 1,779
380
votes
12
answers
345k
views
Why is quicksort better than other sorting algorithms in practice?
In a standard algorithms course we are taught that quicksort is $O(n \log n)$ on average and $O(n^2)$ in the worst case. At the same time, other sorting algorithms are studied which are $O(n \log n)$ ...
- 5,475
56
votes
4
answers
9k
views
Why polynomial time is called "efficient"?
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 ...
- 20.6k
42
votes
6
answers
6k
views
How does a computer work?
I have been a computer nerd for many many years. I can program in quite a few languages, and I can even build them. I sat down with a buddy the other day and asked how a computer actually takes ...
- 529
21
votes
1
answer
7k
views
Languages that satisfy the pumping lemma but aren't regular?
Given a regular language $L$, then it is easy to prove that there is a constant $N$ such that is $\sigma \in L$, with $\lvert \sigma \rvert \ge N$ there exist strings $\alpha$, $\beta$ and $\gamma$ ...
- 13.9k
12
votes
4
answers
7k
views
NFA with exponential number of states when determinized
How can I build an example of a regular language where the minimal DFA has $2^n$ states and the minimal NFA has $n$ states? Obviously the DFA's state-set should contain all subsets of the the NFA's ...
- 3,660
29
votes
6
answers
45k
views
Why Do Computers Use the Binary Number System (0,1)?
Why Do Computers Use the Binary Number System (0,1)? Why don't they use Ternary Number System (0,1,2) or any other number system instead?
- 449
14
votes
2
answers
16k
views
When can I use dynamic programming to reduce the time complexity of my recursive algorithm?
Dynamic programming can reduce the time needed to perform a recursive algorithm. I know that dynamic programming can help reduce the time complexity of algorithms. Are the general conditions such that ...
- 141
36
votes
4
answers
5k
views
What is dynamic programming about?
Sorry in advance if this question sounds dumb...
As far as I know, building an algorithm using dynamic programming works this way:
express the problem as a recurrence relation;
implement the ...
- 463
35
votes
7
answers
10k
views
What are the simplest examples of programs that we do not know whether they terminate?
The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. ...
- 4,117
30
votes
5
answers
20k
views
Is O(mn) considered "linear" or "quadratic" growth?
If I have some function whose time complexity is O(mn), where m and n are the sizes of its two inputs, would we call its time complexity "linear" (since it's linear in both m and n) or "quadratic" (...
- 1,177