主观题：Texture Packing
Texture Packing is to pack multiple rectangle shaped textures into one large texture. The resulting texture must have a given width and a minimum height.
This project requires you to design an approximation algorithm that runs in polynomial time. You must generate test cases of different sizes (from 10 to 10,000) with different distributions of widths and heights. A thorough analysis on **all the factors** that might affect the approximation ratio of your proposed algorithm is expected.
### Grading Policy:
**Programming:** Implement the approximation algorithm (6 pts.). Write a test of performance program (1 pts.). **All the codes must be sufficiently commented.**
**Testing:** Generate the test cases and give the run time table (2 pts.). Plot the run times vs. input sizes for illustration (2 pts.). Write analysis and comments (5 pts.). The analysis must be based on your testing results.
**Documentation:** Chapter 1 (1 pt.), Chapter 2 (2 pts.), and finally a complete report (1 point for overall style of documentation).
**Bonus: Compare your algorithm to any of the known strip algorithms.**
**Note:** Anyone who does excellent job on answering the Bonus question will gain an extra point.
答案：Rubric items: 6
Item 1: 1 point
The cover page must be presented with the title and the date of completion (+ 0.2 pts.). A complete problem description must be given in Chapter 1 (+0.8 pts.). Deduct points if:
- the cover page is not complete (-0.2)
- the introduction is a simple copy + paste of the assignment statement (-0.3)
- the introduction is not very clear -- in this chapter they are supposed to make it clear WHAT is to be done, besides why they are doing it (-0.1 ~ 0.5)
- others – please specify in the final comments.
Item 2: 2 points
Chapter 2 is supposed to specify the approximation algorithm (+1 pt.), together with its time bound and approximation ratio (+1 pt.). Deduct (at most 2) points if:
- the description is way too simple (-1)
- the algorithm specification is not complete – the approximation algorithm description is missing (-1)
- the algorithm specification is not complete – the time bound and approximation ratio description is missing (-1)
- not making their algorithm easier to understand than a simple program (-1)
- only a program + comments, which is not acceptable (-1)
- others – please specify in the final comments.
Item 3: 1 point
The overall style of documentation is supposed to be neat and clear. Deduct (at most 1) point if:
- the document looks like a patch work (-1)
- messy – some of the data in the charts and tables are missing (-1)
- the hand-in is not zipped with proper folders (-1)
- the hand-in is not complete – some files are missing (-1)
- others – please specify in the final comments.
Item 4: 2 points
A complete table of testing data must be given in Chapter 3, including testing the correctness (+0.5 pt.) and the performance (+1 pt.). A case generator program must be given to generate large amount of performance testing data (+0.5 pt.). Deduct (at most 2) points if:
- the testing results have a problem: some of the tick numbers are less than 10, which means that their answer is not accurate enough (-0.2)
- the case generator program is missing (-0.5)
- the testing results are not complete (-0.5~1)
- others – please specify in the final comments.
Item 5: 7 points
Plots (+2 pts.) and comments (+1 pt.) on comparisons of different approximations are supposed to be given in Chapter 4, together with the analysis of both the relations between the approximation ratio and the width of the strip (+2 pts.), and also between the approximation ratio and the different distributions of widths and heights (+2 pts.). **Give bonus (+1 pt.) if they have compared their algorithm to any of the known strip algorithms.** Deduct points if:
- the plot is missing (-2)
- the plot is misleading since the x-axis is NOT EQUALLY SPACED (-1)
- the analysis does not seem to fit with their testing results (-1)
- there is no comments on analyzing the relations between the approximation ratio and the width of the strip (-2)
- there is no comments on analyzing the relations between the approximation ratio and the different distributions of widths and heights (-2)
- others – please specify in the final comments.
Item 6: 7 points
A main program (+6 pts.) and a testing program (+1 pt.) must both be presented. Deduct points if:
- the testing program is missing (-1)
- some of the programs are not working properly (-1 ~ 3)
- the programs are not well-commented (-7)
- others – please specify in the final comments.
This project requires you to design an approximation algorithm that runs in polynomial time. You must generate test cases of different sizes (from 10 to 10,000) with different distributions of widths and heights. A thorough analysis on **all the factors** that might affect the approximation ratio of your proposed algorithm is expected.
### Grading Policy:
**Programming:** Implement the approximation algorithm (6 pts.). Write a test of performance program (1 pts.). **All the codes must be sufficiently commented.**
**Testing:** Generate the test cases and give the run time table (2 pts.). Plot the run times vs. input sizes for illustration (2 pts.). Write analysis and comments (5 pts.). The analysis must be based on your testing results.
**Documentation:** Chapter 1 (1 pt.), Chapter 2 (2 pts.), and finally a complete report (1 point for overall style of documentation).
**Bonus: Compare your algorithm to any of the known strip algorithms.**
**Note:** Anyone who does excellent job on answering the Bonus question will gain an extra point.
答案：Rubric items: 6
Item 1: 1 point
The cover page must be presented with the title and the date of completion (+ 0.2 pts.). A complete problem description must be given in Chapter 1 (+0.8 pts.). Deduct points if:
- the cover page is not complete (-0.2)
- the introduction is a simple copy + paste of the assignment statement (-0.3)
- the introduction is not very clear -- in this chapter they are supposed to make it clear WHAT is to be done, besides why they are doing it (-0.1 ~ 0.5)
- others – please specify in the final comments.
Item 2: 2 points
Chapter 2 is supposed to specify the approximation algorithm (+1 pt.), together with its time bound and approximation ratio (+1 pt.). Deduct (at most 2) points if:
- the description is way too simple (-1)
- the algorithm specification is not complete – the approximation algorithm description is missing (-1)
- the algorithm specification is not complete – the time bound and approximation ratio description is missing (-1)
- not making their algorithm easier to understand than a simple program (-1)
- only a program + comments, which is not acceptable (-1)
- others – please specify in the final comments.
Item 3: 1 point
The overall style of documentation is supposed to be neat and clear. Deduct (at most 1) point if:
- the document looks like a patch work (-1)
- messy – some of the data in the charts and tables are missing (-1)
- the hand-in is not zipped with proper folders (-1)
- the hand-in is not complete – some files are missing (-1)
- others – please specify in the final comments.
Item 4: 2 points
A complete table of testing data must be given in Chapter 3, including testing the correctness (+0.5 pt.) and the performance (+1 pt.). A case generator program must be given to generate large amount of performance testing data (+0.5 pt.). Deduct (at most 2) points if:
- the testing results have a problem: some of the tick numbers are less than 10, which means that their answer is not accurate enough (-0.2)
- the case generator program is missing (-0.5)
- the testing results are not complete (-0.5~1)
- others – please specify in the final comments.
Item 5: 7 points
Plots (+2 pts.) and comments (+1 pt.) on comparisons of different approximations are supposed to be given in Chapter 4, together with the analysis of both the relations between the approximation ratio and the width of the strip (+2 pts.), and also between the approximation ratio and the different distributions of widths and heights (+2 pts.). **Give bonus (+1 pt.) if they have compared their algorithm to any of the known strip algorithms.** Deduct points if:
- the plot is missing (-2)
- the plot is misleading since the x-axis is NOT EQUALLY SPACED (-1)
- the analysis does not seem to fit with their testing results (-1)
- there is no comments on analyzing the relations between the approximation ratio and the width of the strip (-2)
- there is no comments on analyzing the relations between the approximation ratio and the different distributions of widths and heights (-2)
- others – please specify in the final comments.
Item 6: 7 points
A main program (+6 pts.) and a testing program (+1 pt.) must both be presented. Deduct points if:
- the testing program is missing (-1)
- some of the programs are not working properly (-1 ~ 3)
- the programs are not well-commented (-7)
- others – please specify in the final comments.
