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 ...
Ciro Santilli OurBigBook.com's user avatar
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 ...
Ciro Santilli OurBigBook.com's user avatar
2 votes

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 ...
Hendrik Jan's user avatar
  • 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 ...
redroid's user avatar
  • 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 ...
Inuyasha Yagami's user avatar
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 ...
Yves Daoust's user avatar
  • 10.3k

Only top scored, non community-wiki answers of a minimum length are eligible