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.

Filter by
Sorted by
Tagged with
1 vote
1 answer

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 "...
Sam's user avatar
  • 123
2 votes
2 answers

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 (...
senseiwu's user avatar
  • 175
6 votes
1 answer

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?
Yuval Filmus's user avatar
13 votes
3 answers

Why nondeterminism?

Theory of computation often involves nondeterministic models of computation. Some examples include nondeterministic finite automata (NFAs), nondeterministic pushdown automata (PDAs), and ...
Yuval Filmus's user avatar
10 votes
1 answer

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 ...
flashburn's user avatar
  • 1,213
194 votes
3 answers

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 ...
Raphael's user avatar
  • 72k
49 votes
4 answers

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. ...
Smajl's user avatar
  • 1,045
28 votes
2 answers

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.'s user avatar
  • 156k
50 votes
2 answers

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 ...
jmite's user avatar
  • 29.7k
25 votes
1 answer

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 ...
Raphael's user avatar
  • 72k
45 votes
4 answers

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 ...
Raphael's user avatar
  • 72k
45 votes
2 answers

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 ...
user5507's user avatar
  • 2,181
326 votes
7 answers

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 ...
Mirrana's user avatar
  • 4,259
40 votes
7 answers

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 ...
Ricky Stam's user avatar
20 votes
1 answer

How do I write a proof using induction on the length of the input string?

In my Computing Theory course, a lot of our problems involve using induction on the length of the input string to prove statements about finite automata. I understand mathematical induction, however ...
tcdowney's user avatar
  • 303
42 votes
6 answers

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 ...
Christian's user avatar
  • 529
94 votes
11 answers

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 ...
Raphael's user avatar
  • 72k
139 votes
4 answers

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 ...
Raphael's user avatar
  • 72k
105 votes
5 answers

How not to solve P=NP?

There are lots of attempts at proving either $\mathsf{P} = \mathsf{NP} $ or $\mathsf{P} \neq \mathsf{NP}$, and naturally many people think about the question, having ideas for proving either direction....
Raphael's user avatar
  • 72k
86 votes
6 answers

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 ...
user avatar
52 votes
6 answers

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?
Anonymous's user avatar
  • 621
53 votes
9 answers

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 ...
corium's user avatar
  • 879
96 votes
10 answers

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 ...
Raphael's user avatar
  • 72k
41 votes
6 answers

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 \...
JAN's user avatar
  • 619
98 votes
5 answers

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....
Raphael's user avatar
  • 72k
40 votes
5 answers

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 ...
Code0987's user avatar
  • 523
101 votes
3 answers

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 ...
Jack H's user avatar
  • 1,323
76 votes
1 answer

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 ...
Raphael's user avatar
  • 72k