Questions tagged [reference-question]
Reserved -- shouldn't be used for most new questions. Questions with a broad scope about general methods and concepts, such as proof methods, tools for algorithm analysis or basics of computer architecture. This is not for questions asking for references, i.e. books or articles.
29
questions
1
vote
1
answer
34
views
Seeking a reference for NP-hardness of optimization problems
Most optimization textbooks do not cover the concept of NP-hardness. Some examples include:
"Convex optimization" by Boyd and Vandenberghe
"Numerical Optimization" by Nocedal and ...
- 821
1
vote
1
answer
49
views
Does Sipser's _Introduction to the Theory of Computation_ cover the Chomsky hierarchy?
I saw the book suggested here.
Does Sipser's Introduction to the Theory of Computation cover the Chomsky hierarchy?
I ask since, looking through a pdf copy of the book, I found no matches with "...
- 143
3
votes
2
answers
255
views
MOOC recommendations for learning algorithms based on topics covered in Daspupta, Papadimitriou & Vazirani
I would appreciate some advise/mentoring on self-study of algorithms. Based on my several years of work as a software developer (non CS background), I have some good grip on standard data structures (...
- 185
6
votes
1
answer
955
views
What does the "big O complexity" of a function mean?
What do people mean when they refer to the "big O complexity" of a function? What is the big O complexity of $9n^2 + 10n$, for example?
- 278k
14
votes
3
answers
1k
views
Why nondeterminism?
Theory of computation often involves nondeterministic models of computation. Some examples include nondeterministic finite automata (NFAs), nondeterministic pushdown automata (PDAs), and ...
- 278k
10
votes
1
answer
2k
views
What's wrong with my pumping lemma proof?
The language $L = \{0^{2n} \space |\space n \ge 0 \}$ is obviously regular – for example, it matches the regular expression $(00)^*$. But the following pumping lemma argument seems to show it's ...
- 1,223
197
votes
3
answers
26k
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 ...
- 72.7k
49
votes
4
answers
72k
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,045
28
votes
2
answers
48k
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.♦
- 162k
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.8k
27
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 ...
- 72.7k
45
votes
4
answers
20k
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 ...
- 72.7k
45
votes
2
answers
22k
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,191
331
votes
7
answers
160k
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,329
40
votes
7
answers
34k
views
How does the computer determine whether a number is smaller or greater than another?
It might sound like a stupid question but I'm really curious to know how a computer knows that $1<2$? Also, how does a computer know that the order of integer is $1,2,3,4,5,\ldots$ and alphabet is ...
- 501