STARTED: 11/8/0312/3/03

PRELEMINARY NOTES:

1. A language independent representation of an algorithm allows a software developer to design an algorithm that can be implemented in any programming language (that provides the required constructs).  Schematic representations (using diagrams) are more efficient than text representations (pseudocode) in prototyping algorithms.  The SAC representation is the most useful, most powerful, and and most efficient schematic representation of which I am aware. 
   
1. Any algorithm representation can be translated to any other, therefore, the nonstandard SAC can be translated to traditional flowcharts, pseudocode, etc.
2. Any language independent algorithm representation must be ultimately expressed, completely, in concrete" terms", i.e. terms that can be translated into program code. 
   
2. There are only two logic constructs (selection and repetition) in structured algorithms and only two ways to organize them (sequence and nested) so constructing algorithms is a relatively straightforward process, especially if the developer "understands":
1. what situations require selection and what requires repetition and
   
2. what situations require sequential constructs and what requires nested constructs.
1. Nested constructs are dependent.
1. Nested selections apply to "categorization" into mutually exclusive categories, e.g. a triangle can be either equilateral, isosceles, or scalene, but it can not be two of these.
2. Nested loops are interdependent, i.e. outer loops control inner loops.
   
1. Sequential constructs are independent, i.e. they do not affect each other.
1. Sequential selections apply to categorization into unrelated categories, e.g. a triangle can be a right triangle as well as an isosceles triangle or scalene triangle.
2. Sequential loops are independent, i.e. the execution of a second loop has nothing to do with the execution of  a preceding loop.

