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
 A written report
explaining your work. You will decide on the length of the report; I understand that
some of you like to give longer explanations and some of you like to write more concisely.
Due to the amount of work involved in each project, I can imagine that your report should be
at least 10 pages long. Your mark will be based
on the quality of your report, not on its length. Some information about the organization
of your report
can be found here.
 If your project involves an implementation, then you must also send me by email a
copy of your program and instructions on how to run it, so I can test it. You might
choose any programming language, as long
as I can compile and run your program on the Department's computers.
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 worstcase 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 worstcase 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
Select one of the following.
 The relabeltofront algorithm described in Introduction to Algorithms
by Cormen, Leiserson , Rivest, and Stein.
 At least 3 variants of the Ford and Fulkerson algorithm where the augmenting path
selected in each iteration is selected in a different
manner. For example the algorithm can select a shortest augmenting path, an augmenting
path with largest residual capacity, a shortest augmenting path formed by edges of
capacity at least C/2, where C is the largest residual capacity of the current residual
network, and so on. Your choice of augmenting paths must be sensible, though.
Alexander Gyori
 Algorithms for computing minimum cost flows. We did not study minimum cost flows in
class; to learn about them you can read the following references:
 Network flows by Ahua, Magnati and Orlin, Sections 9.6 and 9.7.
 Algorithm design by Goodrich and Tamassia, Section 8.4.
 There are many lecture notes available on the Internet describing algorithms for
minimum cost flows.
Minimum cut and maximum matching
Approximation algorithms
 Polynomial time approximation scheme for the multiprocessor scheduling problem.
 Algorithms for the bin packing problem. Select one of the following two options.
 Next fit, first fit, best fit, and worst fit.
 Polynomial time approximation scheme for the bin packing problem.
To learn more about algorithms for the bin packing problem, please read the following
references:
 Approximation algorithms for NP_hard problems edited by D.S. Hochbaum. Chapter 2.
 Lecture notes on approximation algorithms by D.P. Williamson, Lecture 4.
 There are many lecture notes available on the Internet describing algorithms for the
bin packing problem.
 Approximation algorithms for the rectangle packing problem. Given a set R of
rectangles and a rectangular
bin, the goal is to pack the largest number of rectangles in the bin. There are several
variations of the problem that you can consider, like the square packing problem (where all
rectangles in R are squares), the strip packing problem, and the twodimensional bin
packing problem.
A nice survey of algorithms for 2 dimensional packing problems can be found
here. You can also
consider an algorithm that tries all possible ways of packing the rectangles in the bin.
Randomized algorithms
 String matching. Reference: Randomized algorithms by Motwani and Raghavan,
Section 7.4.
 The randomized algorithms discussed in class.
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
Implement some of the following variants of the FordFulkerson algorithm:
 Choose an arbitrary augmenting path in each iteration
 Choose a fattest augmenting path in each iteration: the path with largest residual
capacity.
 Choose in each iteration an augmenting path in which the sum of the
capacities of its edges is minimum.
 Choose in each iteration an augmenting path with residual capacity at least
k, for some given value k > 0. If such a path does not exist, then
choose a shortest augmenting path.
 Choose in each iteration an augmenting path that saturates at least 2 edges.
