Algorithmic Challenges

I will add new problems into this list as we go. All these problems are extremely difficult if they have a solution at all. But if you solve or improve any of these, you get an automatic 100 for this course.

Problem #1

Give an O(n log n) algorithm for multiplying 2 n-bit numbers. (People think such an algorithm should exist, and in 2007 Martin Furer gave an O(nlogn 2^(log*n) time algorithm, where log*n is number of times you take logarithm on n until it becomes 0 or negative.)

Problem #2

Assume we have k stacks (last-in fist-out devices) lined up as S1,S2, ... , Sk. A permuation of n numbers come one by one in the online fashion (once a number passes by, we do not see it or remember it any more). Each number x sequentially goes through stacks S1 to Sk in the following fashion. At each stack Si, you can first pop some elements out from Si and send them, in the order they are popped out, to the next stack S(i+1) (or output if it is popped from the last stack Sk), then you push x into Si. It is known (a) log n stacks are sufficient to sort n numbers (i.e. when they come out of the last stack, they should be in sorted order). (b) A lower bound of (1/2)logn stacks are known to be necessary. Can you close this gap? Note: Luke Schaffer has improved the lower bound to 0.53logn. Thus you need to do better.

Problem #2

Can you close the gap for finding the median? (See lecture notes 13). The best upper bound is about 2.95n and best lower bound is 2n+o(1) (Dor-Zwick, FOCS96).

Problem #3

Can you show Greedy has approximation ratio 2 for the Shortest common superstring problem? (Or construct a counterexample for more than 2.) See lecture notes 24.