Title: Comparison of Exhaustive, Greedy, and Dynamic Programming approaches for the Partition problem. Description: In this assignment, we are given a set S containing n integers and we are expected to output a partition with two subsets such that they have the minimumdifference in their sums. For this purpose, we can use the simple exhaustive approach, which takes every subset A of S and compare the difference d of the sums: d =sum(A)-sum(S-A). The greedy approach is to use the numbers in S in pairs in descending order as described in class (you can also see the Wikipedia entry for thepartition problem). The dynamic programming algorithm that we covered in class is also to be implemented. We are also asked to compare the three algorithms in their runtime (in msecs) and difference found (d) for various values of k=log2(n). Your program will produce theseperformance measures, and then using any utility such as Excel, draw the plots of their runtimes versus k and d versus k (use k=1,2,…,10). Plot three separate curvesin the each one of the two figures. For each value of k, you will create t=50 trials (in each trial choose n integers randomly) and use the averages in theplots. In creating the random integers you will use different scenarios as there is an important ratio that affects the existence of solution(s). We will call this ratio r =m/n, where m is the number of bits needed to express the maximum number in the set. If r Please help me.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

Title: Comparison of Exhaustive, Greedy, and Dynamic Programming approaches for the Partition problem.
Description: In this assignment, we are given a set S containing n integers and we are expected to output a partition with two subsets such that they have the minimumdifference in their sums. For this purpose, we can use the simple exhaustive approach, which takes every subset A of S and compare the difference d of the sums: d =sum(A)-sum(S-A). The greedy approach is to use the numbers in S in pairs in descending order as described in class (you can also see the Wikipedia entry for thepartition problem). The dynamic programming algorithm that we covered in class is also to be implemented.
We are also asked to compare the three algorithms in their runtime (in msecs) and difference found (d) for various values of k=log2(n). Your program will produce theseperformance measures, and then using any utility such as Excel, draw the plots of their runtimes versus k and d versus k (use k=1,2,…,10). Plot three separate curvesin the each one of the two figures. For each value of k, you will create t=50 trials (in each trial choose n integers randomly) and use the averages in theplots.
In creating the random integers you will use different scenarios as there is an important ratio that affects the existence of solution(s). We will call this ratio r =m/n, where m is the number of bits needed to express the maximum number in the set. If r
Please help me.

Expert Solution

Step by step

Solved in 4 steps with 4 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions