Final Project - NP-Hard Problems

Analzying an NP-Hard Problem

This project will explore an known NP-complete problem and will consist of the following components:

• Problem presentation explaining the problem to be solved and its reduction to another accepted NP-complete problem.
• Exact Solution Code – develop code that exactly solves the problem.
• Approximation presentation – show an approximation algorithm for this problem and analyze it.
• Approximation code – develop code that performs this approximation
• Evaluation of Other Projects – you will submit 1 review of other projects.

Below you will find each of these components described in more detail.

Problem and Group Selection

This is a group project with ideally 2 members (maximum 3 with permission of instructor). Your group will select an NP-complete problem to study from the list below:

• Max 3-Sat
• Max clique
• Traveling Salesman Problem (with a complete graph)
• Longest Path
• Vertex Cover
• Min Graph Coloring
• Max knapsack

Please note:

• all of the graph problem MUST accept input in the format used by the labs.

Submission and Grading

You should never start design or construction until you completely understand the project.

You should start by carefully reading the project specifications. (In general it is a good idea to print a paper copy so that you can take notes and perform calculations as you read.)

Implement all of the classes (in accordance with the specifications, perhaps informed by the Implementation Advice above) and submit them to gradescope .

You are not required to submit tests for these classes.

Grading

The code quality grade will be based on such things as:

• Comment clarity
• Code clarity (including variable names)
• Code duplication
• Elegance
• Acknowledgements (as appropriate)

You may submit to Gradescope an unlimited number of times.