If such a path does not exist, then choose an augmenting path that uses the
largest capacity edge incident on the source.
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 nonempty subgraphs (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:
 Compute n1 maximum flows using always a fixed vertex $s$ as the source,
and a different vertex as sink. For each maximum flow compute the residual network and
a minimum cut. Select the cut with the lowest capacity among the n1 cuts found.
 Minimum cut algorithm of Stoer and Wagner.

Randomized minimum cut algorithm of Karger.
String matching Winston Ka Hon Leung, Haoyu Gu
In this project you must implement the randomized string matching algorithm described in
Section 7.4 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:
 the naive algorithm, that tries to match the pattern to every position of the
text,
 the BoyerMoore algorithm (you can read about this algorithm in this
page),
 the RabinKarp, or the KnuthMorrisPratt algorithms described in the
book Introduction to Algorithms by T. Cormen, C. Leiserson, and R. Rivest,
 the string matching algorithm used by the Java libraries (method indexOf
from class String).
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:
 BigInteger(int,int,Random), returns a randomly selected number with the specified length that is probably prime.
 IsProbablyPrime(int), returns true if the input value is probably prime, and
false if the number is not prime.
Bin Packing Qiang Zhou
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:
 Approximation algorithms for NP_hard problems edited by D.S. Hochbaum. Chapter 2.
 Lecture notes on approximation algorithms by D.P. Williamson, Lecture 4.
 There are many lecture notes available on the Internet describing algorithms for the
bin packing problem.
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.
Alltoall communication problem with unit length messages.
The alltoall 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 unitlength 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 semiduplex, 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 alltoall 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 NPhard. 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 Scheduling
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.
 Every team will play k games, where k is an input parameter.
If there are n teams, then k can be no larger than n1.
 Every team plays at least p games at home, and at most q
games at home, for two given values p and q.
 A team should not play more than r games away from home in a row,
for some given value r.
Other Problems
Consider this list of problems. You have two choices:
 design
algorithms for problems 13, or
 design an algorithm for problem 4.
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 23 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 NPhard 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 NPhard 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
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.
 Local search heuristics
for kmedian and facility location problems,
V. Aryam A. Meyerson, V. Pandit, N. Garg, K. Munagala.
 Simpler analyses of local search algorithms for facility location,
A. Gupta and L. Tangwongsan.
 A local search approximation algorithm for kmeans clustering,
T. Kanungo, D. Mount, N. Netanyahu, C. Piatko, W. Silverman, A. Wu.
Online financial problems Sangeet Parashar, Yu Wu
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.
 Competitive solutions for online financial problems, R. ElYaniv,
ACM Computing Surveys, 30(1), 1998, 2869.
 On the competitive theory and practice of online portfolio selection,
A. Borodin, R. ElYaniv, V. Gogan. You can download this paper
from here.
This paper appeared
at the Proceedings of Latin 2000.
 Online portfolio selection using multiplicative updates, D. Helmbold,
R. Schapire, Y. Singer, and M. Warmuth, Mathematical Finance, 8(4),
1998, 325347.
 Universal portfolios with and without transaction costs, A. Blum and A. Kalai,
Machine Learning, 35, 1999, 193205. You can download the
paper here.
 Universal portfolios with side information, T. Cover and E. Ordentlich,
IEEE Transactions on Information Theory, March 1996. This paper is in
the library.
 Online Computation and Competitive Analysis by Borodin and ElYaniv, Chapter 14.
Multicriteria optimization problems.
Optimization problems with
more than two objective functions are called multicriteria optimization
problems. Most of these problems are NPhard 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.
 Bicriteria network design problems, M. Marathe, R. Ravi, R. Sundaram, S.S.
Ravi, D. Rosenkrantz, H. Hunt III, Journal of Algorithms, 28 (1), 1998,
142171. This paper is in the library.
 Bicriteria compact location problems, S. Krumke, H. Noltemeier, S. Ravi, and
M. Marathe, Studies in Location Analysis, 10, 1996, 3751.
 Complexity and Approximability of Some Bicriteria Location Problems,
S.O. Krumke, H. Noltemeier, S.S. Ravi and M.V. Marathe, Proceedings of the 21st International Workshop on GraphTheoretic Concepts in Computer Science (WG'95),
volume 1017 of Lecture Notes in Computer Science, pages 7387. Springer, 1995.
 Multicriteria approximation through decomposition, C. Burch, S. Krumke, M.
Marathe, C. Phillips, and E. Sundberg. You can download the paper
here.
 On multicriteria online problems, M. Flammini and G. Nicosia,
Proceedings of the 8th Annual European Symposium on Algorithms, 2000,
191201. This paper is in the library (call number QA76.9.A43E83 2000).
Parameterized AlgorithmsCarter Boon
Several NPhard 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
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
 A. Goldberg and S. Rao, Beyond the flow decomposition barrier,
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997,
pp. 211.
 A. Goldberg a,d R. Tarjan, A new approach to the maximum flow problem
JACM, Vol. 35, 1988, pp. 921940.
 V. King, S. Rao, and R. Tarjan, A faster deterministic maximum flow
algorithm Journal of Algorithms, vol. 17, 1994, pp. 447474.
 J. Cheriyan, T. Hagerup, and K. Mehlhorn, An o(n^3)time
maximum flow algorithm, SIAM Journal on Computing, vol. 25, 1996, pp. 11441170.
 R. Ahuja, J. Orlin, and R. Tarjan, Improved time bounds for the maximum
flow problem, SIAM Journal on Computing, vol. 18, 1989, pp. 939954.
 S. Phillips and J. Westbrook, Online load balancing and network flow,
Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1
993, pp. 402411.
 D. Karger, Better random sampling algorithms for flows in undirected
graphs, Proceedings of the 9th Annual ACMSIAM Symposium on Discrete
Algorithms, 1998.
Minimum cut algorithms
This project involves reading several of the papers describing algorithms for
computing minimum cuts and minimum st 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
edgeconnectivity of the graph)
References
 M. Stoer and F. Wagner,A simple mincut algorithm, Journal of
the ACM, 44 (4), 1997, pp. 585591
 D. Karger and C. Stein, A new approach to the minimum cut problem,
Journal of the ACM, 43(4), 1996, pp. 601640.
 J. Hao and J Orlin, A faster algorithm for finding the minimum cut in
a graph, Proceedings of the 3rd Annual Symposium on Discrete Algorithms (SODA'92),
pp. 165174.
 M. Padberg and G. Rinaldi, An efficient algorithm for the minimum capacity
city cut problem, Mathematical Programming, 47, 1990, pp. 1936.
Maximum matching algorithms
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
 R. Tarjan, Data structures and network algorithms, SIAM, 1983.
 J. Hopcroft and R. Karp, An n^(5/2) algorithm for maximum matchings
in bipartite graphs, SIAM Journal on Computing, 2(4), 1973, pp. 225
231.
 H. Alt, N. Blum, K. Mehlhorn, and M. Paul, Computing a maximum cardinality
matching in a bipartite graph in time O(n^1.5 sqrt{m/
log n}, Information Processing Letters, 37 (4), 1991, pp. 237240
.
Vertex/Edge coloring algorithms
For this project you must describe some approximation algorithms for optimization
problems involving coloring the
vertices or the edges of a graph.
References

Halldórsson, M. M. (1993a),
A still better performance guarantee for approximate graph coloring,
Inform. Process. Lett. 45, 1923.
 A. Wigderson, Improving the performance guarantee for approximate
graph coloring, Journal of the ACM, 30 (1983), 729735.
 D. Karger, R. Motwani, and M. Sudan,
Approximate graph coloring by
semidefinite programming, FOCS 1994.
 M. Blum, Extremely greedy coloring algorithms in "Graphs and
Applications" (Ed. Harary and Maybee), Wiley, 1985, 257270.
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
 J. Edmonds and R. Karp, Theoretical improvements in algorithmic
efficiency
for network flow problems Journal of the ACM, 19 (1972), 248264.
 A. Goldberg and R. Tarjan, Solving minimum cost flow problem by successive
approximation, Mathematics of Operations Research, 15 (1990), 430466.
 A. Goldberg and R. Tarjan, Finding minimum cost circulations by cancelling
negative cycles, Journal of the ACM, 36 (1989), 873886.
 R. Ahuja, T., Magnati, and J. Orlin, Network Flows, Prentice Hall,
New Jersey, 1993.
Applications for maximum flow, minimum cut, and maximum matching
Jumayel Islam
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
 M. Hall, An algorithm for distinct representatives, American Mathematical
Monthly, 63 (1956), 716717.
 M. Bacharach, Matrix rounding problems, Management Science, 9
(1966), 732742.
 A. Federgruen and H. Groenevelt, Preemptive scheduling of uniform machines
by ordinary network flow techniques, Management Science, 32 (1986),
341349.
 R. van Slyke and H. Frank, Network reliability analysis: Part I
Networks, 1 (1972), 279290.
 D. Gusfield, A graph theoretic approach to statistical data security
, SIAM Journal on Computing, 17 (1988), 552571.
Stochastic and Heuristic Algorithms
Mahtab Ahmed
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.
 Hill climbing
 Principles of artificial intelligence, N. Nilson. Taylor Library, call
number Q335.N515.
 Artificial intelligence: a modern approach, S. Russel and P. Norvig.
Taylor library, call number Q335.R86 2003.
 Probabilistic hill climbing, Cohen, Greiner, and Schuurmans.
 Simulated annealing
 Tabu search
 Evolutionary algorithms
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
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.