Draft Created: 5/26/98; 11/11/03
This REFERENCE is only a skeleton of what it is intended to be.
FIBs & SACs must be added.

       In the1960's it was mathematically proven that any programmable problem can be solved using only three logic control structures, sequence, selection, and repetition (iteration or recursion), that govern the flow of execution of any algorithm or program.   These along with modularization structures became the constructs (building blocks) of "structured programming", a strategy, developed in the 1970s, that facilitated the development of modular programs that were easy to develop, debug, and modify.  Previous programming languages, that did not have these structured programming constructs, relied on the GOTO statement to control the flow of program execution.  The GOTO instruction is a low level (equivalent to machine language) construct, that could jump to any specified line in a program).  This was a powerful construct, but it allowed (and some say encouraged) undisciplined software development that promoted "buggy" software.    Flowcharts, language-independent diagrams developed to illustrate the logic of algorithms, were oriented towards GOTO programming; the arrows of the flowcharts represented the GOTO statements.  Structured programming, on the other hand, is "GOTO-less programming" so flowcharts fell out of fashion; they were replaced by pseudocode (concise, English-llike statements that indicated the flow of the program logic).  However, "A picture IS worth a thousand words.", so the methodology of flowcharting was adapted to the format of structured programming.  Several versions of structured flowcharting appeared, but, unfortunately, none became a standard.  The structured flowcharting proposed by G. W. Williams, the Editor of Byte Magazine, in the March, 1981 issue (no online archive) most effectively illustrates the logic and format of structured program code.  Structured Algorithm Charts (SACs), presented below, are extensions of Williams ideas.  A comparison of the results of representing an algorithm using old-fashoned flowcharts to a representation using SACs is given here.

SAQ1: What is the (a) similarity and (b) difference between a "construct" and a "control structure"?

The goals of this learning module are:

1. to present the elements of SAC diagrams,
2. to illustrate the constructs of structured algorithms using SACs,
3. to illustrate the various ways the constructs of sturctured algorithms can be organized to achieve fundamental logic constructs, and
   
4. to illustrate classic" algorithmic problem solving examples in order to improve "problem solving skills" and "task automation skills".
   

1. SAC FORMAT
2. RULES FOR CONSTRUCTING A SAC
3. SAC REPRESENTATION OF THE FUNDAMENTAL INPUT-PROCESS-OUTPUT SEQUENCE
4. SAC REPRESENTATION OF SELECTION CONSTRUCTS
5. SAC REPRESENTATION OF REPETITION CONSTRUCTS
6. COMBINED REPETITION AND SELECTION
7. MODULARIZATION AND TOP-DOWN ALGORITHM DESIGN
8. SUMMARY

    In order to be a completely general tool for developing or illlustrating structured algorithms that are clear, precise, and concise, a SAC must emphasize human-oriented logic rather than machine-oriented logic of old-fashioned flowcharts.  The following rules reflect this principle.  (See Table SAC-1 for a reference to the symbols mentioned.)

