Should I incorporate modularization (i.e. parts of Modularization: O vs SP) in this?

  STARTED: 11/8/03 11/19/03; 3/26/06

APPENDIX
PROBLEM SOLVING: DEVELOPING ALGORITHMS
(..)
NOTE:  Except for the first exercise, None of the following takes into account "modularization",
i.e. the divide and conquer aspect of software development; read about this in  Modularization: O vs SP. 
The following focuses, exclusively on algroithm development.

Problem solving is a "polymorphic" term used to cover any apparoach to determining unknowns (or "undones") based on a set of initial conditions...Most people think of problem solving in terms of math problems (this applies anything that uses math e.g. science, economics, etc.), but we also consider writing a theme, planning a trip, improving a curriculum, etc. as problem solving exercises.  (Even my task of trying to find a way of helping a "group" of prospective computer scientists develop "individual" algorithmic problem solving solving skills is a problem - but NOT one that has a clear, single answer.)  As diverse as these "problem solving examples" are, they all have one thing in common - once the problem is solved, the "problem solving" is finished (with the exception of "my" problem).  This is NOT true in problem solving associated with software development; in software development, solving the problem is only the first step.  The unique feature of problem solving in software development is the need to determine "every" step in the problem solving process so that they can be "programmed" so that a machine (the computer) can repeat the process over and over using different inputs.  There are two paradigms in software development, algorithmic and object oriented; actually the object oriented approach includes algorithmic development, so developing algorithms is part of every software development project.... Therefore, in the following presentation we are NOT talking about problem solving in the traditional sense (solve it and stop); we are focusing on problem solving strategies associated with software development (solve it and program it).  In fact we are not considering object-oriented development, but focusing on its subset, structured algorithm development (SAD), the problem of developing an efficient algorithm that satisfies a set of requirements, i.e. given specific inputs, the algorithm will perform, efficiently, a well defined task that results in specific outputs - I think that "task automation" is a more specific, descriptive name for this than "problem solving"

OUTLINE:

1. Learn how to use SACs (Structured Algorithm Charts), a "tool" for visually developing algorithms
2. Identify the basic constructs of "structured" algorithms and how they can be combined
   
1. constructs: sequence, selection, and repetition
2. two ways of combining constructs: sequential and nested
   
3. Gain experience developing structured algorithms (problem solving in software development) using SACs for:
1. selections in sequence and nested
2. repetition in sequence and nested
3. combined selections and repetitions
   
4. Integrate the preceding, into a generalized structured algorithm development strategy

1. The strategy for software development has (at least) four distinct phases, Analysis, Design, Implementation, and Maintenance, including Testing within each phase.  The first two phases, Analysis and Design, are "language independent", i.e. occur before any source code is written.  During these phases, language independent representations of algorithms (pseudocode or schematic diagrams) or software models (UML diagrams) are used to facilitate critical and creative thinking as well as to record design features.  In this presentation we are focusing on SAC diagrams, a nonstandard, but (in my opinion) the most "powerful" language independent representation of algorithms; we use them to facilitate both the analysis and design phases - in particular the later.
2. Regardless of their representation, all algorithms consist of a collection of "statements" some of which are  "control structures" that govern the flow of execution of the algorithm.
   
3. Regardless of their representation, fundamental statements include those for:
1. starting and stoping; stoping includes the termination of a procedure or function after which control is returned to a higher level algorithm that "called" the procedure or function.
2. input and output; this can involve:
1. different "kinds" of input, e.g. interactive input from a keyboard, reading data from a file, etc.
2. different "types" (a very special word in computer science!) of input, e.g. numbers (integers, mixed numbers, etc.), text, etc.
3. processing, e.g. math operations, text manipulation, etc. 
   
1. Processing statements have one of two fundamentally different forms:
1. Concrete statements that can be executed by a computer, e.g. the addition of two numbers, the concatenation of two character strings, a while loop, an if-then-else statement, etc.
   
2. Abstract statements are those that can NOT be executed by a computer.  Obviously, they must be replaced by concrete statements - before one moves to the implementation phase where you translate you algorithm into source code.  Usually abstract statements are written in terms of named modules  (subalgorithms, procedures or functions), within which concrete statements are written.
   
2. A block of statements is a collection of statements (both concrete and abstract); they may be "boxed" together just for convenience, but usually they are replaced by modules (subalgorithms,  procedures or functions).
   
4. control structures; all algorithms consist of a "sequence" of statements where the flow of execution is modified by two control structures ( Here is where 99.9% of the problem of algorithm development arise.):
1. selection which allows a single block of statementss to be executed depending on specific conditions; see section 2, below.
2. repetition which allows a single block of statementss to be repeated depending on specific conditions; see section 2, below.
4. Representation of algorithms:  Algorithms are "ideas", i.e. abstractions of the task we want a computer to perform.  To develop algorithms,  especially complex ones, we need a way representing the algorithm in a way that is not dependent on any particular programming language; we call these "language independent representations" of algorithms.  There are several ways to represent algorithms, but we discuss only two (pseudocode and SACs) here.
   
1. Pseudocode is a text based representation of algorithms.  See the separate Overview of Pseudocode.
   
2. Structured Algorithm Charts (SAC) is a schematic way of representing algorithms (one of several symbolic ways of showing algorithms).  To learn the SAC way of representating algorithms, see the following (which are presented in sequence, so you can read them all at once).  Note that the SAC technique is not standard, but it can be easily translated into traditional algorithm representation formats like flowcharts or pseudocode, which have (loose) standards.  On the other hand SACs have significant advantages over traditional flowcharts and especially pseudocode; to paraphrase Confuscious, "A SAC is worth a thousand pseudocode words!"  In fact a "blank" SAC diagram is a "power tool" that can help you "generate" the most efficient structured algorithm for the task you want to program - be sure to look out for this as you work through the exercise problems in section 3, below; if this is not apparent to you, after you finish, be sure to ask me what this means!  To begin learning how to use SACs study the following:
   
1. SAC symbols and formats.
   
2. Rules for constructing a SAC.
3. The fundamental "INPUT-PROCESS-OUTPUT" sequence.

1. Regardless of their representation, there are only two control structures (although there are several forms of each) that alter the normal sequential flow of algorithm execution thus governing the logic of the algorithm.
1. "selection" where, "if" a selection condition is met (i.e. it is "true"),  a single block of statements (selected from one or more alternative blocks) is executed before the original sequence is continued.  (The "block" selected by the selection construct can include any type instruction including other blocks and/or control structures - there is no limit.)
   
2. "repetition" where a single block of statements is repeated a specified number of times before the original sequence is continued.  (The "block" selected by the selection construct can include any type instruction including other blocks and/or control structures - there is not limit.)
2. Regardless of their representation, there are only two ways to organize control structures:
   
1. Sequential control structures are independent, i.e. occur one after another.
   
2. Nested control structures mean that one control structure "contains" other control structures within them.
3. The pseudocode representation of structured control structures simple uses descriptive words, e.g. if, while, for, repeat, etc.
   
4. To see the SAC way of representating control structures, see the following (which are presented in sequence, so you can read them all at once).
1. SAC REPRESENTATION OF SELECTION CONSTRUCTS:  If you are only interested in seeing how SAC selection constructs are written then ignore the EXERCISES; these are part of the hands-on approach to algorithmic problem solving in section 3, below.
   
2. SAC REPRESENTATION OF REPETITION CONSTRUCTS:  If you are only interested in seeing how SAC repetition constructs are written then ignore the EXERCISES; these are part of the hands-on approach to algorithmic problem solving in section 3, below.

3. HANDS-ON EXERCISES IN CLASSIC ALGORITHM DEVELOPMENT PROBLEMS:

STRUCTURED ALGORITHM CHARTS and ALGORITHMIC PROBLEM SOLVING is an organized approach to using selection and repetition (both in sequence and nested) in simple but classic algorithmic problems.  If you have not read the  first three sections of this document, start at the beginning.  If you are ready to begin the problem solving exercises start at SAC REPRESENTATION OF SELECTION CONSTRUCTS.  ( Beginners, e.g. COSC101 students should only use if-the-else for selection and  while () for repetition.)  If you want an overview of the problems before they are presented here they are:

