CSCE 481: Seminar

Spring 2017

• Home
  
  
• Assignments
  
  
• Schedule
  
  

Algorithm Description Long Writing Assignment

The purpose of this assignment is to give you experience explaining details of a software algorithm, program, or routine. The idea is to take a real, existing program, and write a description of some piece of that program so that others can follow what was done.

You should first find an existing open-source software project -it should not be your own project that you made open-source, but it is OK if it is one you've contributed to. Any open-source software project will be OK, but it needs to be easily accessible by the TAs. Within that project, you should find some portion of it in which you can understand what is happening, and which can be described in a manner similar to an algorithm. You may describe the algorithm that is implemented, the routine that implements it, or a sequence of routines in a program that accomplish some task. Note that you don't have to understand the entire program, just some piece of it. You then should write a description of that portion of the program.

When finding a piece of code to look at, you are welcome to discuss with others (e.g. to find a reasonable piece of code to use), and to discuss with others how that code works. However, all of the writing should be your own.

Here are specific requirements:

• Your description should take 3-4 pages. You should adjust your scope to reflect that page limitation. For example, a description of low-level details might cover only a single algorithm or routine. A mid-level description might allow you to describe a class, and a high-level description might allow you to describe an entire program.
• You should clearly identify what part of the project you are going to describe and where it was found. There should be enough detail to allow the TAs to easily find the file/project when looking.
• You should give a description of the algorithm/routine/program using one of the formalisms outlined in the textbook: list, pseudocode, prosecode, or literate. Prosecode or literate descriptions are preferred. See chapter 7 of the textbook for more description. This point is the reason that you must choose a "chunk" of the code that can be described in an algorithm-like format.
• You should include at least one diagram or figure in your document. Note that you should not just copy a diagram or figure from elsewhere, but create your own. See chapter 6 of the textbook for information about figures, graphs, and tables.
• Generally, an algorithm description such as this would give a good sense of motivation for the algorithm and describe the ways it is used in the program. If you are familiar enough with the code that you can add such descriptions in, you are welcome to do so. Since you might not already be that familiar with the code as a whole, you do not need to do so for this assignment.
• You can still discuss items such as input, output, assumed preconditions, the steps that make up the algorithm, data structures used, limitations on the algorithm, performance (complexity or practical performance), and ways it could be used (even if it is not used that way in the program).

Identification

• High[10]: The section of code is clearly identified, and it is easy to follow directions to find the code.
• Medium[5]: The code is clearly identified, and the code can be located, but some effort is required.
• Low[0]: The section of code is not clearly specified, or it is very difficult to find the code itself.

Formalism

• High[15]: The algorithm description is given in a prosecode or literate style.
• Medium[10]: The algorithm description is given in a list or pseudocode style.
• Low[0]: No formalism is used for describing the algorithm.

Figures

• High[15]: Figures or tables amplify the material and are described or referenced in the written portion.
• Medium[10]: Figures or tables are of appropriate size, neither wasting space nor too hard to read.
• Low[0]: Figures or tables appear to be added ad hoc.

Steps and Data Structures

• High[20]: Clear expression of the steps followed and the data structures involved.
• Medium[10]: Steps can be followed, though with some concentration, or data structures not clearly stated.
• Low[0]: Cannot easily follow the steps of the algorithm/routine or the data structures used.

I/O and Precondtions

• High[15]: The input, output, assumed preconditions, and postconditions are clearly defined.
• Medium[10]: These aspects can be identified, though the description may be fuzzy.
• Low[0]: Cannot discern the input, output, or data structures.

Scope

• High[15]: The overall behavior of the algorithm is well-described, including limitations on ways it is used.
• Medium[10]: There is a general but vague sense of how the algorithm works.
• Low[0]: It is difficult to understand the overall function of the algorithm from the description.

Complexity/Performance

• High[10]: The complexity of the algorithm is clear and justified in a theoretical and/or practical sense.
• Medium[5]: There is a vague sense of how this routine would function theoretically or in practice.
• Low[0]: There is no sense of how this algorithm would perform in either a theoretical or practical sense.