1. SAC RULES:
1. A SAC must clearly distinguish the three fundamental control structures as well as invoke operations (of the same class or, implementing the dependency relationship, of other classes).
1. The three constol structures of structured programming include the following.
1. The sequence is represented by a simple vertical line connecting constructs (elements of of a SAC) in a top-down sequence.
2. Selection is represented by the traditional diamond; however, unlike traditional flowcharting, the lines connecting the possible selected constructs flow only from left to right and then, if necessary, top down.  (This restriction insures that all SAC diagrams are top down or left right; thus the developer can begin prototyping a SAC at the upper left corner of a "scratch pad", knowing that no logic construct will ever go up or to the left.)  See section 4 for the case/switch, if, and if-then-else forms of selection.
3. Repetition is represented by the only "new" symbol, the hexagon.  (It is new in that it was not present in older "goto oriented flowcharts"; the diamond was used in original flowcharts because iteration (looping) was viewed as a selection construct, i.e. the flow of control branched upwards to repeat a sequence of instructions or it branched downward to the instructions following the "loop".)  Like the lines of the selection construct, the lines of repition flow left right, top down.   See section 5.
2. A block of instructions is represented by by a rectangle or parallelogram with a descriptive name that explains the result of the instructions.  This implements "abstraction", i.e. the replacement of detailed instructions with a meaningful name.
1. The rectangle is the most general of the SAC constructs; it represents a process, that could contain any self-contained algorithm, i.e. its own SAC.
2. The parallelogram represents a process that serves as input/output.
3. A SAC must clearly represent operation invocations (or OO messages), i.e. transfer of control to operations which must return control, after the operation is completed, to the instruction following the invocation.  Such "calls" or messages are represented by adding double sides to the rectangle,  parallelogram, or hexagon (recursive operations) that represents a complete algorithm (possibly represented by a "subSAC").
2. A SAC should have a top-down flow of execution, containing only blocks or operation invocations, that is modified only by selection or repetition constructs.   Each selection or repetition construct interrupts the top-down (sequential) flow with a left-to-right line that links to a process or new (indented) top-down sequence.  (Most of the following examples show selection or repetition constructs with a single process but SAC EXAMPLES 7, 8, and 9 illustrate new, indented top-down sequences.)  The top-down, left-right format has two distinct advantages (not available in standard flowcharting).
1. SAC development space may be efficiently used.  Since all SACs are developed in a top-down, left-right order, the developer can draft a new SAC by starting the SAC in the upper left corner of a page, without worrying about the algorithm development ever requiring upward or left-right flows of control, that often occur in traditional flowcharting.
2. A SAC mirrors the indentation convention of structured code. Every time a SAC control structure has a line to the right, the corresponding code will be indented one level.  This also makes it easy to develop a SAC from existing code.
3. An optimum number of construct symbols should be used.  There should be enough different symbols to distinguish fundamentally different consturcts (control structures, processing, input/output, beginning/end symbols (including arguments and return values), and documentation).  On the other hand, too many symbols would defeat the purpose of representing the logic of an algorithm clearly, precisely, and concisely.  Therefore, the several possible varieties of the following general constructs will each be represented by a single symbol.
1. Iteration constructs (loop, while, do-while/repeat-until, for, etc.) are all representeed by a right pointed hexagon; they are distinguished by their names.
2. Selection constructs (if-then, if-then-else, or switch/case constructs) are all represented by a diamond; they are distinguished by their names.
3. Input/output constructs (input or output) are represented by parallelograms; they are distinguished by their names.
4. Processes and operation invocations are represented by rectangles; they are distinguished by their names.
5. Beginning and end symbols are represented by ovals; they are distinguished by their names.

TABLE SAC-1: SAC SYMBOLS

Beginnin or end of a SAC or subSAC.  The beginning symbol contains the algorithm name; the end symbol contains END for a program or Main method and RETURN(with output parameters, if needed) for a subSAC.       Documentation, I/0 parameters, or declarations     Input or output statements       Statement or block of statements         Operation invocations (messages) in OOSD; module invocations (e.g. procedure or function calls) in structured programming.  May or may not have a subSAC.       Selection: (1) An "If" construct has a single line extending to the right linking to another construct.  (2) An "If-then-else"  has two lines, extending to the right, linking to other constructs.  (3) "Switch"/"case" constructs have multiple lines, extending to the right, linking to other constructs.     Repetition: (1) iteration (Loop, while, repeat-until (do-while), for, etc.); (2) recursion is represented by a double sided, left pointing hexagon, above.

2. RULES FOR CONSTRUCTING A SAC:

1. The flow of control should always be top-down (sequence) or left-right (initiation of selection or iteration); no arrows are used.
2. Only symbols from TABLE SAC-1 are used.
3. Operation invocations (messages to objects) are represented by the operation name, inclosed within a double sided symbols, e.g. rectangles (representing                        ()) parallelograms (representing                        ()), or right pointed pentagons (representing                        ()), e.g.

   or  or

Modules may refer to separate "subSACs" located elsewhere, which show the details of the module referenced by the name written within the symbol.  One should distinguish between modules which have separate subSacs (refresented by solid sided symbols, e.g.  ) and those which are purely descriptive, that is they do not have separate subSACs (e.g.  ).  If a language provides modules (methods, functions, or procedures) that allow parameter passing, these symbols represent "calls" to the subprogram named in the parallelogram or rectangle (e.g.  ) calls a subSAC method  that switches the values of parameters A and B.

4. There is only one entrance and one exit for each SAC construct.  Premature exits from a loop or operation are acceptable, but there is only one exit "point", the end of the construct.
5. The labelling of constructs is language dependent.  The language used in this presentation is English with a syntax based on Pascal-like languages, e.g. Pascal, Modula, Ada, etc.

