主观题：Performance Measurement (MSS)
In your textbook, several methods for solving the *Maximum Subsequence Sum* problem are discussed. Now let us extend this problem to 2-dimensional.
**MAXIMUM SUBMATRIX SUM PROBLEM:**
Given an $$N\times N$$ integer matrix $$(a_{ij})_{N\times N}$$, find the maximum value of $$\sum_{k=i}^m \sum_{l=j}^n a_{kl}$$ for all $$1\le i \le m \le N$$ and $$1\le j \le n \le N$$. For convenience, the maximum submatrix sum is 0 if all the integers are negative.
**Example:** For matrix
, the maximum submatrix is
and has the sum of 15.
The simplest method is to compute every possible submatrix sum and find the maximum number. An algorithm similar to Algorithm 1 given in Section 2.4.3 will run in $$O(N^6)$$, and the one similar to Algorithm 2 in $$O(N^4)$$.
Your tasks are:
- (1) Implement the $$O(N^6)$$ and the $$O(N^4)$$ versions of algorithms for finding the maximum submatrix sum;
- (2) Analyze the time and space complexities of the above two versions of algorithms;
- (3) Measure and compare the performances of the above two functions for $$N$$ = 5, 10, 30, 50, 80, 100.
- (4) **Bonus:** Give a better algorithm. Analyze and prove that your algorithm is indeed better than the above two simple algorithms.
To measure the performance of a function, we may use C's standard library **time.h** as the following:
**Note:** If a function runs so quickly that it takes less than a tick to finish, we may repeat the function calls for $$K$$ times to obtain a total run time, and then divide the total time by $$K$$ to obtain a more accurate duration for a single run of the function. The repetition factor must be large enough so that the number of elapsed ticks is at least 10 if we want an accuracy of at least 10%.
The test results must be listed in the following table:
The performances of the two functions must be **plotted** in the **same** $$N$$–run_time coordinate system for illustration.
###Grading Policy:
**Programmer:** Implement the two functions (30 pts.) and a testing program (20 pts.) with sufficient comments.
**Tester:** Decide the iteration number K for each test case and fill in the table of results (8 pts.). Plot the run times of the functions (12 pts.). Write analysis and comments (10 pts.).
**Report Writer:** Write Chapter 1 (6 pts.), Chapter 2 (12 pts.), and finally a complete report (2 pts. for overall style of documentation).
**Note:** Anyone who does excellent job on solving the Bonus problem will gain an extra **5%** of his/her points.
答案：Rubric items: 6
Item 1: 6 points
The cover page must be presented with the title and the date of completion (+2 pts.). A complete problem description must be given in Chapter 1 (+4 pts.). Deduct points if:
- the cover page is not complete (-1)
- the introduction is a simple copy + paste of the assignment statement (-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 (-1 ~ -2)
- others – please specify in the final comments.
Item 2: 12 points
Chapter 2 is supposed to contain the descriptions (pseudo-code preferred) of both methods involved (+5 pts. for each algorithm), plus a sketch of the main program (+2 pts.). Deduct points if:
- the algorithm specification is not complete -- they are supposed to specify all the algorithms involved, not only a sketch of the main program (-2 ~ -10)
- not making their algorithm easier to understand than a simple program (-2)
- only a program + comments, which is not acceptable (-4)
- others – please specify in the final comments.
Item 3: 2 points
The overall style of documentation is supposed to be neat and clear. Deduct (at most 2) points 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: 8 points
A complete table of testing data must be given in Chapter 3 (+4 pts. for each method). Deduct 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 (-1)
- the testing results are not complete (-2 ~ -8)
- others – please specify in the final comments.
Item 5: 22 points
Plots (+8 pts.) and comments (+4 pts.) on comparisons of the two algorithms are supposed to be given in Chapter 4, together with the analysis of both the time (+5 pts.) and space (+5 pts.) complexities of the algorithms. Deduct points if:
- the plot is missing (-8)
- there is no comments on analyzing why one algorithm is faster than another (-1 ~ -4)
- the plot is misleading since the x-axis is NOT EQUALLY SPACED (-1)
- analysis of the complexities of time and/or space is missing -- they must show how they have reached their conclusions, instead of simply listing them (-4 ~ -10)
- others – please specify in the final comments.
Item 6: 50 points
The programmer is supposed to implement the two functions (14 pts. each, plus 2 pts. for readability) and a testing program (20 pts.). Deduct points if:
- implementation of some of the functions are missing (-14 ~ -30)
- the testing program is missing (-20)
- some of the programs are not working properly (-1 ~ -20)
- the programs are not well-commented (-50)
- others – please specify in the final comments.
**MAXIMUM SUBMATRIX SUM PROBLEM:**
Given an $$N\times N$$ integer matrix $$(a_{ij})_{N\times N}$$, find the maximum value of $$\sum_{k=i}^m \sum_{l=j}^n a_{kl}$$ for all $$1\le i \le m \le N$$ and $$1\le j \le n \le N$$. For convenience, the maximum submatrix sum is 0 if all the integers are negative.
**Example:** For matrix
, the maximum submatrix is
and has the sum of 15.
The simplest method is to compute every possible submatrix sum and find the maximum number. An algorithm similar to Algorithm 1 given in Section 2.4.3 will run in $$O(N^6)$$, and the one similar to Algorithm 2 in $$O(N^4)$$.
Your tasks are:
- (1) Implement the $$O(N^6)$$ and the $$O(N^4)$$ versions of algorithms for finding the maximum submatrix sum;
- (2) Analyze the time and space complexities of the above two versions of algorithms;
- (3) Measure and compare the performances of the above two functions for $$N$$ = 5, 10, 30, 50, 80, 100.
- (4) **Bonus:** Give a better algorithm. Analyze and prove that your algorithm is indeed better than the above two simple algorithms.
To measure the performance of a function, we may use C's standard library **time.h** as the following:
**Note:** If a function runs so quickly that it takes less than a tick to finish, we may repeat the function calls for $$K$$ times to obtain a total run time, and then divide the total time by $$K$$ to obtain a more accurate duration for a single run of the function. The repetition factor must be large enough so that the number of elapsed ticks is at least 10 if we want an accuracy of at least 10%.
The test results must be listed in the following table:
The performances of the two functions must be **plotted** in the **same** $$N$$–run_time coordinate system for illustration.
###Grading Policy:
**Programmer:** Implement the two functions (30 pts.) and a testing program (20 pts.) with sufficient comments.
**Tester:** Decide the iteration number K for each test case and fill in the table of results (8 pts.). Plot the run times of the functions (12 pts.). Write analysis and comments (10 pts.).
**Report Writer:** Write Chapter 1 (6 pts.), Chapter 2 (12 pts.), and finally a complete report (2 pts. for overall style of documentation).
**Note:** Anyone who does excellent job on solving the Bonus problem will gain an extra **5%** of his/her points.
答案：Rubric items: 6
Item 1: 6 points
The cover page must be presented with the title and the date of completion (+2 pts.). A complete problem description must be given in Chapter 1 (+4 pts.). Deduct points if:
- the cover page is not complete (-1)
- the introduction is a simple copy + paste of the assignment statement (-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 (-1 ~ -2)
- others – please specify in the final comments.
Item 2: 12 points
Chapter 2 is supposed to contain the descriptions (pseudo-code preferred) of both methods involved (+5 pts. for each algorithm), plus a sketch of the main program (+2 pts.). Deduct points if:
- the algorithm specification is not complete -- they are supposed to specify all the algorithms involved, not only a sketch of the main program (-2 ~ -10)
- not making their algorithm easier to understand than a simple program (-2)
- only a program + comments, which is not acceptable (-4)
- others – please specify in the final comments.
Item 3: 2 points
The overall style of documentation is supposed to be neat and clear. Deduct (at most 2) points 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: 8 points
A complete table of testing data must be given in Chapter 3 (+4 pts. for each method). Deduct 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 (-1)
- the testing results are not complete (-2 ~ -8)
- others – please specify in the final comments.
Item 5: 22 points
Plots (+8 pts.) and comments (+4 pts.) on comparisons of the two algorithms are supposed to be given in Chapter 4, together with the analysis of both the time (+5 pts.) and space (+5 pts.) complexities of the algorithms. Deduct points if:
- the plot is missing (-8)
- there is no comments on analyzing why one algorithm is faster than another (-1 ~ -4)
- the plot is misleading since the x-axis is NOT EQUALLY SPACED (-1)
- analysis of the complexities of time and/or space is missing -- they must show how they have reached their conclusions, instead of simply listing them (-4 ~ -10)
- others – please specify in the final comments.
Item 6: 50 points
The programmer is supposed to implement the two functions (14 pts. each, plus 2 pts. for readability) and a testing program (20 pts.). Deduct points if:
- implementation of some of the functions are missing (-14 ~ -30)
- the testing program is missing (-20)
- some of the programs are not working properly (-1 ~ -20)
- the programs are not well-commented (-50)
- others – please specify in the final comments.
