代写159.271留学生、代做Python程序语言、代写Greedy Heuristics、代写Python

日期：2019-05-26 11:24

Computational Thinking 14/05/19, 6*55 PM

file:///Users/cmmccart/Documents/Teaching/159271/Notes/assignment3_2019.html Page 1 of 2

159.271 Computational Thinking

Assignment 3

Greedy Heuristics for Independent Set

This assignment is worth 10% of your final mark. It will be marked out of a total of 20

marks. The due date for this assignment is Friday May 31st. You are expected to work on

this assignment individually and all work that you hand in is expected to be your own work.

In this assignment your task is to test greedy heuristics for the NP-complete problem

Maximum Independent Set. Recall that a maximum independent set for a graph is a subset

of the vertices in the graph, of maximum size possible, where no two vertices in the subset

are adjacent to one another. Two vertices are adjacent if there is an edge connecting one to

the other.

You have seen this problem already in Tutorial 5, where two different algorithms were

presented. Each of these takes a graph as input (in the form of a list of vertices and a list of

edges) and returns the size of a maximum independent set for the graph. Both of these

algorithms essentially use a brute-force approach (with some minor improvements to allow

us to avoid considering every subset of vertices.) As you will have seen, both of these

algorithms run in time exponential in n, where n is the number of vertices.

Your task is to implement two different greedy heuristics for the Maximum Independent Set

problem, and to compare the results they produce against a brute-force approach, using a set

of small benchmark graphs. A simple example of a (polynomial-time) greedy heuristic for

this problem: Start with an empty independent set. At each step, pick a vertex with lowest

degree and add it to the independent set. Remove this vertex v and all of its neighbours

from the graph (along with all of the edges involving v and its neighbours.) Stop when there

are no more vertices left. This heuristic will return an independent set, but not necessarily a

maximum-sized independent set.

Proceed as follows:

1. Implement a version of one of the algorithms presented in Tutorial 5, altered so that it

returns the independent set itself, along with the size of that set.

2. Implement your two greedy algorithms so that each returns the independent set that it

finds, along with the size of that set.

3. Run your three algorithms on the test graphs supplied on Stream (and any others that

you choose) and report a comparison of the results obtained.

Computational Thinking 14/05/19, 6*55 PM

file:///Users/cmmccart/Documents/Teaching/159271/Notes/assignment3_2019.html Page 2 of 2

Your implementations will need to handle the test graph files as input. The test graph files

are text files with the following format:

n # number of vertices in the graph, vertices are named as n # number of vertices in the graph, vertices are named as

numbers numbers 1 to n)

m # number of edges in the graph m # number of edges in the graph

# blank line, followed by m rows, each containing a pair of # blank line, followed by m rows, each containing a pair of

digits representing the edges of G digits representing the edges of G

For each of your algorithms, consider carefully what sort of data structures should be used to

store the input graphs, in order to allow for efficient implementation of your strategy.

Marking scheme

1. 5 marks for a correct brute-force program, returning a maximum independent set, along

with the size of that set.

2. 5 marks each, for each of your implemented greedy heuristics, returning an

independent set, along with the size of that set.

3. 5 marks for a report, sensibly comparing the results of your three algorithms, on the

test graphs supplied on Stream (and any others that you might decide to utilise.)

Submission

Submit your project in Stream as a single zipped file containing your completed code, as

three separate .py files, and the results report that you produce in a separate text file.