1. Virtually all "programs" will first input "data", then process it, and output it as "information".

INPUT AND OUTPUT SACS

2. OO I/O....reflect that attributes are encapsulated with associated operations within classes; therefore, input/output is disassociated from processing.

  (a) Draw the SAC of a first level algorithm that only has three procedures, GETDATA, PROCESSDATA, and OUT.   (b) Assume that the programming language contains a "write" statement that can handle the output in one statement, draw the second level algorithms for the subalgorithms GETDATA and PROCESSDATA without using parameters.  PART II: Modify the SACs in part I to include parameters.  To get help, see

4. SAC REPRESENTATION OF SELECTION CONSTRUCTS:

This section illustrates the format and use of SAC selection constructs by discussing the simplest possible examples of fundamental selection categories.  It reviews the main concepts in selection control structures and the basic techniques used to employ selection correctly and efficiently.  The presentation is via example, the classification of a grade into three categories.  Note that the classification into three categories is the simplest selection task that still illustrates all the main features of selection.  Also note that the following is completely language independent.

THE TASK: Design an algorithm component (portion of a SAC) that, depending on the value of the score, S, classifies the grade, G, into three categories: G is "High" if S >= 90 (greater than or equal to 90), "Medium" if S < 90 and >= 60, or "Low" if S < 60.  (Note that these categories are "mutually exclusive", i.e. no value can be in more than one category; mutually exclusive categories form a very large, often used type of selection problem!)

The first version representation (call it a "prototype selection") of this construct would simply be drawing the selection diamond with three categories extending to the right, i.e.

Label the branches in the preceding "prototype" selection construct so that it reflects the logic required to accomplish "THE TASK".  In the following sections we will look at three ways to implement the above logic.  (Note that there are only two ways to use if-then-else constructs: sequential and nested.  Watch how these turn out!)

4.1 Switch (case) Implementation of THE TASK ( impractical ):

1. The switch statement (languages using ANSI standard C terminology) or case statement ( Pascal-like languages, e.g. Modula and Ada) can have any number of independent blocks. 
   
2. Switch/case statements are ideal for selecting categories, each of which have specific ranges of selection values; however, such constructs can not make selection based on boolean conditions  which are needed for our problem.
   
1. A switch/case could be used if all values were integers, i.e. the the three cases would be identified with 90..100,  60..89, and 0..59 along the branches of the case construct.
   

4.2 Sequential Implementation of THE TASK (three mutually exclusive categories -  inefficient ):

1. Fill in the blanks in the following SAC to make the logic equivalent to the previous implementations of THE TASK.






2. An important question now arises: Is the sequential if implementation of classification of mutually exclusive categories a "good" implementation?  To answer this, consider two cases.
1. Assume that the first if statement had s >= 80 as its condition and the second had the condition S >= 60.
1. Do a trace for a complete set of test data, e.g. for values of 90, 70, and 30.
2. Hopefully you detected the logic error characteristic of inappropriate sequential selections.  Note that the logic works for two of the three values but not the third.  ( This should emphasize the importance of doing a trace of any logic construct with a complete set of test data!) thus the sequential if implementation of mutually exclusive classification is not only more inefficient than the nested if implementation, it is more dangerous because it is easy to overlook subtle bugs!
3. The sequential if algorithm can be made to work.  If you haven't alreay done so, change the conditions to make the logic correct.  ( Hint: use compound conditions.)
2. Even if it is made made to work, the sequential if implementation is essentially less efficient that the nested if implementation (See the next section) for mutually exclusive categories like those in this example.

SAQ 6: Why do we use an if-then and an if-the-else instead of two if-then-elses (or an if-then-else followed by an if-then) in the sequential if implemenation of this example.
SAQ 7: Inmplement the error traps, given in SAQ 5.  Does this help you answer the first SAQ under section 3.1?  It should!)

EXERCISE 2: Using SACs develop the algorithm that does the following:  Input the name, sex, and age of a person; output the name followed by 

" is a male " or " is a female "; if the person is older than 65 append " and is retired.", otherwise end the sentence with a period.  (Note that the selections in this problem are "independent".)   To get help, see

