Projects

Select one of the projects below, and please let me know your choice. You might propose a project different from the ones that are suggested here. In that case you should write a brief proposal, which I need to approve before you start working on it.

These are individual projects, however, it is possible for several of you to work on the same project as long as each one of you make an equal contribution. Team projects are expected to be of larger scope than individual ones. If some of you want to work as a team on a project, please talk with me first.

What you need to submit

Projects are due on December 8 during class. I need both a hard copy of your report and an electronic version. You can email me the electronic copy of your report. The project topics are grouped by type.


Implementations

Algorithm Animations

For these projects you have to implement animations for algorithms related to the topics covered in this course. Here are some examples of very simple animations using samba.

When designing an animation, the goal is to illustrate how an algorithm works and why it works. Furthermore, animations should be designed so that they can be used to try to improve existing algorithms. An animation should help us find worst-case inputs where an algorithm does not perform very well and the visualization of an algorithm should try to help us discover ways of improving it.

Your animation must be interactive and, as mentioned above, it should help us discover worst-case inputs for the algorithm. As an optional feature, you should design your animation to allow the user to modify the algorithm and run the animation for the modified algorithm. You can impose reasonable restrictions on the kind of modifications to an algorithm that the user can make.

Below are a few of examples of the algorithms that you can animate. You can propose different algorithms from the one's below; in this case, please let me know which algorithm you plan to animate before you start working on your project.

Maximum flow algorithms Gabriel Keenleyside
Select one of the following. Minimum cut and maximum matching  
Approximation algorithms
Randomized algorithms
As mentioned above, you can select algorithms for other problems, but please check with me first. Your mark will be affected by the complexity of your animation, how well it explains the working of an algorithm, and how useful it is to discover hard instances for the algorithm and to explore ways of improving it.

Experimental Evaluation of Algorithms

The experimental evaluation of an algorithm requires implementing it and running it on "typical" instances to determine its performance and to try to discover ways of improving it. For each one of these projects you must implement several algorithms and experimentally compare their performance (either running time or approximation ratio) over a carefully selected set of test inputs.

You must explain how the test cases where selected and/or generated. Argue that the results of theses tests are a good representation of the true performance of the algorithms that you have implemented. From the tests, try to discover ways of making the implementations faster/better. Report your findings. Also, show the instances for which your algorithm has the worst running time/approximation ratio, and explain why this is the case.

You might choose any of the problems that we have studied in class (max flow, min cut, maximum matching, vertex covering, bin packing, ...). Choose at least 2 algorithms for solving the problem that you have selected and implement them. Below are some specific suggestions.

Maximum flow Rifayat Samee, Kuldip Chakrabarty

Implement some of the following variants of the Ford-Fulkerson algorithm:
Compare the performance of these algorithms as described above.

Global Minimum Cut  Patrick Carnahan

