========================================================================== PA1 Report Outline ========================================================================== Many students initially struggle with the idea of preparing the programming assignment report. In previous courses, students often simply describe their code at a low level in a programming assignment report. In this course, we are challenging students to prepare reports that better demonstrate the student's understanding of the course content. Before starting to write the report, we encourage students to prepare a detailed outline. The outline should include one section for each of the five sections that will eventually make up the report. Under each section, there should be one bullet for each paragraph the student is planning to include in that section. This bullet should describe the topic of the paragraph. Under each bullet there should be several sub-bullets, one for each topic to be discussed in that paragraph. The outline should also explicitly include references to the figures, tables, and plots the student plans to include in the report. This is called a _structured approach_ to technical writing. Students are strongly discouraged from "just starting to write". Just like we should always plan our approach before starting to write our programs, we should plan our approach before writing the report. Students are encouraged to review their outline with the course staff several days before the deadline. This document includes a rough outline for a report for the first programming assignment. Keep in mind that any outline will evolve as you start writing the report. Students do not need to follow this outline, nor should students expect a similar outline for future programming assignments. This outline is simply meant as an example to demonstrate our expectations and our suggested approach for writing great reports; which ultimately will enable students to become great programmers. * 1. Introduction - Topic of Paragraph 1.1: one (possibly long?) paragraph overview + "Why are we doing this assignment?" Maybe motivate the idea of writing functions for complex math functions as necessary for using C to do numerical computing? More broadly, this PA acts as a warmup teaching us about the general compilation, testing, and evaluation process and the specific tools we will be using in the course. + "How does it connect to the lecture material?" We have learned about functions, conditional statements, and iteration statements in Topic 1, so potentially mention that here, but maybe also mention how the assignment connects to recursive thinking as discussed in Topic 2. We will be putting these concepts into practice in this assignment. + "Describe progress on the assignment" Mention that both implementations of pow and sqrt have been successfully implemented. + "Sentence or two that describes the implementations" Mention that the first implementations use an iterative approach while the second implementations use a recursive approach. First implementation of pow simply implements the mathematical definition, while the second implementation reduces the required number of multiplies by reusing previously calculated results. First implementation of sqrt uses a brute force linear search, while the second implementation uses a more efficient binary search. + "Students must include a brief qualitative and quantitative overview of the evaluation results" Mention that the recursive implementations are significantly faster than the corresponding iterative implementations. Include quantitative results such "the performance of the recursive implementation of pow (sqrt) was 3x (4x) faster than the iterative implementation when processing a random array of input values". + "Students must include some high-level conclusions" Mention that these results suggest the importance of considering the high-level algorithm to reduce computation as a way to improve the performance of mathematical functions. Possibly also mention the ability of recursive functions to elegantly implement recursive algorithms. * 2. First Implementation: Iterative Algorithms - Topic of Paragraph 2.1: Review what the pow/sqrt functions do + Mention that the pow function takes two arguments (b,e) and returns the base raised to the power of the exponent (b^e). + Mention that the sqrt function takes one argument and returns the (truncated) square root. - Topic of Paragraph 2.2: Discuss the first impl of pow func + FIG-1: include pseudocode for first impl of pow + Mention first impl will use a simple iterative approach + Reference FIG-1 and briefly discuss algorithm + Maybe include a simple example in appendix and reference? or maybe this is too simple, and save example for second impl? + Discuss how corner cases are handled (base zero raised to negative exponent, base 0 raised to 0, overflow, etc) - Topic of Paragraph 2.3: Discuss the first impl of sqrt func + FIG-2: include pseudocode for first impl of sqrt + Mention first impl will again use a simple iterative approach + Reference FIG-2 and briefly discuss algorithm + Maybe include a simple example in appendix and reference? or maybe this is too simple, and save example for second impl? + Discuss how corner cases are handled (negative input, overflow) - Topic of Paragraph 2.4: Discuss why these impls are interesting + Admit that these algorithms are naive, they will likely be slow ... but these algorithms are simple and easy to implement. + They will serve as good comparison points for the more sophisticated algorithms in the second implementation. * 3. Second Implementation: Recursive Algorithms - Topic of Paragraph 3.1: Emphasize same interface, different impls + Discuss that the second implementations should have the exact same functionality as the first implementations; difference is in the implementation/ + Pretty short paragraph? keep for parallel structure with previous section? - Topic of Paragraph 3.2: Discuss the second impl of pow func + FIG-3: include pseudocode for second impl of pow + Mention second impl will use a recursive approach + Reference FIG-3 and briefly discuss algorithm + Focus on what is the base case? what is the recursive case? + Maybe include a simple example in appendix and reference? see how the length of the report is working out + Discuss why this impl should be faster than first impl + Discuss how corner cases are handled (base zero raised to negative exponent, base 0 raised to 0, overflow, etc) - Topic of Paragraph 3.3: Discuss the second impl of sqrt func + FIG-4: include pseudocode for second impl of sqrt + Mention second impl will again use a recursive approach + Reference FIG-4 and briefly discuss algorithm + Focus on what is the base case? what is the recursive case? + Maybe include a simple example in appendix and reference? see how the length of the report is working out + Discuss how corner cases are handled (negative input, overflow) + Expand a bit more on overflow since it is quite tricky - Topic of Paragraph 3.4: Discuss why these impls are interesting + Discuss that the second implementations are more complicated than the first implementations, but they designed to be faster than the first implementations. + Re-iterate that the second impl of pow is faster because it reduces the total number of multiplications by reusing previously computed results. + Re-iterate that the second impl of sqrt is faster because it reduces the number of steps we need to do in the search. + Acknowledge that there is a trade-off between implementation complexity and performance (simple implementations are often slower than more complex implementations, start simple and justify the complexity if our performance requirements demand it). * 4. Testing Strategy - Topic of Paragraph 4.1: Overall strategy + Emphasize we are using a strategic approach to testing as opposed to an ad-hoc approach. + We are using unit-testing where we test small pieces of code in isolation before trying to use these pieces of code. + We will unit test each math function in isolation before using that function in the evaluation. + We will use a combination of basic tests, directed tests, random tests, and code coverage. + Maybe mention basic tests here in this paragraph? Basic tests are simplest possible test that should compile and test some minimal functionality; useful for "smoke testing" an implementation. - Topic of Paragraph 4.2: Directed testing + Why directed testing? Provide more confidence in the basic functionality, but also test key corner cases that the programmer already knows are important. + List the key categories of directed tests for both pow and sqrt. Each category maps to a unit test in the test program. Mention directed tests with small base and large exponent, large base and small exponent, negative base, negative exponent, zero base, zero exponent. Maybe include a table in the appendix with each type of test case and how many asserts were in each one? Mention total number of test cases and asserts? - Topic of Paragraph 4.3: Random testing + Why random testing? Help catch corner cases which were not explicitly covered in the directed testing, but also to just generally increase confidence in correct functionality. + List the key categories of random tests. Include some discussion of how the random tests were generated and verified (e.g., with the corresponding function from the C standard library). - Topic of Paragraph 4.4: Code coverage + Why code coverage? Important to check if there are any statements in the code which have not been executed by the directed and random tests. Helps increase confidence both basic functionality and corner cases have been tested. + Mention 100% code coverage. Discuss how code was maybe revised to improve code coverage by avoiding dead code. - Topic of Paragraph 4.5: Summary + Re-iterate multi-dimensional testing strategy including basic, directed, and random tests. + Summarize total number of test cases and asserts. + Re-iterate code coverage results. + Conclude with something like "these testing results provide compelling evidence that all implementations are correct". * 5. Evaluation - Topic of Paragraph 5.1: Overview of approach + Mention we will evaluate both implementations of each function by applying that function across an array of input values. + Mention what the datasets are: pow uses 100 random positive and negative doubles for both the base and exponent (see the pow.dat file); sqrt uses a sequence of 12 values ranging from 1 to 2147395599 (see sqrt.dat). + Justify why these datasets are reasonable? Both datasets will stress various aspects of the implementations and enable us to make broad general claims about the performance of each implementation. + Timing approach will be to use gettimeofday to time how long it takes to apply the function to the dataset. Mention because of the timing resolution of gettimeofday, we need to apply the function across the dataset many times (how many?) to ensure we can accurately measure the time. + Mention the need to do multiple trials to compensate for any variability in the system due to other programs being run or the operating system executing. + Mention that all output values are compared to reference values to ensure proper functionality. - Topic of Paragraph 5.2: Summary of results + TABLE-1: include table with time of each trial for each implementation and the average time for each trial, maybe include the variance across the trials? + Reference TABLE-1 and mention that the recursive implementations are significantly faster than the iterative implementations. Quantify this performance benefit (i.e., the sqrt recursive implementation is 4x faster than the iterative implementation). + Discuss _why_ the recursive implementations are faster. This involves briefly re-iterating some of the discussion from sections 2 and 3. The recursive implementation of pow does many fewer multiplications, while the recursive implementation of sqrt is able to use a binary search to quickly "zero-in" on the square root. + Ideally we would have some evidence to help explain the performance difference. This evidence could be a back-of-the-envelope calculation for how many multiplies are required in both implementations of pow, or how many comparisons need to be done for both implementations of sqrt? - Topic of Paragraph 5.3: Conclusions + Overall, the recursive implementations are significantly faster than the iterative implementations, although there is always a trade-off. In this case the trade-off is implementation complexity. + In this situation the performance benefit seems to outweigh the implementation complexity. + Might be good to end with the point that in practice, we should use the pow and sqrt functions from the C standard library (which are highly optimized) as opposed to writing them on our own!