# All Questions

4,102 questions
Filter by
Sorted by
Tagged with
24k 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 ...
25k 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 ...
17k views

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 \... 94 votes 10 answers 162k 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 ... 316 votes 7 answers 150k 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 ... 96 votes 5 answers 94k 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.... 52 votes 8 answers 112k 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 ... 28 votes 2 answers 42k 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 ... 99 votes 3 answers 32k 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 ... 136 votes 4 answers 197k 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 ... 43 votes 4 answers 17k 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 ... 25 votes 1 answer 8k 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 ... 73 votes 3 answers 49k 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$)... 42 votes 3 answers 44k 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 ... 45 votes 2 answers 20k 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 ... 145 votes 3 answers 18k 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}$... 39 votes 5 answers 119k 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 ... 48 votes 4 answers 65k 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. ... 83 votes 6 answers 20k 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 ... 37 votes 2 answers 15k 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 ... 48 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 ... 49 votes 1 answer 21k 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'... 46 votes 6 answers 6k 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? 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 ... 68 votes 6 answers 18k 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 ... 31 votes 3 answers 5k 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 ... 50 votes 4 answers 5k 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))$. ... 177 votes 13 answers 60k 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 ... 73 votes 4 answers 32k 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.... 30 votes 2 answers 12k 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 ... 12k 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 ...
9k 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 ...
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. ...
13k 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 ...
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 ...
8k 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". ...
339k 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)$ ...
14k 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 ...
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 ...
6k 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$ ...
6k 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 ...
5k 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 ...