All Questions
47,703
questions
383
votes
12
answers
346k
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)$ ...
- 5,505
326
votes
7
answers
156k
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,259
218
votes
32
answers
53k
views
Why is writing down mathematical proofs more fault-proof than writing computer code?
I have noticed that I find it far easier to write down mathematical proofs without making any mistakes, than to write down a computer program without bugs.
It seems that this is something more ...
- 3,632
194
votes
10
answers
55k
views
How can a language whose compiler is written in C ever be faster than C?
Taking a look at Julia's webpage, you can see some benchmarks of several languages across several algorithms (timings shown below). How can a language with a compiler originally written in C, ...
- 1,983
194
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 ...
- 72k
181
votes
13
answers
65k
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 ...
- 2,543
146
votes
3
answers
19k
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}$
...
- 72k
145
votes
12
answers
43k
views
Why are there so many programming languages?
I'm pretty fluent in C/C++, and can make my way around the various scripting languages (awk/sed/perl). I've started using python a lot more because it combines some of the nifty aspects of C++ with ...
- 5,387
139
votes
4
answers
204k
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 ...
- 72k
137
votes
3
answers
47k
views
BIT: What is the intuition behind a binary indexed tree and how was it thought about?
A binary indexed tree has very less or relatively no literature as compared to other data structures. The only place where it is taught is the topcoder tutorial. Although the tutorial is complete in ...
- 1,545
137
votes
7
answers
40k
views
Is Category Theory useful for learning functional programming?
I'm learning Haskell and I'm fascinated by the language. However I have no serious math or CS background. But I am an experienced software programmer.
I want to learn category theory so I can become ...
dan
132
votes
14
answers
21k
views
Why can I look at a graph and immediately find the closest point to another point, but it takes me O(n) time through programming?
Let me clarify:
Given a scatterplot of some given number of points n, if I want to find the closest point to any point in the plot mentally, I can immediately ignore most points in the graph, ...
- 1,417
128
votes
15
answers
16k
views
How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect
To try to test whether an algorithm for some problem is correct, the usual starting point is to try running the algorithm by hand on a number of simple test cases -- try it on a few example problem ...
D.W.♦
- 156k
127
votes
5
answers
151k
views
What's the difference between a binary search tree and a binary heap?
These two seem very similar and have almost an identical structure. What's the difference? What are the time complexities for different operations of each?
- 1,751
127
votes
6
answers
15k
views
Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?
Most of today's encryption, such as the RSA, relies on the integer factorization, which is not believed to be a NP-hard problem, but it belongs to BQP, which makes it vulnerable to quantum computers. ...
- 3,078
112
votes
9
answers
104k
views
How/when is calculus used in Computer Science?
Many computer science programs require two or three calculus classes.
I'm wondering, how and when is calculus used in computer science? The CS content of a degree in computer science tends to focus ...
- 1,299
110
votes
2
answers
79k
views
Quicksort Partitioning: Hoare vs. Lomuto
There are two quicksort partition methods mentioned in Cormen:
(the argument A is the array, and [p, r] is the range, inclusive,...
- 2,901
107
votes
7
answers
86k
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 ...
- 2,957
105
votes
5
answers
18k
views
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....
- 72k
103
votes
7
answers
22k
views
Why is deep learning hyped despite bad VC dimension?
The Vapnik–Chervonenkis (VC)-dimension formula for neural networks ranges from $O(E)$ to $O(E^2)$, with $O(E^2V^2)$ in the worst case, where $E$ is the number of edges and $V$ is the number of nodes. ...
- 1,409
101
votes
5
answers
10k
views
What are the reasons to learn different algorithms / data structures serving the same purpose?
I have been wondering about this question since I was an undergraduate student.
It is a general question but I will elaborate with examples below.
I have seen a lot of algorithms - for example, for ...
- 1,200
101
votes
3
answers
34k
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 ...
- 1,323
98
votes
5
answers
102k
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....
- 72k
96
votes
10
answers
177k
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 ...
- 72k
95
votes
13
answers
25k
views
What are GPUs bad at?
I understand that GPUs are generally used to do LOTS of calculations in parallel. I understand why we would want to parallelize processes in order to speed things up. However, GPUs aren't always ...
- 1,111
94
votes
11
answers
28k
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 ...
- 72k
93
votes
7
answers
23k
views
Why are some programming languages "faster" or "slower" than others?
I have noticed that some applications or algorithms that are built on a programming language, say C++/Rust run faster or snappier than those built on say, Java/Node.js, running on the same machine. I ...
- 1,362
92
votes
6
answers
17k
views
Is there any concrete relation between Gödel's incompleteness theorem, the halting problem and universal Turing machines?
I've always thought vaguely that the answer to the above question was affirmative along the following lines. Gödel's incompleteness theorem and the undecidability of the halting problem both being ...
- 1,023
89
votes
11
answers
26k
views
Why is the unit of image size not Pixel²?
If you calculate the area of a rectangle, you just multiply the height and the width and get back the unit squared.
Example:
5cm * 10cm = 50cm²
In contrast, if you calculate the size of an image, you ...
- 1,007
86
votes
6
answers
22k
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 ...
user742
85
votes
8
answers
59k
views
Graph searching: Breadth-first vs. depth-first
When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)).
Now, are ...
- 975
81
votes
6
answers
29k
views
Formal program verification in practice
As a software engineer, I write a lot of code for industrial products. Relatively complicated stuff with classes, threads, some design efforts, but also some compromises for performance. I do a lot of ...
- 1,572
80
votes
3
answers
49k
views
How do computers keep track of time?
How are computers able to tell the correct time and date every time?
Whenever I close the computer (shut it down) all connections and processes inside stop. How is it that when I open the computer ...
- 937
80
votes
3
answers
53k
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$)...
D.W.♦
- 156k
79
votes
2
answers
8k
views
What does the "Lambda" in "Lambda calculus" stand for?
I've been reading about Lambda calculus recently but strangely I can't find an explanation for why it is called "Lambda" or where the expression comes from.
Can anyone explain the origins of the term?...
- 1,100
79
votes
2
answers
12k
views
What is coinduction?
I've heard of (structural) induction. It allows you to build up finite structures from smaller ones and gives you proof principles for reasoning about such structures. The idea is clear enough.
But ...
- 20.2k
78
votes
9
answers
23k
views
Why is addition as fast as bit-wise operations in modern processors?
I know that bit-wise operations are so fast on modern processors, because they can operate on 32 or 64 bits on parallel, so bit-wise operations take only one clock cycle. However addition is a complex ...
- 1,331
78
votes
5
answers
15k
views
What important/crucial real-world applications use blockchain?
As part of some blockchain-related research I am currently undertaking, the notion of using blockchains for a variety of real-world applications are thrown about loosely.
Therefore, I propose the ...
- 863
77
votes
6
answers
17k
views
Why is the Turing Machine a popular model of computation?
I am a CS undergraduate. I understand how Turing came up with his abstract machine (modeling a person doing a computation), but it seems to me to be an awkward, inelegant abstraction. Why do we ...
- 903
76
votes
8
answers
66k
views
Floyd's Cycle detection algorithm | Determining the starting point of cycle
I am seeking help understanding Floyd's cycle detection algorithm. I have gone through the explanation on wikipedia (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare)
I can see how the ...
- 863
76
votes
4
answers
73k
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 ...
- 1,191
76
votes
9
answers
11k
views
What properties of a programming language make compilation impossible?
Question:
"Certain properties of a programming language may require that the only way to get the code written in it be executed is by interpretation. In other words, compilation to a native machine ...
76
votes
4
answers
16k
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 ...
- 29.6k
76
votes
1
answer
15k
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 ...
- 72k
74
votes
4
answers
33k
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 ...
72
votes
4
answers
115k
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 ...
- 841
71
votes
10
answers
113k
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 ...
- 1,213
71
votes
6
answers
20k
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 ...
- 1,451
71
votes
4
answers
17k
views
What is the novelty in MapReduce?
A few years ago, MapReduce was hailed as revolution of distributed programming. There have also been critics but by and large there was an enthusiastic hype. It even got patented! [1]
The name is ...
- 72k
69
votes
10
answers
12k
views
Can a dynamic language like Ruby/Python reach C/C++ like performance?
I wonder if it is possible to build compilers for dynamic languages like Ruby to have similar and comparable performance to C/C++? From what I understand about compilers, take Ruby for instance, ...
- 815