All Questions

Filter by
Sorted by
Tagged with
58
votes
8answers
4k views

Algorithmic intuition for logarithmic complexity

I believe I have a reasonable grasp of complexities like $\mathcal{O}(1)$, $\Theta(n)$ and $\Theta(n^2)$. In terms of a list, $\mathcal{O}(1)$ is a constant lookup, so it's just getting the head of ...
57
votes
3answers
36k 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$)...
56
votes
4answers
45k views

Why is it best to use a prime number as a mod in a hashing function?

If I have a list of key values from 1 to 100 and I want to organize them in an array of 11 buckets, I've been taught to form a mod function $$ H = k \bmod \ 11$$ Now all the values will be placed ...
56
votes
3answers
9k views

Dependent types vs refinement types

Could somebody explain the difference between dependent types and refinement types? As I understand it, a refinement type contains all values of a type fulfilling a predicate. Is there a feature of ...
55
votes
12answers
24k views

Does a byte contain 8 bits, or 9?

I read in this assembly programming tutorial that 8 bits are used for data while 1 bit is for parity, which is then used for detecting parity error (caused by hardware fault or electrical disturbance)....
54
votes
9answers
27k views

What is a safe programming language?

Safe programming languages (PL) are gaining popularity. I wonder what is the formal definition of safe PL. For example, C is not safe, but Java is safe. I suspect that the property “safe” should be ...
54
votes
6answers
22k views

If everyone believes P ≠ NP, why is everyone sceptical of proof attempts for P ≠ NP?

Many seem to believe that $P\ne NP$, but many also believe it to be very unlikely that this will ever be proven. Is there not some inconsistency to this? If you hold that such a proof is unlikely, ...
54
votes
9answers
8k views

What would be the real-world implications of a constructive $P=NP$ proof?

I have a high-level understanding of the $P=NP$ problem and I understand that if it were absolutely "proven" to be true with a provided solution, it would open the door for solving numerous problems ...
54
votes
6answers
12k 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 ...
53
votes
8answers
19k views

Is Morse code without spaces uniquely decipherable?

Are all Morse code strings uniquely decipherable? Without the spaces, ......-...-..---.-----.-..-..-.. could be Hello World ...
53
votes
8answers
166k views

What is a the fastest sorting algorithm for an array of integers?

I have come across many sorting algorithms during my high school studies. However, I never know which is the fastest (for a random array of integers). So my questions are: Which is the fastest ...
53
votes
4answers
6k views

Time complexity of a compiler

I am interested in the time complexity of a compiler. Clearly this is a very complicated question as there are many compilers, compiler options and variables to consider. Specifically, I am interested ...
52
votes
7answers
20k views

Is a Turing Machine “by definition” the most powerful machine?

I agree that a Turing Machine can do "all possible mathematical problems". But that is because it is just a machine representation of an algorithm: first do this, then do that, finally output that. ...
51
votes
7answers
27k views

Why does a processor have 32 registers?

I've always wondered why processors stopped at 32 registers. It's by far the fastest piece of the machine, why not just make bigger processors with more registers? Wouldn't that mean less going to the ...
51
votes
4answers
51k views

What is tail recursion?

I know the general concept of recursion. I came across the concept of tail recursion while studying the quicksort algorithm. In this video of quick sort algorithm from MIT at 18:30 seconds the ...
51
votes
5answers
7k views

How is this sorting algorithm Θ(n³) and not Θ(n²), worst-case?

I just starting taking a course on Data Structures and Algorithms and my teaching assistant gave us the following pseudo-code for sorting an array of integers: ...
51
votes
2answers
6k views

How to define quantum Turing machines?

In quantum computation, what is the equivalent model of a Turing machine? It is quite clear to me how quantum circuits can be constructed out of quantum gates, but how can we define a quantum Turing ...
49
votes
6answers
10k views

Keeping a String Secret in (Open) Source Code

I have finished developing an app for Android and intend to publish it with GPL -- I want it to be open source. However, the nature of the application (a game) is that it asks riddles and has the ...
49
votes
6answers
11k views

Why are some games np-complete?

I read the Wikipedia entry about "List of NP-complete problems" and found that games like super mario, pokemon, tetris or candy crush saga are np-complete. How can I imagine np-completeness of a game? ...
49
votes
2answers
7k 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 ...
49
votes
3answers
20k views

Knapsack problem — NP-complete despite dynamic programming solution?

Knapsack problems are easily solved by dynamic programming. Dynamic programming runs in polynomial time; that is why we do it, right? I have read it is actually an NP-complete problem, though, which ...
49
votes
4answers
5k 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 ...
48
votes
3answers
22k views

Why is binary search faster than ternary search?

Searching an array of $N$ elements using binary search takes, in the worst case $\log_2 N$ iterations because, at each step we trim half of our search space. If, instead, we used 'ternary search', we'...
48
votes
2answers
20k views

What happens to the cache contents on a context switch?

In a multicore processor, what happens to the contents of a core's cache (say L1) when a context switch occurs on that cache? Is the behaviour dependent on the architecture or is it a general ...
48
votes
12answers
35k views

How to verify number with Bob without Eve knowing?

You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob ...
47
votes
10answers
6k views

If the speed of electrical charge hasn't changed, how have computers become faster?

Everyone knows computing speed has drastically increased since their invention, and it looks set to continue. But one thing is puzzling me: if you ran an electrical current through a material today, ...
46
votes
10answers
11k views

O(·) is not a function, so how can a function be equal to it?

I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$. I understand semantics of it. But $T(n)$ ...
46
votes
5answers
6k views

Why are so many internet protocols text-based?

From what I have found, a very large amount of protocols that travel over the internet are "text-based" rather than binary. The protocols in question include, but are not limited to HTTP, SMTP, FTP (I ...
46
votes
2answers
7k views

Order of growth definition from Reynolds & Tymann

I am reading a book called Principles of Computer Science (2008), by Carl Reynolds and Paul Tymann (published by Schaum's Outlines). The second chapter introduces algorithms with an example of a ...
46
votes
8answers
71k 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 ...
45
votes
9answers
10k views

Does there exist a priority queue with $O(1)$ extracts?

There are a great many data structures that implement the priority-queue interface: Insert: insert an element into the structure Get-Min: return the smallest element in the structure Extract-Min: ...
45
votes
4answers
11k views

Why are Red-Black trees so popular?

It seems that everywhere I look, data structures are being implemented using red-black trees (std::set in C++, SortedDictionary ...
44
votes
7answers
11k views

Is there anything that MUST be done on a multi-core CPU?

When considering how multi-thread-friendly our program must be, my team puzzled about whether there's anything that absolutely cannot be done on a single-core CPU. I posited that graphics processing ...
44
votes
8answers
14k views

How are variables stored in and retrieved from the program stack?

Apologies in advance for the naivety of this question. I am a 50 year old artist trying to properly understand computers really for the first time. So here goes. I have been trying to understand how ...
44
votes
5answers
13k views

Why has research on genetic algorithms slowed?

While discussing some intro level topics today, including the use of genetic algorithms; I was told that research has really slowed in this field. The reason given was that most people are focusing on ...
44
votes
7answers
65k views

Minimum spanning tree vs Shortest path

What is the difference between minimum spanning tree algorithm and a shortest path algorithm? In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and ...
44
votes
2answers
4k views

How does the Y combinator exemplify “Lambda calculus inconsistency”?

On the Wikipedia page for Fixed Point Combinators is written the rather mysterious text The Y combinator is an example of what makes the Lambda calculus inconsistent. So it should be regarded with ...
44
votes
2answers
3k 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))$. ...
44
votes
2answers
1k views

Determining capabilities of a min-heap (or other exotic) state machines

See the end of this post for some clarification on the definition(s) of min-heap automata. One can imagine using a variety of data structures for storing information for use by state machines. For ...
44
votes
3answers
46k views

Longest path in an undirected tree with only one traversal

There is this standard algorithm for finding longest path in undirected trees using two depth-first searches: Start DFS from a random vertex $v$ and find the farthest vertex from it; say it is $v'$. ...
43
votes
6answers
8k views

Learning Automated Theorem Proving

I am learning Automated Theorem Proving / SMT solvers / Proof Assistants by myself and post a series of questions about the process, starting here. Note that these topics are not easily digested ...
43
votes
2answers
68k views

Find median of unsorted array in $O(n)$ time

To find the median of an unsorted array, we can make a min-heap in $O(n\log n)$ time for $n$ elements, and then we can extract one by one $n/2$ elements to get the median. But this approach would take ...
42
votes
3answers
8k views

Why can humans solve certain “undecidable” problems?

High-order pattern matching is an undecidable problem. That means there is no algorithm that, given an equation a => b, where ...
42
votes
4answers
46k views

Difference between Parallel and Concurrent programming?

When looking at concurrent programming, two terms are commonly used i.e. concurrent and parallel. And some programming languages specifically claim support for parallel programming, such as Java. ...
42
votes
2answers
14k views

How to show that a function is not computable?

I know that there exist 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 ...
42
votes
1answer
12k 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'...
41
votes
9answers
15k views

Why are some programming languages Turing complete but lack some abilities of other languages?

I came across an odd problem when writing an interpreter that (should) hooks to external programs/functions: Functions in 'C' and 'C++' can't hook variadic functions, e.g. I can't make a function that ...
41
votes
6answers
4k 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?
41
votes
1answer
5k views

What makes type inference for dependent types undecidable?

I have seen it mentioned that dependent type systems are not inferable, but are checkable. I was wondering if there is a simple explanation of why that is so, and whether or not there is there a limit ...
40
votes
5answers
9k views

Iteration can replace Recursion?

I've been seeing all over stack Overflow, e.g here, here, here, here, here and some others I don't care to mention, that "any program that uses recursion can be converted to a program using only ...

15 30 50 per page