The goals of this project are:
To design Divide & Conquer and Dynamic Programming algorithms for a given problem.
To prove the correctness of your algorithms and analyze them in terms of running time and
To implement and test them.
To document your findings in a project report.
You are organizing the perfect party and you are given a list
of people that can potentially attend the party. Each person
in the list is assigned a positive integer (between 1‐1000)
that rates how much this person can contribute to the
success of the party. However, the list is organized in such a
way such that if you select the i‐th person from the list to
attend the party then you cannot select any of its
neighbors because they do not mix well with each other.
So, given the list and the ratings of the people, you need to come up with two algorithms (a Divide &
Conquer algorithm and a Dynamic Programming one) that return the maximum sum achieved as well
as the people to attend the party, subject to the constraint mentioned above. For example if the list of
ratings is 7, 3, 5, 8, 2, 1, 2, 3, then the best sum is 19, achieved by the underlined people.
You should implement the two algorithms, test them for correctness using the test instances that can be
found in the class web page and evaluate their performance.
3. Project Implementation
You can work in teams of up to two. The teams are expected to accomplice the following goals.
Implement your algorithms in JAVA following the conventions below:
o Classname: Party
o Method signature: int partySum (int rating) (your method should be
o rating is a 1‐dimensional array of maximum size 10000 containing the rating of
o The ratings are integers in the range 1‐1000
o When your method is called, it should print the maximum sum attained as well as the
people that will attend the party.
o Example: partySum[7, 3, 5, 8, 2, 1, 2, 3]. Your method should print
Maximum sum: 19
The following persons should attend the party: 0, 3, 5, 7
Add comments to your code. At least 20% of your source code must be in the form of valid and
Your methods should compile with no mistakes. They will be tested on bigger and more
complex examples, so make sure your algorithms work correctly.
You need to submit a clearly written project report detailing all your work including all the steps
of the design process (problem formulation, D&C and DP algorithm descriptions, analysis of
running time and space requirements), screenshots of your program execution with specific
examples, and conclusions.
The report should be professionally written using a text processing software (e.g., MS Word or
other), and all figures, tables, etc. should also be generated preferably using some software tool.
6 pekerja bebas membida secara purata $93 untuk pekerjaan ini
Hi there. I am a talented developer. I have strong knowledge of algorithms. I am confident to provide you what you want on time. Kindly contact me. Regards. Evgeniia