[SOLVED] Cop4533 project 1 -algorithm abstraction & design

Algorithm Abstraction & Design
1 Problem Definition
Consider the problem of curating an art exhibition featuring n paintings that must be displayed in a specific sequence determined by the theme of the show; thus, their order cannot be changed. Each painting si, where 1 ≤ i ≤ n, has a base width wi and a height hi. The gallery space is divided into display platforms, each with a fixed maximum width W. The total width of the paintings placed on a single platform cannot exceed W. We have the flexibility to adjust the height of each platform to match the tallest painting placed upon it. The cost of a particular arrangement is the sum of the heights of the tallest paintings on each platform. Your goal is to determine an assignment of the paintings to platforms that minimizes the total cost.
Example 1: n = 7, W = 10,
hi = [21,19,17,16,11,5,1] wi = [7,1,2,3,5,8,1]
Solution 1: Platform1 = [s1…s3];
Platform2 = [s4…s5];
Platform3 = [s6…s7];
cost = 21 + 16 + 5 = 42
Example 2: n = 4, W = 10, hi = [8, 10, 9, 7] wi = [8, 1, 2, 2]
Solution 2: Platform1 = [s1];
Platform2 = [s2 …s4]; cost = 8 + 10 = 18
Example 3: n = 7, W = 10,
hi = [12, 10, 9, 7, 8, 10, 11] wi = [3, 2, 3, 4, 3, 2, 3]
Solution 3: Platform1 = [s1 …s3];
Platform2 = [s4];
Platform3 = [s5 …s7]; cost = 12 + 7 + 11 = 30
ProblemG Given the heights h1,…,hn and the base widths w1,…,wn of n paintings, along with the width W of the display platform, find an arrangement of the paintings on platforms that minimizes the total height.
ProblemS1 Given the heights h1,…,hn, where hi ≥ hj ∀i < j, and the base widths w1,…,wn of n paintings, along with the width W of the display platform, find an arrangement of the paintings on platforms that minimizes the total height.
(Note: The heights of the paintings form a monotonically non-increasing sequence, as in Example 1.)
ProblemS2 Given the heights h1,…,hn, where ∃k such that ∀i < j ≤ k, hi ≥ hj and ∀k ≤ i < j, hi ≤ hj, and the base widths w1,…,wn of n paintings, along with the width W of the display platform, find an arrangement of the paintings on platforms that minimizes the total height.
(Note: The heights of the paintings follow a unimodal function with a single local minimum, as in Example 3.)
2 MILESTONE 1 – Greedy Algorithms
For the first part of the project, you will design, analyze and implement greedy algorithms to solve the special cases of the problem. You will conduct an experimental study on the performance of your algorithms. You are also required to construct examples showing how an algorithm developed for a special case of the problem might not work for the general version of the problem.
2.1 Design, Analysis, and Implementation Tasks
Algorithm1 Design a Θ(n) time greedy algorithm for solving ProblemS1.
Analysis1 Prove the correctness of your greedy Algorithm1 for solving ProblemS1.
Question1 Give an input example showing that Algorithm1 does not always solve ProblemG.
Question2 Give an input example showing that Algorithm1 does not always solve ProblemS2.
Program1 Give an implementation of your greedy Algorithm1.
Algorithm2 Design a Θ(n) time greedy algorithm for solving ProblemS2.
Analysis2 Prove the correctness of your greedy Algorithm2 for solving ProblemS2.
Program2 Give an implementation of your greedy Algorithm2.
2.2 Experimental Comparative Study
Test your implementations extensively for correctness and performance. For this purpose, you should create randomly generated input files of various sizes. The exact size of the experimental data sets that your program can handle depends on the quality of your implementation. For instance, you might want to choose n = 1000,2000,3000,4000,5000 to create at least five data sets for each experiment. Then, you should conduct and present a performance comparison of the following: For each comparison, generate a two dimensional plot of running time (yaxis) against input size (x-axis). These should be included in your report along with additional comments/observations.
Plot1 Plot the running time of Program1 with respect to varying input size (as x-axis).
Plot2 Plot the running time of Program2 with respect to varying input size (as x-axis).
2.3 Report
Prepare a report that describes design and analysis of your algorithms, presents the results of experimental study, and summarizes your learning experience. Your report should include but not limited to the following sections.
• Algorithm Design and Analysis. Give a clear description of your algorithm design and as well as its analysis. You can also include the pseudo code of your algorithms. Make sure to provide the answers to Question1 and Question2 as well.
• Experimental Study. Present the results of your experimental study. Include all your plots along with any explanation and comments you wish to provide.
• Conclusion. Summarize your learning experience on the first component of the project assignment. For each programming task, comment on the ease of implementation and other potential technical challenges.
2.4 Deliverables
The following contents are required for Milestone1 submission:
• Implementation: Submit the implementation code on Gradescope. Refer to Section 5 for more details. Make sure to include detailed comments next to each non-trivial block of code.
• Report: The report, in PDF format, must be submitted on Canvas.
3 MILESTONE 2 – Dynamic Programming Algorithms
For the second part of the project, you will design, analyze and implement dynamic programming algorithms to solve the general cases of the problem. You will conduct an experimental study on the performance of your algorithms.
3.1 Design, Analysis, and Implementation Tasks
Algorithm3 Design a Θ(n2n−1) time naive algorithm for solving ProblemG.
Analysis3 Give an analysis (correctness & running time) of Algorithm3 for solving ProblemG.
Algorithm4 Design either a Θ(n3) time dynamic programming algorithm or a Θ(n2|W|) time dynamic programming algorithm for solving ProblemG.
Analysis4 Give an analysis (correctness & running time) of Algorithm4 for solving ProblemG.
Algorithm5 Design a Θ(n2) time dynamic programming algorithm for solving ProblemG.
Analysis5 Give an analysis (correctness & running time) of Algorithm5 for solving ProblemG.
Program3 Give an implementation of Algorithm3.
Program4 Give an implementation of Algorithm4.
Program5A Give a top-down recursive implementation of Algorithm5 using memoization.
Program5B Give an iterative bottom-up implementation of Algorithm5.
3.2 Experimental Comparative Study
Test your implementations extensively for correctness and performance. For this purpose, you should create randomly generated input files of various sizes. The exact size of the experimental data sets that your program can handle depends on the quality of your implementation. For instance, you might want to choose n = 1000,2000,3000,4000,5000 to create at least five data sets for each experiment. Then, you should conduct and present a performance comparison of the following: For each comparison, generate a two dimensional plot of running time (yaxis) against input size (x-axis). These should be included in your report along with additional comments/observations.
Plot3 Plot the running time of Program3 with respect to varying input size (as x-axis).
Plot4 Plot the running time of Program4 with respect to varying input size (as x-axis).
Plot5 Plot the running time of Program5A with respect to varying input size (as x-axis).
Plot6 Plot the running time of Program5B with respect to varying input size (as x-axis).
Plot7 Overlay Plots 3,4,5,6 and contrasting the performance of Programs 3,4,5A,5B.
Plot8 Overlay Plots 5,6 and contrasting the performance of Programs 5A, 5B.
In addition to testing the running time performance of the algorithms described above, you are asked to conduct experiments to test the quality of the output of Program1 which implements greedy Algorithm1, when it is run on the general case of the problem ProblemG. Note that such solution is not guaranteed to be optimal. Your task is to determine how different it is from the optimal. Make sure to conduct enough experiments with many random data sets. For x-axis, simply use n as the varying input size. On y-axis you can simply plot (hg − ho)/ho, where ho is the optimal height determined by any of Programs 3,4,5A,5B, and hg is the height determined by Program1.
Plot9 Plot the output quality comparison (hg − ho)/ho of Program1 and any of Programs 3,4,5A,5B.
3.3 Report
Prepare a report that describes design and analysis of your algorithms, presents the results of experimental study, and summarizes your learning experience. Your report should include but not limited to the following sections.
• Algorithm Design and Analysis. Give a clear description of your algorithm design and as well as its analysis. Make sure to include the recursive formulation expressing optimal substructure for the dynamic programming algorithms. You can also include the pseudo code of your algorithms.
• Experimental Study. Present the results of your experimental study. Include all your plots along with any explanation and comments you wish to provide.
• Conclusion. Summarize your learning experience on the first component of the project assignment. For each programming task, comment on the ease of implementation and other potential technical challenges.
3.4 Deliverables
The following contents are required for Milestone2 submission:
• Implementation: Submit the implementation code on Gradescope. Refer to Section 5 for more details. Make sure to include detailed comments next to each non-trivial block of code.
• Report: The report, in PDF format, must be submitted on Canvas.
4 MILESTONE 3 – Video Presentation
Prepare a video of length between 5 to 7 minutes, that presents all your results (design, analysis, experiments, and learning experience). Following are the expected components. Summarize your results on algorithm design and analysis. Note that you have already detailed these in your report. Given the time limit for the presentation, it is best to focus on the challenging components. For instance of all the design and analysis tasks, I recommend you spend more time presenting the following: Algorithm2, Analysis2, Algorithm4, Analysis4, Algorithm5, Analysis5. Also, contrast Algorithm4 and Algorithm5, given that both are dynamic programming algorithms solving the same problem but they have different time complexity. [recommended time: upto 2-4 minutes] Comment on your implementations (e.g., whether you used any other resources/libraries) and make a demo of your implementations clearly showing that they work. [recommended time: 2-3 minutes] Summarize your experimental study results, using your plots. [recommended time: 1 minute] In conclusion briefly comment on your learning experience. For group projects, all members must take part in the video presentation.
5 Language/Input/Output Specifications
The autograder on Gradescope runs on an Ubuntu 22.04 image. C++ code will be compiled using g++ 11.4.0 with the ‘-std=gnu++17‘ compile flag. Java code will be compiled and evaluated using OpenJDK 17. Python code will be evaluated using Python 3.10.
For convenience, you can assume that 1 ≤ n,W < 105, and ∀i 1 ≤ h[i],w[i] < 105. Test cases will be generated to accommodate the required time complexity.
Input. Your program will read input from standard input (stdin) in the following order:
• Line 1 consists of two integers n and W separated by a single space.
• Line 2 consists of n integers (height of n paintings) separated by a single space.
• Line 3 consists of n integers (base width of n paintings) separated by a single space.
Output. Your program should print to standard output (stdout) in the following order: • Line 1 contains the number of platforms used (denoted as m)
• Line 2 contains the optimal total height.
• The next m lines should consist of the number of paintings on each platform.
6 Grading Policy
For Milestones 1 and 2, grades will be based on the correctness & efficiency of algorithms and the quality of your experimental study and report:
• Program 60%. Correct/efficient design and implementation/execution. Also make sure to include comments with your code for clarity.
• Report 40%. Quality (clarity, details) of the write up on your design, analysis, programming experience, and experimental study.