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.

Questions with a broad scope about general methods and concepts, such as proof-methods, tools for algorithm analysis or basics of computer architecture. Answers apply to many more specific problems.

See our full, ordered list with an explanatory text.

This is not for questions asking for references, i.e. books or articles introducing a certain concept or providing a certain result; for such use . This tag is semi-reserved and should not be used for most new questions. If you're not sure whether this tag is applicable: err on the side of not using this tag.

30 questions
48
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 Pumping lemma? Similarly, how can we show a language…
user5507
  • 2,261
  • 4
  • 25
  • 41
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 \iff f \in O(g)$, assuming they are indeed pairwise…
JAN
  • 619
  • 1
  • 6
  • 10
41
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 electricity and does something with it, and we just…
Christian
  • 519
  • 5
  • 6
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 A,B,C,D,...? Is it somewhere stored in the hardware…
Ricky Stam
  • 501
  • 1
  • 5
  • 7
40
votes
5 answers

How to come up with the runtime of algorithms?

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…
Code0987
  • 523
  • 1
  • 5
  • 8
30
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 a context-free grammar for the language. Are there…
D.W.
  • 170,893
  • 23
  • 241
  • 528
26
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 important that the grammar at hand is correct , that…
Raphael
  • 73,461
  • 31
  • 185
  • 415
21
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 when strings come into play I get real tripped up.…
tcdowney
  • 313
  • 1
  • 2
  • 7
15
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 nondeterministic Turing machines. Real computers, however, are…
Yuval Filmus
  • 281,565
  • 27
  • 323
  • 519
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 not regular. What's gone wrong? I've found a way of…
flashburn
  • 1,233
  • 1
  • 13
  • 22
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
  • 281,565
  • 27
  • 323
  • 519
3
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 (linked lists, stacks etc.) and basic sorting and…
senseiwu
  • 185
  • 6
1
vote
2 answers

A weird strict inequality

In his book , Oded Goldreich infers from $$Pr[X_n\in B_n]<\rho(n)$$ that $$Pr[X_n\in \{0,1\}^*\setminus B_n]>1-\rho(n).$$ My Question is why this last $>$ is not $\geq$ as the negation of $Pr[X_n\in B_n]<\rho(n)$ would give ?? Please forgive me…
user2925716
  • 153
  • 6
1
vote
1 answer

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 Wright "An Introduction to Optimization" by Chong and Zak and half a…
Fraïssé
  • 821
  • 11
  • 20
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 "Chomsky Hierarchy", but perhaps it is covered with a…
Sam
  • 207
  • 1
  • 6
1
2