23 votes

How AlphaDev improved sorting algorithms?

This is not a new sorting algorithm. It's much more interesting than that. AlphaDev appears to have produced a new technique for superoptimisation. You can think of the superoptimisation problem as ...
Pseudonym's user avatar
  • 22.1k
18 votes

False proofs that look correct

One of my favourites is the "brothers paradox": https://en.wikipedia.org/wiki/Boy_or_Girl_paradox I tell it as I learned it*, as follows: in a village, each family has two children, elder ...
Shaull's user avatar
  • 17.2k
16 votes

False proofs that look correct

Merge-sort can be done in linear time! Indeed, the time complexity to sort a list or array of length $n$ verifies$^{(1)}$: $$T(n) = T\left(\left\lfloor\frac{n}2\right\rfloor\right) + T\left(\left\...
Nathaniel's user avatar
  • 15.4k
14 votes
Accepted

How to find a "short" walk that visits all vertices of a strongly connected directed graph

The answer is no. For any $n\geq 3$ consider an oriented cycle $C_n$ and let $u\to v$ be adjacent in the $C_n$. Create $n$ vertices $x_1...x_n$ and add edges $u\to x_i$ and $x_i \to v$. Now any walk ...
Michal Dvořák's user avatar
14 votes

Time Complexity of Linear Search vs Brute Force

Time complexity is expressed as a function of some parameter, which is usually the size of the input. The combination lock is not a perfect analogy as it is not immediately clear what the input would ...
Steven's user avatar
  • 29.4k
13 votes

Find 1s in almost all 0 array using comparisons only

Start by splitting the 100 elements in 50 pairs of two, and use a comparison on each pair. If a comparison returns -1 or 1, then you've found one of the elements which is 1 (and the other one must be ...
orlp's user avatar
  • 13.4k
12 votes

How AlphaDev improved sorting algorithms?

Check out Grady Booch's tweet on the matter: there is no "new sorting algorithm" here. Coming up with assembly level tricks is not the same as finding a new sorting algorithm. That would ...
ExpressionCoder's user avatar
9 votes
Accepted

Are there associative cryptographic / collision resistant hashes?

There is a plausible construction of such a hash. At design time, randomly choose two $2\times 2$ matrices with entries in $\mathbb{F}_{2^n}$ that have determinant 1, fix them, and call them $h(0),h(...
D.W.'s user avatar
  • 159k
9 votes

False proofs that look correct

This one is regarding $\mathsf{FPT}$ time algorithm. Suppose an algorithm has time complexity of: $O((\log n)^k \cdot n^{O(1)})$. Is it an $\mathsf{FPT}$ time algorithm in parameter $k$? Well ...
Inuyasha Yagami's user avatar
9 votes

False proofs that look correct

I have often seen among undergraduates that they believe that the heaps are constructed in $\Theta(n \log n)$ time. The standard algorithm for that is to insert an element to a heap one after another. ...
Inuyasha Yagami's user avatar
8 votes

Small doubt concerning cardinality of set of problems and algorithms?

The intuitive reasoning is "there are more problems than algorithms, so it cannot be the case that, for each problem, there exists an algorithm that solves it". More formally, this can be ...
mell_o_tron's user avatar
8 votes

False proofs that look correct

This one is classic. $0$-$1$ Knapsack problem is polynomial time problem since there is dynamic programming solution with running time $O(n W)$ time. However, it is incorrect. Note that the input size ...
Inuyasha Yagami's user avatar
7 votes

Time Complexity of Linear Search vs Brute Force

You are absolutely right that they are the same algorithm! At least, in this context. "Brute-force attack" is a general term referring to finding a solution to the problem at hand by trying ...
NaturalLogZ's user avatar
7 votes

Creating a deterministic finite automaton for strings of 2k ones and 3q zeros or a general language

One way to look at these specific problems is to have states labeled $(x,y)$ where $x$ will correspond to the ones seen so far and $y$ similarly to the zeros so far. These are taken mod 2 or mod 3 ...
Rick Decker's user avatar
  • 14.8k
6 votes

can we computably list every primitive recursive function?

The primitive recursive functions can be defined in terms of the following five axioms: Constant function: $C_n^k$ is a $k$-ary function that always returns $n$ Successor function: $S$ is a 1-ary ...
Pål GD's user avatar
  • 16.1k
6 votes
Accepted

Possible Mistake in Skiena's Algorithm Design Manual

You are totally right, though I think there is an easier proof: if $m = n$, then $mn-m^2 +m= m\notin \Omega(m^2)$. However, since the analysis is done when searching for a worst case, you could just ...
Nathaniel's user avatar
  • 15.4k
6 votes

Small doubt concerning cardinality of set of problems and algorithms?

Correct. There are only countably many algorithms (only countably many Turing machines). Yes, this proves that there exists at least one decision problem that cannot be decided by any algorithm (in ...
D.W.'s user avatar
  • 159k
6 votes
Accepted

Find the smallest subarray with sum larger than a threshold

You can solve your problem in linear time using a "sliding window" algorithm. Let $i,j$ be two pointers initialized to $1$, and denote by $\sigma(i,j)$ the sum $a_i + a_{i+1} + \dots + a_{j}$...
Steven's user avatar
  • 29.4k
6 votes
Accepted

What else measures are used to compare algorithm efficiency apart from Time and Space complexities?

When it comes to the numerical methods used in science and engineering, one important measure is numerical accuracy.
DirkT's user avatar
  • 991
6 votes
Accepted

How AlphaDev improved sorting algorithms?

The improvement in the figure consists of the removal of one instruction. In a branch-less assembly program, this usually leads to a performance improvement. How much of a practical improvement it ...
Discrete lizard's user avatar
  • 8,248
6 votes

False proofs that look correct

An simple example that I can think of, which is commonly use as introductory topic in amortized analysis, is the analysis of dynamic table. The usual scenario is to analyze the total time needed to ...
Russel's user avatar
  • 2,745
6 votes
Accepted

NP-completeness of problem based on non-arbitrary instance

A specific instance is never NP-hard. The concept of NP-hardness only applies to languages (classes of instances, if you will). If your reduction from $A$ to $B$ is $f$, then $f$ is a function from ...
Steven's user avatar
  • 29.4k
6 votes
Accepted

Linear-time algorithm for determining the presence of incomparable pairs in a directed acyclic graph (DAG)

Here is a linear-time algorithm that decides whether a DAG contains at least one incomparable pair of nodes. Do a topological sorting with a linear algorithm. (Yes, topological sorting is very ...
John L.'s user avatar
  • 39k
5 votes
Accepted

Given two sets of integers find an integer in the first set furthest away from all members of the second set

Since you now clarified your request, I give a new answer: Assume your sets are $A$ and $B$, with $|A|=n$ and $|B|=m$. Let $k=\max(n,m)$. This is the procedure: Join the two sets $X=A\cup B$ in $\...
SilvioM's user avatar
  • 843
5 votes
Accepted

Can we solve $\mathrm{MFVS} \leq 1$ in linear (or subquadratic) time?

A vertex $v$ such that $G-v$ is acyclic is called a feedback vertex, so your problem is equivalent to deciding whether there exists at least one feedback vertex in $G$. The paper "A linear-time ...
Steven's user avatar
  • 29.4k
5 votes
Accepted

Read-once complexity of a matrix problem

The computation of the erasing machine can be expressed as a read-once branching program. A branching program is a DAG with a unique source and two sinks, labelled "Yes" and "No". ...
Yuval Filmus's user avatar
5 votes
Accepted

Find Minimum Transformation Between Multisets of Lists of Cards

I think the variant with sets can be solved using bipartite matching. Build a complete bipartite graph, with one left vertex per set in s0 and one right vertex per set in s1. Also, if there are fewer ...
D.W.'s user avatar
  • 159k
5 votes
Accepted

Bounded clique width graphs vs parameter clique width

Not necessarily, being polynomial-time solvable for graphs with bounded clique-width means that on graphs of clique-width less than $k$ an algorithm solves the problem in $O(n^{f(k)})$ time for some ...
pasthec's user avatar
  • 291
5 votes

False proofs that look correct

Induction often yields great wrong proofs because there are many things which can fail: The induction base $P(0)$ can be false, or it may be missing at all and hence the rest of the induction is ...
rexkogitans's user avatar

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