Deadlines:

The objective of the project is to explore the limits of tractability and to better understand the importance (or the irrelevance!) of asymptotic analysis. To that end each group will work on a different problem. For each problem there will be two or three algorithms with very different analytical guarantees. Your goal is to test these algorithms to see if the actual performance corresponds to the theoretical guarantee.

You are allowed to use library routines you may be familiar with. However, do acknowledge the use of any code that is not yours. If you are planning to use Python for your project, check out David Eppstein's PADS library.

Each group must have three members. If you do not submit your group by Monday 24 I will create the groups at random.

Vertex cover

In an undirected graph G=(V,E) a vertex cover C is a subset of the vertices such that every edge in E has at least one end point in C, that is, every edge is covered by C.

Because the problem of finding the smallest vertex cover is NP-hard, we concentrate on heuristics. You are study the performance of the following two algorithms: greedly pick a vertex covering the most uncovered edges until all edges are covered; find a maximal matching and return all the matched vertices. Somewhat surprisingly, the first algorithm can be off by a ln n factor from optimum while the second produces solutions with cost at most twice optimum.

Report: link.

Group Members: Christopher Baird, Rustin Rockstroh and Andrew Parrish.

Nim

In the game of Nim there are three piles of matches on a table. Two players take turns to remove any number of matches from a single pile. The player to remove the last match from the table wins.

In turns out that there are instances (number of matches in each pile) that no matter what the adversary plays there is always a winning strategy. On the other hand, in some instances no matter what we play a smart oponent always wins.

You are to study three different algorithms for determining if a given instance is winning or loosing for the game of Nim and other related games.

Report: link.

Group Members: Curtis Bolser, David Jones and John Cirujales.

Cut vertices/edges

Let G be a connected undirected graph. We say u in V is a cut vertex if its removal disconnects G into two or more pieces. Similarly (u,v) in E is a cut edge if its removal disconnects G.

Identifying cut vertices/edges is crucial in the realm of communication networks. A naive algorithm solves the problem in O(n(n+m)) time, while a more sophisticated algorithm does the job in O(n+m) time. There is a clear tradeoff between runtime and algorithmic complexity. The objective of this project is to explore this tradeoff and determine how big the graph has to be for the naive solution to become prohibitively slow.

Report: link.

Group Members: Derrick Hayford, Stephenson Ohimor and You Lu.

Union-find data structure

The union-find data structure maintains a collection of sets and supports two operations: find(x) returns the set x belongs to, and union(A,B) merges the sets A and B.

A commonly used option is to represent each set with a tree. In this project you are to study different attachment policies for the union operation and the effect of path compression in the find operation. Depending on the implemention chosen the performance a find operation can be O(n), O(log n) or O(log* n).

Report: link.

Group Members: Nikhil Purushe, Tiffany Gray and Henry Man.

Web Accessibility