3
votes
What is the fastest algorithm for multiplication of two n-digit numbers?
n log(n) by Harvey and van der Hoeven (2021)
This was mentioned in two comments previously (1, 2), but it deserves its own answer.
Title: "Integer ...
3
votes
What are very short programs with unknown halting status?
Overview of Turing Machine decidability starting on the a blank tape (Busy Beaver style)
For the blank tape input only:
4-state machines: all decided in 1983
5-state machines: as of 2023 it is ...
2
votes
Accepted
Is binary tree balanced if and only if the morris traversal of the tree produces ordered list?
A binary tree is a binary search tree iff its inorder traversal yields an ordered list.
Inorder (or symmetric) traversal is recursively defined as left-node-right. This recurrence is of course ...
- 29.5k
2
votes
Is there any computation formalism based on general relativity?
The reason quantum computing is useful is not (just) that the problems in QM are applicable to problems that'd we'd like to solve in computing generally, but because we can physically realize setups ...
- 153
1
vote
Understanding the Recursive Algorithm for Integer Division
Suppose $x$ is divided by $y$, and the quotient is $q$ and remainder is $r$. Then, it means the following:
$$x = q \cdot y + r \quad \quad \textrm{where} \quad r < y. \quad \quad (1)$$
Consider ...
- 5,221
1
vote
Comparing a greedy and a brute force algorithm for NMS
Your description of the problem and your solutions are not very accurate. I will rephrase as follows: "any rectangle that has a sufficient overlap with another rectangle of a higher score must be ...
- 10.3k
Only top scored, non community-wiki answers of a minimum length are eligible