Software can be:

• complex
  • “has many parts”
• complicated
  • “has a high level of difficulty”
• Need design approaches

Decomposition

• Breaking a complex problem or system into a collection of smaller parts
• Start with the initial problem or system, and apply decomposition recursively
• When performed correctly, the smaller parts are easier to: design, implement, comprehend, test, maintain, and reuse
• Design answers the question: What parts do I need to solve this problem, and how do these parts relate to each other?
• Possible tradeoffs: efficiency

Algorithmic Decomposition

• Breaking a complex algorithm into a collection of smaller algorithms
• Start with the initial algorithm, and apply algorithm decomposition recursively
• When performed correctly, the smaller algorithms are easier to: design, implement, comprehend, test, maintain, and reuse
• Design answers the question: What algorithms do I need to solve this problem, and how do these algorithms relate to each other?
• Possible tradeoffs: efficiency

Rainfall: Algorithmic Decomposition

• Input rainfall data
• Calculate maximum rainfall
• Calculate average rainfall
• Output the rainfall report

Modeling Decomposed Structure

• Data-Flow Diagram (DFD)
  • Shows data exchanged between elements
• Hierarchy Chart or Organization Chart
  • Shows levels of elements
• Structure Chart
  • Shows levels of elements and the data exchanged between the elements

Structure Chart

src

Rainfall: Structure Chart

Function Decomposition

• Breaking a function down into a collection of smaller functions
• Start with the main function, and apply function decomposition recursively
• When performed correctly, the smaller functions are easier to: design, implement, comprehend, test, maintain, and reuse
• Design answers the question: What functions do I need to solve this problem, and how do these functions relate to each other?
• Possible tradeoffs: efficiency

What Functions Care About and Algorithms Don’t

• input source and format, e.g., Where did the array data come from?
• output source and format, e.g., Where is the data going to?
• exact syntax used, e.g., What language features do we use?
• interface, e.g., What name, parameters, and return type does the functions have?
• options and special cases

Structure Chart

src

Rainfall: Structure Chart

Information Hiding

• Hide the internal details of a part, algorithm, or function, and only expose the minimal interface
• information can be specific values, complex operations, complex series of operations, knowledge, etc.
• interface includes what we pass IN, OUT, and IN/OUT
• This is what gives decomposition its advantages

Rainfall: Structure Chart

Relation to functions

• Functions created by algorithmic decomposition work only on the data in the parameters given (IN, OUT, and IN/OUT)
• These functions are operations, actions, etc. on some data

Interface and Functions

• name
• parameters
• return type

IN, OUT, and IN/OUT in C++

functions and State

• In general, free functions do not save state between calls; they do not have any internal “memory” between calls
• Parameters and local variables are created when the function is called and destroyed when the function call returns
• Mostly exhibit consistent behavior, i.e., if passed same data, produces same result, e.g., double average(const std::vector<int>& v)
• Note: There are ways around this, but use object-oriented approaches instead

Algorithmic Decomposition and OOP/OOD

• A lower-level approach needed for OOP/OOD
• Algorithmic decomposition only scales so far
• Primary challenge of modern applications is not algorithmic complexity but the sheer number of things to keep track of
• Core algorithms for a particular problem often do not change over time, but surrounding code does, e.g., input formats, output formats