In class we discussed the minimum cut problem separating a source vertex s from a sink vertex t. This problem is known as the $st minimum cut problem. In the global minimum cut problem (or just minimum cut problem) the goal is to find a cut of minimum cost that partitions the graph into two non-empty sub-graphs (note that no vertices s or t are specified in this case. For this project you will implement some algorithms for computing global minimum cuts: String matching  Winston Ka Hon Leung, Haoyu Gu, Christopher Steward, Daniel Deng, Touchaolong Zhang

In this project you must implement the randomized string matching algorithm described in Section 7.6 of the book Randomized algorithms by Motwani and Raghavan, and compare its performance with some deterministic string matching algorithms.

Among the string matching algorithms that you can use are: If you implement the randomized string matching algorithms in Java, you can use class BigInteger from package java.math. The following methods from this class might be useful: Bin Packing Qiang Zhou, Tarandeep Randhawa, Colin Costello, Ruoxi Shi, Tim Etchells

Implement some of the existing approximation algorithms for bin packing: first fit, next fit, best fit, worst fit, first fit decreasing, next fit decreasing, and the asymptotic polynomial time approximation scheme of de la Vega and Lueker. References:

Vertex Cover Amha Tsegaye, Tianzhi Zhu

Given a graph G = (V,E) in the vertex cover problem the goal is to select a smallest weight set S of vertices such that every edge of G is incident to at least one vertex in S. In this project you are to implement several approximation algorithms for the vertex cover problem. References: Algorithm Design

If you choose as your project one of the following problems, you must design an efficient algorithm for it, prove its correctness, and determine its performance ratio, and/or time complexity.

All-to-all communication problem with unit length messages. Robert Meagher

The all-to-all communication problem is: given a set of processors interconnected by a complete communication network (i.e. there is an edge between every pair of nodes) and a set of messages that each processor has to send, schedule the message transfers so that all messages can be exchanged in the smallest possible time.

For this project you will consider first the simpler instance of the problem when each processor has exactly one unit-length message that it must send to every other processor in the system. The following graph shows an example with 5 processors. The messages that need to be sent are indicated with arrows. Each arrow is one unit length message.

Assume that the model of communication is semi-duplex, that means that messages can flow in both directions along an edge, but at any given moment only one message can be transmitted through a particular edge. Also assume that a processor can only deal with one message at a time, i.e. at any moment a processor is either sending one message, receiving one message, or it is idle. A processor cannot send two messages at a time, receive two messages simultaneously, or send a message and receive a message at the same moment.

The all-to-all communication problem with unit length messages can be solved in time linear in the number of edges. Design a linear time algorithm for optimally solving the problem. Prove that the algorithm finds the optimal solution and analyze its time complexity. Indicate what is the length of the solution when the number of processors is even and when the number of processors is odd.

Then, consider the case when the number of messages that processors must exchange is not one, but an arbitrary number. This problem now becomes NP-hard. Propose an approximation algorithm for this problem and try to analyze it and compute its approximation ratio. You might only consider the simpler version when, for example, a processor cannot send more than 2 messages to another processor. If you cannot compute the approximation ratio of the algorithm just try to convincingly argue that it should compute a good solution.

Games SchedulingBrandon Glied-Goldstein

A set of teams will participate in a tournament, and it is desired to produce a schedule for the games. For this project you must design an algorithm that produces this schedule subject to to the following constraints. Other Problems

Consider this list of problems. You have two choices: Each algorithm must be given in pseudocode, you must compute its time complexity and you must prove its correctness. For each algorithm give a high level description explaining the main ideas and intuition behind its design. Your algorithms must run in polynomial time and you should try to design the algorithms so they have the lowest possible running time.

Survey papers

For each one of the following projects you are required to read a number of papers (at least 2-3 depending on how complicated they are) and write a report giving a critical analysis of these papers.

The references given below are just to get you started. I expect that you will look for relevant and recent research papers on the subject of your choice.

Techniques for proving inapproximability

We know that NP-hard problems are related in a very special manner, so that if a polynomial time solution for one of them exists, then polynomial time solutions for all NP problems exist as well. Not all NP-hard problems are equally difficult; some of them can be approximated in polynomial time better than others. For this project you will read papers describing techniques for proving that it is hard to approximate the optimum solution of a problem within a certain factor. The PCP TheoremNikita Sokolov

The PCP Theorem is one of the most important results in the filed of approximation algorithms as it has allowed researchers to prove that some problems are hard to approximate within a certain multiplicative factor from the optimum. For this project you will read papers about this seminal theorem and its implications for proving hardness of approximation. Local searchWon Ryul Lee, Rafe Beatty

Local search algorithms start with a given solution for an optimization problem and they repeatedly make local changes to the solution to try to improve it. Local search algorithms are usually intuitive an very simple, but it is difficult to prove that they produce solutions of value close to the optimum one. For this project you will read several papers detailing the design of approximation algorithms based on local search. Online financial problems Sangeet Parashar, Yu Wu, Tian Yi Li

Read some of the following papers, and related papers that you find, and describe online algorithms for interesting financial problems. We will discuss in class one of such problems involving selling stock. Multi-criteria optimization problems.

Optimization problems with more than two objective functions are called multi-criteria optimization problems. Most of these problems are NP-hard and different techniques have been proposed for designing approximation algorithms for them. Describe some of these problems and overview the techniques for dealing with them.

Parameterized AlgorithmsCarter Boon

Several NP-hard problems become polynomially solvable if some parameter of the problem is assumed to have a fixed value. There are several interesting techniques that have been proposed to design parameterized algorithms. The objective of this project is for you to describe some of these techniques and some parameterized algorithms.

Some additional information about this topic can be found in this site. Look at the section on "books and survey articles"

Maximum flow algorithms Alaa Darwech, Neeraja Dharan, Mostafa Shadi

We have studied a couple of algorithms for the maximum flow problem in class. There is no single best algorithm for this problem, but rather there are several algorithms that have incomparable time complexities. This project involves reading several of the papers described below (and/or others that you find), and giving a description of each one of the algorithms. An important part of the paper is a comparison of the time complexities of the algorithms, and an explanation of the conditions under which an algorithm is better than the others.

References

Minimum cut algorithms

This project involves reading several of the papers describing algorithms for computing minimum cuts and minimum s-t cuts, and writing a uniform description of them along with a comparison of their time complexities.

You might also consider algorithms for finding a minimum cut when all edge capacities are equal to 1 (the capacity of this minimum cut is called the edge-connectivity of the graph)

References

Maximum matching algorithms David Kolkarev

This project involves reading several papers about matchings, and describing in a unified way, some algorithms for finding maximum matchings. You might consider algorithms for general graphs, or you might restrict yourself to algorithms for special classes of graphs, like bipartite graphs and planar graphs.

References

Vertex/Edge coloring algorithms Angus Poole, Nima Khairdoost

For this project you must describe some approximation algorithms for optimization problems involving coloring the vertices or the edges of a graph.

References

Minimum cost flow

Assume that for every edge (i,j) in a flow network, the cost of pushing one unit of flow from i to j is c(i,j). The problem is to find a maximum flow of minimum total cost from a source vertex s to a sink vertex t. Describe the different approaches that have been proposed for solving this problem and make a comparison of them.

References

Applications for maximum flow, minimum cut, and maximum matching Jumayel Islam, Zaied Zaman, Suben Kumer Saha, Amir Memari

Describe some applications for these problems. I mentioned a few in class, for this project you have to find more. For each application describe how the problem is solved using max flows, minimum cuts, or maximum matchings.

References

Stochastic and Heuristic Algorithms Mahtab Ahmed, Joshua Jackson, Shrumit Mehta

For this project you will review several papers on heuristics that produce good solutions in practice, but are hard to analyze and prove a performance guarantee in the worst case. You can survey all heuristics mentioned below, or you can focus on only one of them. Parallel Models of Computation Dalal Shahrani

There is no single universally accepted model of parallel computers. For this project you will read papers describing various models used for parallel computations, you will discuss their advantages and disadvantages, and give examples of algorithms and their analyses in each model. Some of the models that you might study are the directed acyclic graph model, the shared memory model (PRAM and its variations), and the network model (ring, mesh, hypercube)

Techniques for the Design of Efficient Parallel Algorithms

In class we will study some basic techniques used for the design of efficient parallel algorithms like divide and conquer and jumper pointing. For this project you will learn other design techniques for parallel algorithms like partitioning, pipelining, Euler tour technique, accelerated cascading, and so on.

Randomized Parallel Algorithms

For this project you will read several papers describing randomized parallel algorithms, you will explain the problems sutudied, the algorithms proposed for solving them and how they were analyzed.

Sorting Parallel Algorithms Wenyang Liu

For this project you will read and describe various prallel algorithms that have been proposed for sorting a collection of items. Among the algorithm that you might study are quicksort, selection sort, insertion sort, couting sort, Batcher's bitonic sort, radix sort, and so on.