#algorithms

P is the class of decision problems that can be solved in polynomial time, and NP is the class of decision problems whose yes answers can be checked in polynomial time given a suitable certificate. Is P equal to NP? Equivalently, does some NP-complete problem, such as Boolean satisfiability, have a…

Let $\omega$ be the infimum of all real $c$ such that two $n\times n$ matrices can be multiplied using $\mathcal{O}(n^c)$ arithmetic operations. The schoolbook method shows $\omega \le 3$, and $\omega \ge 2$ because the output has $n^2$ entries. Is $\omega =2$?

Given an integer $N$ with $b$ bits, find its prime factorization. Is there a classical (non-quantum) algorithm that does this in time polynomial in $b$?

Given $n$ integers, decide whether some three of them sum to zero. A simple algorithm takes $\mathcal{O}(n^2)$ time. Is there an algorithm that runs in time $\mathcal{O}(n^{2-\epsilon })$ for some fixed $\epsilon >0$?

For a sequence $S$ of accesses to keys in a binary search tree with $n$ keys, let $\mathrm{OPT}(S)$ be the minimum total cost of serving $S$ by any binary search tree algorithm that may rotate the tree, even one that knows $S$ in advance. Prove or disprove that splay trees serve every access…

A sorting network on $n$ wires is a fixed sequence of comparators, each of which swaps the values on two wires if they are out of order, such that every possible input comes out sorted. What is the minimum number of comparators in a sorting network for $n=13$ inputs?

Given a real $m\times n$ matrix $A$ and a vector $b\in {\mathbb{R}}^m$, decide whether there is $x\in {\mathbb{R}}^n$ with $Ax\ge b$. Is there an algorithm whose number of arithmetic operations is bounded by a polynomial in $m$ and $n$ alone, independent of the size of the numbers in $A$ and $b$?

Give a deterministic algorithm that decides whether an integer $n$ is prime in time polynomial in the number of digits of $n$, without relying on any unproved conjecture.

There are $n$ men and $n$ women, and each person ranks all members of the other group. A perfect matching is unstable if some man and woman both prefer each other to their assigned partners. Prove that a stable matching always exists, and give an algorithm that finds one in $\mathcal{O}(n^2)$ time.

You have 2 identical eggs and a building with 100 floors. There is an unknown threshold floor such that an egg breaks when dropped from that floor or above and survives from any floor below, and an egg that survives can be reused. What is the smallest number of drops that guarantees finding the…

A stream of $n$ items is read once, from left to right. Using only a constant number of memory words, find an item that occurs more than $n/2$ times, assuming such an item exists. Then explain how a second pass can check whether a majority exists at all.

A singly linked list either ends in a null pointer or eventually loops back into itself. Using $\mathcal{O}(1)$ extra memory and time linear in the number of nodes, decide whether it has a cycle, and if it does, find the first node on the cycle and the cycle length.

Given an array of $n$ integers, some possibly negative, find a contiguous subarray with the largest sum. For example, in $[-2,1,-3,4,-1,2,1,-5,4]$ the best subarray is $[4,-1,2,1]$ with sum 6. Give an $\mathcal{O}(n)$ algorithm and prove it correct.

A closed knight's tour on an $m\times n$ board is a sequence of knight moves that visits every square exactly once and ends a knight's move away from the starting square. For which $m\le n$ does a closed tour exist? As a first step, prove that none exists when $m$ and $n$ are both odd.

$n$ disks of different sizes are stacked on one of three pegs, largest at the bottom. A move takes the top disk from one peg and places it on another peg, never on top of a smaller disk. What is the minimum number of moves needed to transfer the whole stack to another peg? Prove your answer.