3.2 - Software Development

Table of Contents

1 Abstraction and Automation

Problem Solving Using Algorithms

Computer science is about building clean abstract models (abstractions) of messy, noisy, real world objects or phenomena. Computer scientists have to choose what to include in models and what to discard, to determine the minimum amount of detail necessary to model in order to solve a given problem to the required degree of accuracy.

Computer science deals with putting the models into action to solve problems. This involves creating algorithms for performing actions on, and with, the data that has been modelled.

Algorithms

  • A finite steps of instrcution/steps to solver a specific problem; Algorithms can be expressed in the following forms:
    • Flowchart
    • Psuedo-code
    • Structured English
  • Algorithms employ with the standard constructs:
    • sequence
    • assignment
    • selection
    • iteration
  • Dry run an algorithms or hand tracing means to the programmer working through a program on paper, usually using a table called a 'trace table'.
  • To test a solution, there needs to be a set of test data that will thoroughly test the solution:
    • typical/normal/valid data: the solution expected data including type and range
    • extreme/boundary data: Data that is on the extreme limits of the range but should be accepted e.g. if the validation says that price <=£100 then £100 should be tested as that is right at the upper limit.
    • erroneous/invalid data: the solution should output error for those data; either because of wrong type or exceeding the limits.

Abstraction

Abstraction can be achieved by:

  1. representational abstraction: a representation arrived at by removing unnecessary details
  2. abstraction by generalisation or categorisation: a grouping by common characteristics to arrive at a hierarchical relationship of the "is a kind of" type.

Procedural abstraction:

  • Disregards the actual values, the result of a procedural abstraction is a procedure/computational method, not a function. To get a function requires yet another abstraction, which disregards the particular computation method. This is functional abstraction.

Data abstraction:

  • details of how data are actually represented are hidden, allowing new kinds of data objects to be constructed from previously defined types of data objects.
  • For example, a stack could be implemented as an array and a pointer for top of stack. A tree can be implemented as three arrays with one for the left pointer, one for the right pointer and one for the nodes' values.

Problem abstraction:

  • Details are removed until the problem is represented in a way that is possible to solve because the problem reduces to one that has already been solved.

Decomposition:

  • Procedural decomposition means breaking a problem into a number

of sub-problems, so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided. Composition:

  • A composition abstraction means combining procedures to form compound

procedures.

  • Data abstraction composition means combining data objects to form compound data, such as the afore-mentioned tree data structure made of three arrays.

Automation

Automation means putting models (abstraction of real world objects/ phenomena) into action to solve problems. This is achieved by:

  • creating algorithms
  • implementing the algorithms in program code (instructions)
  • implementing the models in data structures
  • executing the code.