1. Analyze the task for which the algorithm is to be developed.  It is ESSENTIAL to UNDERSTAND the requirements of the task before you start designing the algorithm.
1. Analysis is facilitated if you specify every "identifier" (variables, attributes, arguments, or parameters) needed to store the data during algorithm execution.  These include identifiers to hold values for input, output, and internal processing.  This is accomplished in a SAC by drawing a space, at the beginning of the SAC (using a big bracket with a dashed connection to the SAC, i.e. - - - -[ ) for
   
1. writing concise abbreviations for every input and output identifier that is obviously required at the beginning of development (Abbreviations are for "your" convenience during "scratchpad prototyping"; these should be translated to meaningful names when implementing in a programming language.)
   
2. leaving space for adding identifier abbreviations that become needed as the algorithm is developed; these include local variables (temporary variables, counters, accumulators, etc.) and, perhaps, input/output identifiers overlooked at the beginning or recognized as being useful while development.
   
3. This was illustrated, in an almost trivial way, by Exercise 3.1 and repeated in all subsequent exercises in the preceding section.
2. Draw a picture (if possible) that illustrates the task for which you are developing the algorithm.  This helpful step is one that, in my experience, students ignore when faced with an algorithm development task.  It is most important in advanced tasks like developing algorithms that manipulate user defined data structures, like lists, trees, etc.
   
3. Manually do a "work through", i.e. work through the task, using the simplest data set that completely tests the task, to get a personal understanding of what is supposed to happen.   This ESSENTIAL step is another one that, in my experience, students ignore when faced with an algorithm development task.
1. For, example, if you are to develop an algorithm to find the average of a set of grades, do the following
   
1. Define what average means i.e. Average = GradeTotal/NumberOfGrades; this specifies the intermediate variables (GradeTotal and NumberOfGrades) that we have to use.
2. Select a simple but complete set of grades that will illustrate the step by step process of finding and then calculating Average; 8, 9, and 7 would be nice because we know what the average is, so we can easily check our algorithm as it progresses.  (Choosing a "realistic" set of grades, e.g. 83, 96, 54, 79, ... would only complicate our mental picture; such grades should be used to test our program, after it is coded - let the computer do the work.  While you are doing the work, KIS (keep it simple)!
   
3. Calculate the running totals, GradeTotal and NumberOfGrades - step by step, as a computer would have to do it i.e. using GT for  GradeTotal, NG for NumberOfGrades, and Ave for Average, ...
   

4. Calculate Average and compare it to the answer you "know" is correct.
5. NOTES:
   
1. Obviously this example is oversimplified for the sake of illustration so DON'T "BRUSH OFF" THIS MANUAL "WORK THROUGH" AS BEING TRIVIAL.  The more complex the task, the more important the work through is!
2. It is important to do the work through as if you were a computer, one simple step at a time; don't do anything "in your head".  Always keep in mind that your algorithm will have to be translated into computer source code, each instruction of which a computer can perform.
   
2. Only after you completely understand the detailed operations of your task should you go on to the next phase, designing a language independent representation of your algorithm.
   
2. Design a language independent representation (SAC, flowchart, pseudocode) of your prototype algorithm.  Continuously trace (desk check) your developing prototype with a set of simple test data. (This is another ESSENTIAL step that students too often ignore!)  For example, in the Average example, given above, tracing at the very beginning might reveal that you forgot to initialize the values of GradeTotal and NumberOfGrades to zero, something that is commonly done by beginners and would be a "disaster" on a test!
   
2. Categorize subtasks according to selection or repetition:
1. Selection is for things that you "might" do once, depending on the current situation, before continuing.  (See ...)
   
2. Repetition is for things you do over and over (how many times depends on the current conditions) before continuing....
   
3. Prototype the task algorithm with blank SAC control structures.  (This is the unique "power" of a schematic approach to algorithm development that can NOT be efficiently accomplished with pseudocode.)
1. Selection is prototyped with blank diamonds  (Exercises 3.2, 3.3, and 3.4)
   
1. If you need to select one of several mutually independent things, draw a single blank diamond with a line for each "thing you might do" going to the right.  This is just a "space holder" that needs to be refined, later, into nested  if-then-else diamonds (still selecting only one alternative) - at your convenience.
   
2. If you have several independent selections to make, arrange blank diamonds in sequence.
2. Repetition is prototyped with blank pentagons. (Exercises 5, 6, and 7)
4. Fill in the blank control structures so that they "say what you want the control structure to do"; this will help you generate the details, especially of nested control structures, e.g.
1. Mutually exclusive things require nested if-then-else diamonds; there is always one less diamond than there are mutually exclusive categories.  How the diamonds are nested (the order of nesting; whether nested under the "then" branch or "else" branch) can greatly affect the efficiency  and "elegance" of your algorithm.
2. Independent things require sequential diamonds (if-then, if-then-else, or nested selections) for each independent choice, e.g. if you are specifying sex and age categories, the fact that they are unrelated means you organize two selections in sequence.  (However, if you had more than three categories for age, e.g. child, teen, and adult, the age selection construct would be nested if-then-elses.)
5. Reduce all abstractions (blank control structures, module calls (to procedures, functions, or methods), or any unspecified task) to concrete statements that can be coded in the programming language to be used.
1. Note that, although algorithm development is, in general, language independent, if a language has a "short-cut", e.g. a high level construct not generally available in other languages, then they can be used in your algorithm.  However, if you do this, it should be remembered that your algorithm is NOT language independent.
6. Debug your prototype algorithm, i.e.do a final trace (desk check) with a complete set of (simple) test data.  (This is "easier said than done"!  Note that even though you faithfully traced your developing prototype continuously with "simple" data that tests small parts of your algorithm, this final trace must use a "complete" set of data (still simple) in order to cover all possible inputs and all possible abuses of the program by careless users!)  YOU MUST DO THIS FINAL DEBUGGING TRACE BEFORE SUBMITTING ANY ALGORITHM TO TONY; IT WILL SAVE YOU FROM CARELESS MISTAKES THAT WILL RESULT IN A LOWER GRADE - AND YOUR HAVING TO REDO YOUR "INCOMPLETE" SUBMISSION!!
   
3. Implement (actually irrelevant to this discussion of algorithm development) your prototype algorithm in the "most suitable" programming language. 
   
1. Write the source code equivalent of your detailed algorithm representation using a language that has an instruction set that can do all of your algorithm's instructions
   
2. Test and Debug with a complete set of test data.  At this point there is little need to KIS, because the computer is doing  the work; it is more important, in this phase, to use a complete set of data that tests every possible kind of input including incorrect input that must cause an error to be reported to the user.  (This is essentially the same idea as the final trace in
   
4. Document (actually irrelevant to this discussion of algorithm development) your software with with descriptions, schematics (SACs, UML class diagrams, etc.) and comments (both external and internal).  Do this for
1. users of your software and
2. maintainers of your software, i.e. who might modify, debug or otherwise update your software.
   
5. Maintain (actually irrelevant to this discussion of algorithm development) your implementation by doing all of the above when it becomes necessary to update your software.