Reference no: EM133121866

COT 5405 Design and Analysis of Algorithms - University of Central Florida

Project Description

Description

Implement the following algorithms discussed in class:

Greedy algorithm to find maximum-weight-independent set in a graphic matroid
• Reduction of general Steiner tree problem to metric Steiner tree
• The 2-approximation for metric Steiner tree.
• The 2-approximation for the metric Traveling Salesman problem.

The 3/2-approximation (Christofides) for the metric Traveling Salesman problem.

Implementations and Input/Output

All implementations may be done in the language of your choice; but they must run on linprog.cs.fsu.edu. All algorithms should be able to be run standalone, and should input a weighted, undirected graph in edge list format. That is, the first line contains the number of nodes, and every line thereafter is of the form:

u v w

where (u, v) ∈ E and w ∈ [0, 1] is the weight of (u, v). Each algorithm should output its solution to the terminal. If the output is a graph, it should be in edge list format.

Documentation

A README should be included that describes exactly the steps to compile and/or execute your code with an input file.

Assessment

Your project submission will be scored as follows.

• Your code compiles and correctly runs on a set of test instances.
• Your documentation is clear and complete.

You must submit your own code. This is a group project; collaborations between groups are not allowed.

Attachment:- Design and Analysis of Algorithms.rar