Object-Oriented Programming

Algorithmic Decomposition

Michael L. Collard, Ph.D.

Department of Computer Science, The University of Akron

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++

IN void f(int data); value
  void f(const Data& data); const reference
  void f(const Data* data); const pointer
OUT void f(int& data); reference
  void f(Data& data); reference
  void f(Data* data); pointer
  void f(Data** data); pointer to pointer
  int f(); return
  Data f(); return
  const Data& f(); return
IN/OUT void f(int& data); reference
  void f(Data& data); reference
  void f(Data* data); pointer
  void f(Data** data); pointer to pointer

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