Evil
  • Member for 6 years, 6 months
  • Last seen this week
  • Poland
If everyone believes P ≠ NP, why is everyone sceptical of proof attempts for P ≠ NP?
44 votes

Beliefs are orthogonal to proofs. Belief may direct attempted solutions by researchers or rather their main interest but this does not prevent them from checking a proof anyway. The problem with $P \...

View answer
How long does the Collatz recursion run?
Accepted answer
31 votes

This is Collatz conjecture - still open problem. Conjecture is about proof that this sequence stops for any input, since this is unresolved, we do not know how to solve this runtime recurrence ...

View answer
How can a language whose compiler is written in C ever be faster than C?
23 votes

There is one forgotten thing about optimisation here. There was longish debate about fortran outperforming C. Putting apart malformed debate: the same code was written in C and fortran (as testers ...

View answer
Why don't we use quick sort on a linked list?
Accepted answer
22 votes

The memory access pattern in Quicksort is random, also the out-of-the-box implementation is in-place, so it uses many swaps if cells to achieve ordered result. At the same time the merge sort is ...

View answer
Is the halting problem decidable for pure programs on an ideal computer?
16 votes

No it is not, and moreover it does not depend on I/O. Simple counterexample: write a program to find a perfect odd number (this is an open problem: we do not know yet whether one exists) - it does ...

View answer
What is meant by superlinear speedup? Is it possible to have superlinear speedup in practice?
Accepted answer
13 votes

With equation: not really. Superlinear speedup comes from exceeding naively calculated speedup even after taking into account the communication process (which is fading, but still this is the ...

View answer
Interpretation of for loop.
13 votes

There is another interpretation, both $i, j$ might be variables, in that case it is double loop: for every $j$ in $\{0,\ldots,n-1\}$:   for every $i$ in $\{0,\ldots,n-1\}$:   &...

View answer
What is the fastest online sorting algorithm?
Accepted answer
11 votes

I suggest Tree Sort, variant with self-balanced tree. In this case complexity is $O(logn)$ (per insertion). In that case you can access sorted structure at any time. If inputs comes in batches, ...

View answer
Which other programming languages apart from Python and predecessor are out there using indentation to define code blocks?
10 votes

There are: Elm, Haskell, its predecessor Miranda and its predecessor ISWIM, YAML where spaces are crucial for syntax and tabs are forbidden, OCCAM, Coffee script and Cokescript both are language to ...

View answer
What is the difference between oblivious and non-oblivious merging, sorting etc
Accepted answer
10 votes

Oblivious means that the control flow is independent of some properties of data. For example Bitonic Sort (also known as sorting net_ is oblivious, because it always compares the same elements ...

View answer
Why is b-tree search O(log n)?
Accepted answer
9 votes

You have introduced $n$ and $m$ as the order of B-tree, I will stick to $m$. Their height will be in the best case $\lceil log_m(N + 1) \rceil$, and the worst case is height $\lceil log_{\frac{m}{2}}(...

View answer
Regular expressions and 'capturing parentheses' with 'backreferences'
Accepted answer
8 votes

The RE in the Automata Theory are equivalent to FA, but for the programming languages (regexp) this is no longer true. The regular expressions in the programming languages (like PCRE) are far more ...

View answer
What makes a language "optimized" for a specific task?
8 votes

The constraints of some languages makes it easier to implement faster code (e.g. Fortran vs C and the pointers aliasing) which is a tradeoff between out-of-the-box performance and possibilities). The ...

View answer
Why does a MP3 encoder use a fast Fourier transform before applying the psychoacoustic model?
Accepted answer
8 votes

I would suggest a more detailed explanation of mp3 codec. FFT is applied on the time domain signal, so in fact it does not use the result from the MDCT. The input to the psychoacoustic models is in ...

View answer
Why does a color video compress better than a black and white video?
Accepted answer
8 votes

Human eye is very sensitive to luminance change and order of magnitude less sensitive to chrominance change. MPEG under the hood is based on JPEG transform, so you have 8x8 blocks of DCT. It blurs a ...

View answer
Why is the sequence "3,3,4,5,2" considered a bitonic sequence?
Accepted answer
7 votes

Bitonic sequence is defined for example for parallel sort, as non-decreasing and then non-increasing sequence, to allow duplicates. See here: Bitonic sequence. Also Wikipedia article about Bitonic ...

View answer
Are "method" and "function" synonyms?
Accepted answer
7 votes

These are a different level classifications: A method is a function (or procedure) associated with object – a concept from Object Oriented Programming. A function is the logical unit (a piece ...

View answer
Complexity of sorting a 1-sorted array
6 votes

There is hidden linear time to perform merge part of sorting algorithm. Linear is less than loglinear, so it was not visible. $\log1=0$, but it means that you will not e.g. heapify, just merge in $O(n)...

View answer
Why is a (collision-less) hashtable lookup really O(1)?
6 votes

Hash function calculates array position from given string. If this is perfect hash it means that there are for sure no collisions, the most probably array is at least twice bigger than number of ...

View answer
Looking for an algorithm to identify contiguous repeated series of lines in a long string
5 votes

Build suffix tree using Ukkonen's algorithm, this way in $\mathcal O(n)$ you will find all substrings in provided text with indices. In the case of approximate matching, there is also extended ...

View answer
find an element in array that appeared at least 51% times
Accepted answer
5 votes

If element appears more than 50% of time, you can use Median of medians algorithm by Blum et. al. It is not deterministic though. Or use specialized algorithm by Boyer and Moore called "Majority vote ...

View answer
Comparison using only bitwise operators (and return -1 or 0)
Accepted answer
5 votes

The first step is to take $c = a \text{ XOR } b$, this will return $0$ if the numbers were equal or some bits set to $1$ otherwise. Now to calculate the result the $c$ variable should be ORed with its ...

View answer
Compute equality comparison without comparison operators
Accepted answer
5 votes

Let $W$ be the number of bits, $A, B$ integers to compare. $Result = (NOT((A - B) \text{ OR } (B - A))) >> (W - 1)$. Here NOT negates bits. $A - B$ and $B - A$ is zero iff numbers are equal ...

View answer
Why do you need to fill the first element of array when implementing heap?
Accepted answer
5 votes

It is not some magic element but $-\infty$, which is because this is min-heap, in max-heap it would be $\infty$. The sole purpose is consistent representation of all elements inserted - it guarantees ...

View answer
KD-Tree implementation with lat/lon coordinates
Accepted answer
5 votes

Short answer: No, you will not get the same results. It does not matter what coordinate system or what geographic standard you are using, it is not possible to make projection from sphere into ...

View answer
Why not use large $k$ in a $k$-ary tree?
Accepted answer
5 votes

BTrees are used in practice - file systems, database with $k$ for example equal 1024 or 4096, so it seems to be bigger than binary. Probably you have not encountered need yet. For example ternary ...

View answer
Automated optimization of 0-1 matrix vector multiplication
Accepted answer
5 votes

If it is possible try to exploit banded tridiagonal nature of matrix. Otherwise if the matrix contains only a constant number of distinct values (which surely is being binary), you should try Mailman ...

View answer
What is the use of Horner's Method?
5 votes

Yes, exactly as you said. This is used to decrease the number of multiplications, so it is more efficient than computing it the normal way. Example: You have the polynomial $ax^3 + bx^2 + cx + d$...

View answer
Will this algorithm always solve a constrained sudoku puzzle in quadratic time?
Accepted answer
4 votes

Let me start from correctness check, will this method always generate grids abiding sudoku rules? In fact yes, your shift operator is simply circulant matrix, scattering boxes. Since circulant matrix ...

View answer
Minimum amount of swaps needed to sort a stack
4 votes

Your problem is known as Pancake sorting and it is not true that $f(n) < n$. The minimum number of swaps is between $\frac{15n}{14}$ and $\frac{18n}{11}$. Currently we know empirically that $P_{17}...

View answer
1
2 3 4 5
9