Skip to main content

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 four 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. Note that your final report should not look like an outline. It should not have bullets and it should not have numbered paragraphs. It should be prose with paragraphs.

1. Introduction

  • One paragraph introduction

    • “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.

    • “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.

2. Implementation Deep Dive

  • Intro Paragraph

    • Briefly motivate why we are exploring a recursive implementation by comparing to the iterative implementation. A much more detailed comparison will be in the next section. This is mostly to act as a transition from mentioning all four implementations in the introduction.

    • Discuss the specification for the sqrt function (i.e., takes one argument and returns the (truncated) square root).

    • Might be a short paragraph? the goal is to make this paragraph more about the specification as opposed to the implementation, with just a hint of the implementation.

  • Recursive sqrt Implementation

    • FIG: include pseudocode for this impl of sqrt

    • FIG: include example for this impl of sqrt (different example from what was included in the handout)

    • Mention this impl uses a recursive approach
    • Reference FIGs and briefly discuss algorithm
    • Focus on what is the base case? what is the recursive case?
    • Discuss how corner cases are handled (negative input, overflow)
    • Expand a bit more on overflow since it is quite tricky

3. Qualitative Comparison

  • Maybe only one paragraph? Future PAs will likely have another paragraph on time complexity analysis, and a paragraph on space complexity analysis

    • Admit that the iterative 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.

    • Discuss that the recursive implementations are more complicated than the iterative implementations, but they designed to be faster than the iterative implementations.

    • Discuss that the recursive impl of pow is faster because it reduces the total number of multiplications by reusing previously computed results.

    • Discuss that the recursive 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).

    • Is there anything to say about interface? extensibility?

4. Quantitative Evaluation

  • Overview of approach

    • Mention that we will be evaluating six implementations.

    • Mention what the ranges we are considering are (see handout for what ranges you are supposed to explore)

    • Justify why these ranges are reasonable? These ranges 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 input 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.

  • Summary of iter vs. recur results

    • TABLE-1: include table with time for each implementation and the average time for each trial, maybe include the variance across the trials?

    • PLOT-1 and PLOT-2: The handout asks you to make two very specific plots that will show the trends for pow and sqrt for all six implementations as the inputs get larger. make sure these plots are legible with reasonable font sizes and that the colors work when printed in black and white.

    • Reference TABLE/PLOTs and mention that the recursive implementations are significantly faster than the iterative implementations. Quantify this performance benefit for some specific example inputs (i.e., the sqrt recursive implementation is 4x faster than the iterative implementation).

    • Talk more about the trends as the input gets larger.

    • 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?

  • Summary of our results vs standard C library

    • how do our results compare to the standard C library?

    • explain any difference if you can

5. 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.

  • Be sure to include some brief summary quantitative results too.

  • 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!