1. Use SACs to illustrate the modularization of the trivial problem of reading an integer from a file (into a variable X) as well as inputing two integers, interactively, from the keyboard (into variables A and B) and outputing to the user's monitor the the sum, difference, and quotient of A and B as well as the product of the quotient, A/B times X.  (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.  (c) Modify the preceding SACs to include parameters.

1. 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.  PART II: Do the problems under the extensions of this problem (but don't peek at Selections, Part I until you have finished PART I!)
2. (a) Using SACs develop the algorithm that does the following:  Input a number; output whether the number is "negative", "positive", or "zero".  (b) Do the problems under the extensions of this problem (but don't peek at Selections, Part II until you have finished PART I!)
3. Using SACs develop the algorithm that does the following:  Input the three angles of a triangle; output whether the triangle is "equilateral" (all sides equal), "isoceles" (two sides equal), "scalene" (all sides different) or "Not a triangle"; if one of the angles is 90⁰, include "right" in front of the type of triangle.  Hints and simplifications can be found in Selections, Conclusion ( Don't peek at until you have exhausted your brain; this is the "best" complex selection problem in this presentation - so don't waste it!).

1. Using SACs develop the algorithm that does the following:  Input a sequence of numeric grades, calculate their average and determine the maximum and minimum values.  Terminate the input  with a -1.  If a number outside the range -1 to100 is input, output "not a valid grade.  Hints and simplifications can be found in Iteration, Part I.  ( Don't peek until you have exhausted your brain; this is the "best" combined looping and selection problem in this presentation - so don't waste it!).
2. 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).  Include an error trap so that if a negative number is input, the algorithm will keep prompting the user until a positive number (including 0) is entered, i.e. prevent the algorithm from proceding unless zero or a positive number. is input.  Hints and simplifications can be found in Iteration, Part II.  ( Don't peek until you have exhausted your brain; this is an illustrative exercise - so don't waste it!).
3. (a) Using SACs develop the algorithm that does the following:  Input a number and print a "number triangle that looks like:
   
   1
   22
   333
   4444
   .....
   
   where the bottom line consists of the number that was input. (b) Do the problems under the extensions of this problem (but don't peek at  Iteration, Part III until you have finished PART I!).
   

1. (a) 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.   (b) Do the problems under the extensions of this problem (but don't peek at  Simple Search Algorithm until you have finished PART I!) .
2. Expand the algorithm of PART IIA, number 1 to include determination of the maximum and minimum grades.  Also, to handle a mistaken input of "-1", have the algorithm prompt the user when "-1" is entered to see if input is to be terminated.
   

1. Preleminary Notes:
1. A language independent representation of an algorithm is a powerful tool to assist software development.  SAC diagramming is useful, powerful, and efficient way of developing structured algorithms. 
   
1. Any algorithm representation can be translated to any other.
2. Any language independent algorithm representation must be ultimately expressed, completely, in concrete" terms".
   
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 the task" for which the algorithm is being develop.
   
2. Generalized Strategy for SAD:
1. Analyze your task - thoroughly, i.e. identify and distinguish what you are "given", what "results" are required, and any special conditions, restraints, special cases, etc. apply to your task.
   
1. Specify identifiers., i.e. input variables, output variables, and (if obvious) modules for abstract instructions (indicated by verbs in the problem statement).
   
1. This was illustrated, in an almost trivial way, by Exercise 3.1 and repeated in all subsequent exercises in the preceding section.
2. ( Note that, since we are only covering algorithm development (not OOSD) you don't have to identify classes and other classifiers; however, in OOSD, this would be your starting point and algorithm development would be deferred to the phase when you develop the operations of each class.)
   
2. Design a language independent representation (SAC, flowchart, pseudocode) of your prototype algorithm.  (The following is written in terms of SACs, but it also applies to design using flowcharts or pseudocode.)
   
1. Categorize subtasks according to selection or repetition.
2. Prototype the task algorithm with blank SAC control structures.  (Using blank control structures to "guide" you in filling them in with the correct logical conditions is the unique "power" of a schematic approach to algorithm development; this can NOT be efficiently accomplished with pseudocode.)
   
1. Selection is prototyped with blank diamonds.  (Exercises 3.2, 3.3, and 3.4)
2. Repetition is prototyped with blank pentagons. (Exercises 5, 6, and 7; not yet covered)
3. 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.
2. Independent things require sequential diamonds, any of which may contain nested control structures.
4. 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.  (Remember that all algorithms can be written in terms of the fundamental control structures,  while(...) and If(...)-then-else; there are other constructs (switch/case, repeat, for, etc.) which you can use, but all selection and repetition instructions MUST be written using one of these; if you are unsure, use the classic while(...) and If(...)-then-else.
5. Debug your prototype algorthm, i.e.trace (desk check) its execution with a complete set of (simple) test data.  (This is "easier said than done"!)
3. Implement your prototype algorithm in the "most suitable" programming language.  (Note that, at the beginning of this phase, all pseudocode, SAC, flowchart, etc. representations of algorithms and UML, CRC card representations of class architectures MUST be written in terms of concrete instructions - that can be translated directly into source code for the programming language you plan to use.)
   
1. Test and Debug with a compr set of test data.
2. Document your software with with descriptions, schematics (SACs, UML class diagrams, etc.) and comments (both external and internal).
3. Maintain your implementation by doing all of the above when it becomes necessary to update your software.

1. What you should have learned in Part I:
1. Problem solving in software development is very different than in other disciplines.  In fact, once you have "solved the problem" YOUR problem just begins!
1. You have to "solve your problem" so thoroughly that you can give the "recipie" and/or "model" to a dumb machine!
2. You have to "bullet proof" your your algorithm/model so that it will work under all conditions even if "stupid" input is supplied!
3. You should search for the most efficient/elegant algorithm....
4.  Your language independent representations (SAC, flowchart, or pseudocode) MUST be, ultimately, expressed in terms that can be translated directly into source code of a computer language, i.e. they must be "concrete" statements.  (All abstract statements, e.g. Swap(x,y), must be translated to concrete statements, often in another module, e.g. a procedure, function, or method.)  This include representations for:
1. start or end of a program, module, etc.
2. input or output statements
3. assignment statements (Note that abstract statements like "count down by two" MUST be written explicitly, e.g. counter <- counter -2, where <- means assignment.)
   
4. selections statements (Beginners use only if-then-else.)
   
5. repetition statements (Beginners only while loops.)
2. We focused only on Algorithm development problems, one of the two strategies for software development.  (The other is OOSD.)
3. Algorithm design can be divided into two categories, each of which can be divided into two subcategories.  Understanding this will help you analyzed any algorithmic problem and then divide to conquer it.  The two/two categories are:
1. structured algorithm fragments have only two different kinds of control structures:
1. selection control stuctures
1. There are several selection structures, but the if-then-else is the most general and all others can be simulated using it.  Beginners, e.g. COSC 101 students, should only use this in their algorithms.
   
2. repetition control structures 
1. There are several repetition structures, but the while loop is the most general and all others can be simulated using it.  Beginners, e.g. COSC 101 students, should only use this in their algorithms.  (Actually the "loop forever" is the most general loop, but it is not widely implemented; anyway, it can be simulated using a while loop - how?)
2. Either/both selection algorithms and repetition algorithms can be organized only two ways:
1. control structures that are in sequence are independent and
1. sequential selections apply to all classification where something can have every category, e.g. a number can be one of integer/fraction as well as positive/negaive/zero; contrast with mutually exclusive categories under the next section.
   
2. control structures that are nested are dependent.
1. nested selections should be used to classify mutually exclusive categories. i.e. something can be classified in only one category, e.g. positive numbers, negative numbers, and zeros - a number can be only one of these.
   
4. To analyze your task:
1. Write out every identifier (e.g. for structured programmin: Input variables, procedure/function names,  Output variables) along with their types (e.g. integer, number, charactier, text, etc.), if possible.
2. Work through the problem/task by hand to understand what you are going to try to develop the algorithm (recipie) for.
   
2. What you should have learned in Part II:
1. Everything in Part I applies to Part II except the control structure studied is the loop instead of the selection.
1. Still - we can organize loops only two ways: in sequence and nested
2. Still - sequential loops are independent; nested loops are dependent.
3. {UNFINISHED}