PROBLEM SOLVING: DEVELOPING ALGORITHMS

PROBLEM SOLVING: DEVELOPING ALGORITHMS

The divide and conquer aspect of software development; it focuses, exclusively on algorithm 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"

[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

[i]constructs: sequence, selection, and repetition
[ii]two ways of combining constructs: sequential and nested

[3]Gain experience developing structured algorithms (problem solving in software development) using SACs for:

[i] selections in sequence and nested
[ii]repetition in sequence and nested
[iii] combined selections and repetitions

[4]Integrate the preceding, into a generalized structured algorithm development strategy

1.INTRODUCTION TO STRUCTURED ALGORITHM CHARTS (SAC):

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.

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.

Regardless of their representation, fundamental statements include those for:

[a]starting and stopping; stopping includes the termination of a procedure or function after which control is returned to a higher level algorithm that "called" the procedure or function.

[b]input and output; this can involve:

[i]different "kinds" of input, e.g. interactive input from a keyboard, reading data from a file, etc.
[ii]different "types" (a very special word in computer science!) of input, e.g. numbers (integers, mixed numbers, etc.), text, etc.

[c]processing, e.g. math operations, text manipulation, etc.

Processing statements have one of two fundamentally different forms:

[i]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.

[ii] 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 (sub algorithms, procedures or functions), within which concrete statements are written.

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

[d]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.):

[i]selection which allows a single block of statementss to be executed depending on specific conditions; see section 2, below.
[ii]repetition which allows a single block of statementss to be repeated depending on specific conditions; see section 2, below.

[e]Using SACs is one of several ways to developing sturctured 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:
SAC symbols and formats.
Rules for constructing a SAC.

The fundamental "INPUT-PROCESS-OUTPUT" sequence.

2. THE BASIC LOGIC CONSTRUCTS (CONTROL STRUCTURES) OF STRUCTURED PROGRAMMING:

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.

[a] "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.)

[b] "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.)

Regardless of their representation, there are only two ways to organize control structures:

[a]Sequential control structures are independent, i.e. occur one after another.
[b]Nested control structures mean that one control structure "contains" other control structures within them.

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

[a]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.

[b]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: