CS860 (Spring 2007) - Adaptive, Output Sensitive, Online and Parameterized Algorithms

Ideas for Research Projects
The idea given here are preliminaries, most students should find their own project, potentially in relation with their own area of research.

Each project should result in a paper of at most 10 pages not counting the sections on Previous Work, Bibliography & Appendices. Grouped submissions are welcome, provided every author contributed to the work. A shorter paper with highly interesting results is totally acceptable and even recommanded. This "publication" does NOT count as a "publications in a refereed workshop or conference". The goal is to give to the students an idea of the publication process, to motivate them to write and present well, and to allow them to later submit to a peer-reviewed conference.

New Adaptive Sorting Algorithm

(Alejandro Salinger?) David Arthur described in "Fast Sorting and Pattern-avoiding Permutations" [ANALCO07] how to sort faster an array if it is known to avoid some patterns, i.e. if the number of occurences of the pattern in zero. On the other hand, the number of occurences of the pattern "(2,1)" is the number of inversions in the array, and it is a good difficulty measure for sorting (see Estivil-Castro's review). Combine those two approaches, and show that for pattenrs more complex than (2,1) the number of occurences of the pattern is a good difficulty measure for sorting.

Potentially, cooperate with David Arthur and Jeremy Barbay.

Adaptive Compression of Planar Graphs

(Raju?) Read the paper Canonical Triangulation of a Graph, with a Coding Application, from Luca Castelli Aleardi and Olivier Devillers, and represent their compression algorithm as an adaptive one, where this time the quality of their compression is studied in an adaptive way depending on a measure of difficulty (as opposed to the time complexity of the algorithm).

Potentially, cooperate with Luca Castelli and Jeremy Barbay.

Redundancy Analysis of path subset queries and Threshold set

Generalize the redundancy analysis of the intersection problem to path subset queries, to the threshold set problem of sorted arrays, and to the threshold set of path subset queries. Arash mentionned an interesting reduction between intersection and path subset queries, making it explicit is a good exercise already, and adapting the algorithm and analysis is not too difficult.

Adaptive Analysis of the "Small Adaptive" Intersection algorithm

Both the "Adaptive" and "Sequential" algorithms are optimal for their own difficulty measure, and are outperformed by the algorithm "Small Adaptive" in practice. There is no known adaptive analysis for which "Small Adaptive" is optimal. Find a difficulty measure to describe the instances on which "Small Adaptive" performs well, and express its complexity in function of it. Show that neither "Adaptive" nor "Sequential" are optimal for this measure.

Also, the two difficulty measures "gap encoding" and "redundancy" can be combined to form a new measure of difficulty, and a new adaptive analysis, the worst case among all instances of fixed size, gap encoding and redundancy, but no known algorithm is optimal for this new measure.

Adaptive Parallel Intersection

  1. There is a trivial lower bound of Omega(n1+n2+...+nk) comparisons required to compute the intersection of an instance of k sets of size (n1,...,nk) in the worst case with one processor: consider the instance where k=2 and the sets are (1,3,5,7,....) and (2,4,6,8,....), any algorithm has to perform n1+n2 comparisons to check the intersection.

    With p processors, this implies directly a lower bound of Omega((n1+n2+...+nk)/p). And the particular instance used for the worst case in the previous paragraph can be solved easily in O((n1+n2+...+nk)/p) comparisons by p processors. Is there an algorithm performing at most O((n1+n2+...+nk)/p) comparisons when given p processors, or is there a better lower bound?

  2. We saw quickly in class lower bounds on the number of comparisons needed to compute the intersection *with one processor* in the worst case over instances of signature (k,n1,...,nk) and various difficulty measure (such as the nb of comparisons required to check the validity of the answer).

    Some intersection instances are easier to solve in parallel than some others. For instance, the worst case instance of the previous question where k=2 and the sets are (1,3,5,7,....) and (2,4,6,8,....), is **easy** to solve p times faster with a parallel algorithm using p processors. Is there a difficulty measure d to measure this "easiness", so that one could prove upper and lower bounds on the complexity of any parallel algorithm using p processors, among instances of signature and difficulty fixed?

Potentially, cooperate with Mike Mc Cool and Jeremy Barbay.

Paralel Adaptive Sorting

We saw in class many difficulty measures and algorithms for sorting on one single processor. Sorting using several processors at once, or optimizing the use of the cache, is a well studied problem in the worst case for the size fixed, using quite different techniques: Can those approaches be combined to produce an adaptive parallel sorting algorithm? An adaptive cache-friendly sorting algorithm?

Potentially, cooperate with Mike Mc Cool and Jeremy Barbay.

Adaptive Topological Sweep

Read the paper "Topological Sweep in Degenerate Cases" by Eynat Rafalin, Diane Souvaine and Ileana Streinu [Alenex 2002]. (Eventually search for the other papers mentioned at Tuft) Generalize their algorithm to make it adaptive to some difficulty measure.

Adaptive Matrix Multiplication

Search the bibliography about matrix multiplication: many classes of matrices are known on which matrix multiplication is easier (sparse matrices, boolean matrices, triangular matrices). Is there a difficulty measure on matrices such that an adaptive algorithm can take advantage of it?