主观题：Performance Measurement (POW)
There are at least two different algorithms that can compute $$X^N$$ for some positive integer $$N$$.
Algorithm 1 is to use $$N-1$$ multiplications.
Algorithm 2 works in the following way: if $$N$$ is even, $$X^N = X^{N / 2}\times X^{N / 2}$$; and if $$N$$ is odd, $$X^N = X^{(N-1) / 2}\times X^{(N-1) / 2}\times X$$. Figure 2.11 in your textbook gives the recursive version of this algorithm.
Your tasks are:
- (1) Implement Algorithm 1 and an **iterative** version of Algorithm 2;
- (2) Analyze the complexities of the two algorithms;
- (3) Measure and compare the performances of Algorithm 1 and the iterative and recursive implementations of Algorithm 2 for $$X=1.0001$$ and $$N$$ = 1000, 5000, 10000, 20000, 40000, 60000, 80000, 100000.
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 three functions must be **plotted** in the **same** $$N$$–run_time coordinate system for illustration.
###Grading Policy:
**Programmer:** Implement the three 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).
答案：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.
Algorithm 1 is to use $$N-1$$ multiplications.
Algorithm 2 works in the following way: if $$N$$ is even, $$X^N = X^{N / 2}\times X^{N / 2}$$; and if $$N$$ is odd, $$X^N = X^{(N-1) / 2}\times X^{(N-1) / 2}\times X$$. Figure 2.11 in your textbook gives the recursive version of this algorithm.
Your tasks are:
- (1) Implement Algorithm 1 and an **iterative** version of Algorithm 2;
- (2) Analyze the complexities of the two algorithms;
- (3) Measure and compare the performances of Algorithm 1 and the iterative and recursive implementations of Algorithm 2 for $$X=1.0001$$ and $$N$$ = 1000, 5000, 10000, 20000, 40000, 60000, 80000, 100000.
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 three functions must be **plotted** in the **same** $$N$$–run_time coordinate system for illustration.
###Grading Policy:
**Programmer:** Implement the three 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).
答案：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.
