Analysis of Algorithm: NP- Complete Problems

Write a program in C/C++ or Jave for the following: The Independent-Set is to find a maximum-size independent set in G. a) Formulate a related decision problem for the independent-set problem, and prove that it is NP-complete. (Hint: Reduce from the clique problem.) b) Suppose that you are given a "black-box" subroutine to solve the decision problem you defind in part (a). Give an algorithm to find an independent set of maximum size. The running time of your algorithm should be polynominal in |V| and |E|, where queries to the black box are counted as a single step. Although the independent-set decision problem is NP-complete, certain special cases are polynominal-time solvable. c) Give an efficient algorithm to solve the independent-set problem when each vertex in G has degree 2. Analyze the running time, and prove that your algorithm works correctly. d) Give an efficient algorithm to solve the independent-set problem G is bipartite. Analyze the running time, and prove that your algorithm works correctly. 1) No approximation algorithms will be accepted. Only exact solutions required. 2) The program can be done in C or JAVA. 3) The program MUST have comments. 4) There should be a counter that counts how many loops the program goes through. 5) There should be more than five inputs and outputs. Two or three of these inputs should be small enough that a human can find the correct solution by looking at it. Two or three of the inputs should be BIG. A big input should make the machine work at least a half- hour. 6) You may use a random number generator to make your (big) inputs. 7) You may make your program read in input via a file rather than keyboard input. 8) The input should be varied so that the output should be varied. Some input should have no solution or hard to see solutions. 9) Be careful if you use recursion when making combinations or permutations. You might use more stacks than you have. The following must be handed in: a) The program inputs and outputs. b) How the program was implemented? c) What data structures were used? d) What computer was used to implement the algorithm? e) How many loops was the program supposed to makes? f) How many loops did the program, in fact, make? g) How long (time) did the big inputs take?

## Deliverables

1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done and a word file explaining the work.

2) Deliverables must be in ready-to-run condition, as follows? (depending on the nature? of the deliverables):

a)? For web sites or? other server-side deliverables intended to only ever exist in one place in the Buyer's environment--Deliverables must be installed by the Seller in ready-to-run condition in the Buyer's environment.

b) For all others including desktop software or software the buyer intends to distribute: A software? installation package that will install the software in ready-to-run condition on the platform(s) specified in this bid request.

3) All deliverables will be considered "work made for hire" under U.S. Copyright law. Buyer will receive exclusive and complete copyrights to all work purchased. (No GPL, GNU, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site per the coder's Seller Legal Agreement).

## Platform

Windows, Microsoft Visual C++ 6.0

Kemahiran: Pengaturcaraan C, Kejuruteraan, Java, MySQL, PHP, Kejuruteraan Perisian, Ujian Perisian

Lihat lagi: where to find java, when to use recursion, what's an algorithm, what's algorithm, what is the algorithm, what is recursion in programming, what is recursion, what is java programming used for, what is data structures in java, what is data structures in c, what is data structures and algorithms, what is data structures, what is computer programming used for, what is a programming algorithm, what is an algorithms, what is an algorithm in programming, what is an algorithm in computer programming, what is an algorithm, what is algorithms in programming, what is algorithm in programming

Tentang Majikan:
( 5 ulasan ) United States

ID Projek: #3269829

Dianugerahkan kepada:


See private message.

$42.5 USD dalam 3 hari
(8 Ulasan)

5 pekerja bebas membida secara purata $63 untuk pekerjaan ini


See private message.

$126.65 USD dalam 3 hari
(158 Ulasan)

See private message.

$49.3 USD dalam 3 hari
(32 Ulasan)

See private message.

$25.5 USD dalam 3 hari
(12 Ulasan)

See private message.

$72.25 USD dalam 3 hari
(13 Ulasan)