CS 445a/544a: Analysis of Algorithms II

Projects

You are to pick a project in the following list, or come up with a personal one. In any case, you have to inform me of your choice by November 16th latest; if you want to work on a project not in the list, it will be subject to my approval. The projects are individual, but I have no objection to several of you picking the same project, as long as you work individually.

The projects I give here are oriented either towards implementation / experimentation or litterature review. In both cases, you are to submit a written report of about 10 to 15 pages (quality matters, not quantity).

• If you choose an implementation project, the report should not be made only of your code; you need to explain the design and give experimental results. The implementation should be made in a not-too-exotic language; you should send me your source code too, and it should compile. For some projects that may seem too short, I will ask you to come up with extra features such as algorithm animation using for instance samba. You may have to use multiprecision arithmetic, using libraries such as GMP (C, C++) or the class BigInteger (java).


• If you choose a litterature review project, you will read one or several papers or book chapters. You will have to explain their content in your own words. When the papers are long, I mostly want you to understand and extract the main ideas, and present them by yourself.

Flows and cuts

• Implement Ford/Fulkerson and Edmonds/Karp algorithms. Compare their performances on randomly generated graphs: arbitrary ones, as well as some specific families such as the ones for escape plans of assignment~1. Try to find heuristics to improve the performance.


• There are many more max flow algorithms than Ford/Fulkerson and Edmonds/Karp. This project consists in reviewing some of them, explaining them and their complexity. This could cover the following references, or others.
  • A. Goldberg and R. Tarjan, A new approach to the maximum flow problem Journal of the ACM (JACM), Volume 35 Issue 4, 1988.
  • V. King, S. Rao and R. Tarjan, A faster deterministic maximum flow algorithm. Journal of Algorithms, vol. 17, 1994, pp. 447-474.
  
  
• Cuts and image segmentation: implement a segmentation program using the graph cuts techniques. More details are in
  • Yuri Boykov, Gareth Funka-Lea, Graph cuts and efficient N-D image segmentation, International Journal of Computer Vision, vol. 70, no. 2, pp. 109-131, 2006.

Greedy algorithms

• The spanning tree algorithm relies on a disjoint set data structure. The so-called Union-find algorithm can be analyzed very precisely. This project consists in reading one of the following papers (and / or references therein) and reporting on the complexity results mentioned there.
  • R. Tarjan, Efficiency of a good but non-linear set union algorithm, Journal of the ACM (JACM), Volume 22 Issue 2, 1975.
  • R. Tarjan and J. van Leeuwen Worst-case analysis of set union algorithms, Journal of the ACM (JACM), Volume 31 Issue 2, 1984.

Linear programming

• Implement the simplex algorithm. Do it first for cases when the point (0,...,0) is a vertex, and experiment using two strategies (going in the most promising direction, or going to the best neighbor). Test on families of examples and report on the average running time. If time permits, animate the algorithm using samba.


• Chapter 29 of Introduction to algorithms gives a fully functional version of the simplex algorithm, including an initialization step. Explain and implement this step. Test on families of examples and report on the average running time. If time permits, animate the algorithm using samba.


• The most serious competitor to the simplex algorithm is Karmarkar's interior point method, which has a worst case polynomial running time, and is efficient in practice. This project consists in reading Karmarkar's original paper, and report on it.
  • N. Karmarkar, A new polynomial time algorithm for linear programming, Combinatorica Volume 4 Issue 4, 1984.
  I mostly want that you understand the main ideas in the algorithm, more than all technical details. You are welcome to consult other resources.

P and NP

• This project consists in implementing Cook's proof that SAT in NP-complete: basically, given a description of a Turing machine, you are to turn it into a boolean formula. This requires some, but not a lot of, familiarity with Turing machines; then, the steps of the proof are given for instance in Papadimitriou's book Computational complexity (I will provide copies).


• The Davis-Putnam algorithm is one of the most famous solutions to test the satisfiability of boolean formulas. For this project, you can either report on the original papers (which go beyond the family of formulas we saw)
  • M. David and H. Putnam, A computing procedure for quantification Theory, Journal of the ACM, Volume 7 Issue 3, 1960.
  • M. Davis; G. Logemann, and D. Loveland. A machine program for theorem proving. Communications of the ACM Volume 5 Issue 7, 1962.
  or implement and benchmark it, as in
  • H. Zhang and M. Stickel Implementing the Davis-Putnam method , Journal of Automated Reasoning, Volume 24 Issue 1/2, 2000.


• Boolean satisfiability problems exhibit interesting phase transition phenomenons: empirically, there is are threshold regions in the parameter space of the problem that seem to separate easy from hard instances. For this project, you can either read one of the first systematic reports
  • P. Cheeseman, B. Kanefsky and W. M. Taylor, Where the hard problems REALLY are, Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, 1991.
  or do some intensive experimentations as in
  • I. P. Gent and T. Walsh, The SAT phase transition, Proceedings of the Eleventh European Conference on Artificial Intelligence 1994.

Approximation algorithms

• The 3/2-approximation result seen in class is not the best possible one. This project consists in reading and explaining the original paper, where a better bound is given:
  • R. Graham, bounds for multiprocessing timing anomalies, SIAM J. Applied Mathematics, 17, 1969, pp. 263-269.