4.3 Nested If Implementation of THE TASK (the most efficient way to classify three mutually exclusive items):

1. Fill in the constructs, below, to make the control structure, categorize the grade G as shown.






2. The real advantage of the SAC approach to algorithm development is that leaving the construct specification details blank allows us to think our way through the logic of a task, without getting "bogged down" with the details.  In this case, specifiying the categores while leaving the selection conditions blank helps quickly generate the most efficient selection conditions necessary to fulfill the task.  Note that the SAC actually guides us to the solution.  This graphically illustrates that the SAC technique is a "power tool" for logical thinking and a key to algorithm development.
3. Note how the nested if implementation of selecting mutually exclusive categories is not only more natural than the sequential if implementation but it is more efficient, and is less susseptable to subtle bugs!

Does this help you answer the SAQ 8, above?  It should!)

  (Note that the selections in this problem are "mutually exclusive".)   To get help, see

EXERCISE 4:

  (Note that the selections in this problem are "mutually exclusive".)   To get help, see

5. SAC REPRESENTATION OF REPETITION CONSTRUCTS:

1. Repetition in Algorithms has two special cases, iteration (looping) and recursion.





 
1. Iteration is the primary repetition control construct of imperative programming languages but recursive procedures and functions are avaiable in structured programming languages and recursive methods are avaiable in all OOPL.
2. Recursion is the primary repetition construct of declarative programming languages, which seldom have iteration constructs.
2. Iteration Categories:
1. Indefinite Loops repeat a block of instructions as long as a looping condition is true, i.e. something has to be true for the repetition to continue; when this condition changes to false the loop is exited.
1. the Loop construct is the most general iteration construct.  There is no looping condition associated with the loop itself; selection constructs  within the loop body are used to exit the loop.





 
2. the While  construct:

SAC for a Generic While Loop	SAQ: Equivalent using a Loop

  To get help, see

1. the Repeat until construct (do while in languages based on C):




SAC for a Generic Repeat-Until Loop	SAQ: Equivalent using a Loop

2. A Definite loop is one where the number of repetitions can be determined at the beginning of a loop construct.
1. The for loop is a count-controlled definite loop.  The labelling convention used below is based on Pascal-like languages, e.g. Modula, Ada, etc.

SAC for a Generic For Loop	SAQ: Equivalent using a Loop

EXERCISE 6: PART I: Using SACs develop the algorithm that does the following:  Input an integer and output its factorial. (The factorial of N is N(N-1)(N-2)...(3)(2)(1), e.g. the factorial of 4 is 24 (4*3*2*1).   To get help, see Definite Iteration but do nothing more than use it to prompt you when you get stuck, i.e. do NOT sneak a peak until your problem solving is exhausted and it becomes "frustrating" - "thinking" we want, "frustration" we don't!.  PART II: Do the problems under the extensions of Definite Iteration.

1. the repeat loop is the simplest type of loop, e.g. the loop body of a repeat 4 would be executed exactly four times.

SAQ 14: What is the (a) similarity and (b) difference between (1) iteration and recursion,  (2) loop, while loop, and repeat loop, and (3) indefinite loop and definite loop?
SAQ 15: A repeat loop can be simulated using a while loop.  How?
SAQ 16: What looping cases can not be done using a while or repeat loop?

3. Combinations of Repetition constructs:
1. Sequential iterations are completely independent.
2. Nested iteration are dependent; the execution of inner loops depends on the outer loops.
   

EXERCISE 7: PART I: Using SACs develop the algorithm that does the following:  Input a number and print a "number triangle that looks like:

  To get help, see

6. COMBINED REPETITION AND SELECTION:

{EXPAND}
EXERCISE 8: PART I: Develop the algorithm for an "Interger Searcher" that accepts a single integer as input and then searches a file of integers until it finds the first occurance of the integer input, and then prints out the location of that first occurance, i.e. the position of that integer as measured from the first integer in the file.   To get help, see Simple Search Algorithm but do nothing more than use it to prompt you when you get stuck, i.e. do NOT sneak a peak until your problem solving is exhausted and it becomes "frustrating" - "thinking" we want, "frustration" we don't!.  PART II: Do the problems under the extensions of Simple Search Algorithm.

7. MODULARIZATION AND TOP-DOWN ALGORITHM DESIGN:

{WRITE THIS.}

8. SUMMARY: