Implement the greedy algorithm

Assignment Help Data Structure & Algorithms

Reference no: EM133121886

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

Reference no: EM133121886

Questions Cloud

What would be the net present value of a microwave oven : What would be the net present value of a microwave oven that costs $188 and will save you $78 a year in time and food away from home

What are multivariate models : What are multivariate models? Explain with the help of an regression equation the difference between univariate and multi-variate regression model.

Prepare an estimated cash budget : Prepare an estimated cash budget for 3 months from January to March and show the surplus and deficit. The cash balance as on lst January is Rs 30,000.

How much will you make on each bond : How much will you make on each bond if you buy? it, hold it for one? year, and then sell it assuming that the? dollar/euro exchange rate falls

Implement the greedy algorithm : Implement the Greedy algorithm to find maximum-weight-independent set in a graphic matroid - A README should be included that describes exactly the steps

What is considered the minimum interest coverage ratio : What is considered the minimum interest coverage ratio (based on EBIT) that analysts prefer to see?

Calculate the break-even point in units : Sugarman Manufacturing had the following information for the month of June: Units sold: 2,400 units. Calculate the break-even point in units

Why are arbitrage opportunities available : 1) Explain why costs to holding an asset increase its futures price and benefits to holding it decrease its futures price. Use words and not formulas.

What is the rate of return on investment : Dée Trader opens a brokerage account and purchases 300 shares of Internet Dreams at $40 per share. She borrows $4,000 from her broker to help pay for the purcha

User Account

All Pages