“The discipline of computing is the systematic study of the algorithmic processes that describe and transform information: their theory, analysis, design, efficiency, implementation, and application. The fundamental question underlying all of computing is, ‘What can be (efficiently) automated?’ ”
Denning et al., “Computing as a Discipline,” Communications of the ACM 32, 1 (Jan 1989) pp. 9–23.
a young discipline that arose from several more established fields (mathematics, science, engineering)
key words: algorithm, information (“informatics”)
term coined by George Forsythe, a numerical analyst and founding head (1965-1972) of Stanford Univ. CS Department
CS at Waterloo: formally founded in 1967 as the Department of Applied Analysis and Computer Science
Aspects of computer science
Design (from engineering)
establish requirements and specifications; create artefacts based on sound design principles
application: create hardware and software that is flexible, efficient, and usable
Theory (from mathematics)
develop model; prove theorems
application: analyze the efficiency of algorithms before implementation; discover limits to computation
Experimentation (from science)
form hypothesis, design experiments, and test predictions
application: simulate real-world situations; test effectiveness of programs whose behaviour cannot be modelled well
These aspects appear throughout CS, occasionally concurrently.
On 4 June 1996, the maiden flight of the Ariane 5 launcher ended in failure. Only about 40 seconds after initiation of the flight sequence, at an altitude of about 3700 m, the launcher veered off its flight path, broke up and exploded.
[Ariana 5 Flight 501 Failure, Report by the Inquiry Board, July 1996]
“At 36.7 seconds after H0 (approx. 30 seconds after lift-off) the computer within the back-up inertial reference system, which was working on stand-by for guidance and attitude control, became inoperative. This was caused by an internal variable related to the horizontal velocity of the launcher exceeding a limit which existed in the software of this computer.
“Approx. 0.05 seconds later the active inertial reference system, identical to the back-up system in hardware and software, failed for the same reason. Since the back-up inertial system was already inoperative, correct guidance and attitude information could no longer be obtained and loss of the mission was inevitable.
“As a result of its failure, the active inertial reference system transmitted essentially diagnostic information to the launcher's main computer, where it was interpreted as flight data and used for flight control calculations.
“On the basis of those calculations the main computer commanded the booster nozzles, and somewhat later the main engine nozzle also, to make a large correction for an attitude deviation that had not occurred.”
Ariane 5 (cont’d)
The inertial reference system of Ariane 5 is essentially common to a system which is presently flying on Ariane 4.
So, how did the failure happen?
“The part of the software which caused the interruption in the inertial system computers is used before launch to align the inertial reference system and, in Ariane 4, also to enable a rapid realignment of the system in case of a late hold in the countdown. This realignment function, which does not serve any purpose on Ariane 5, was nevertheless retained for commonality reasons and allowed, as in Ariane 4, to operate for approx. 40 seconds after lift-off.
“In Ariane 4 flights using the same type of inertial reference system there has been no such failure because the trajectory during the first 40 seconds of flight is such that the particular variable related to horizontal velocity cannot reach, with an adequate operational margin, a value beyond the limit present in the software.
“Ariane 5 has a high initial acceleration and a trajectory which leads to a build-up of horizontal velocity which is five times more rapid than for Ariane 4. The higher horizontal velocity of Ariane 5 generated, within the 40-second timeframe, the excessive value which caused the inertial system computers to cease operation.”
R5 … Identify all implicit assumptions made by the code and its justification documents on the values of quantities provided by the equipment. Check these assumptions against the restrictions on use of the equipment….
R11 Review the test coverage of existing equipment and extend it where it is deemed necessary.
R12 Give the justification documents the same attention as code. Improve the technique for keeping code and its justifications consistent….
Software in the real world
Support systems change
Intended applications change
Programs must survive these changes.
well-designed programs are adaptable
well-designed components can be reused
Guideline: Design and document software components as you would have others others design and document them for you.
The “Software Life Cycle”
Iterative model of software evolution
[Hume, West, Holt, and Barnard]
Note the cycle!
more accurate than including a maintenance box as part of the traditional “waterfall model”
Throughout the whole life cycle, documentation is critical: to capture rationale and communicate intent
“Fundamentally, computer science is a science of abstraction – creating the right model for a problem and devising the appropriate mechanizable techniques to solve it. Confronted with a problem, we must create an abstraction of that problem that can be represented and manipulated inside a computer. Through these manipulations, we try to find a solution to the original problem.”
A. V. Aho & J. D. Ullman, Foundations of Computer Science Object-oriented design concentrates on data abstraction:
identify entities occurring in problem domain
partition similar entities into sets
identify properties and operations common to all entities in each set
define interfaces to support operations on objects that belong to each entity set
define code modules to implement the entity sets
choose representations for objects
implement methods for constructing and manipulating objects conforming to the interfaces
Abstract Data Types
An abstract data type (ADT) includes
set of values (data space)
set of operators (methods)
whole numbers with addition, subtraction, absolute value, square root, ...
ordered sequences of characters with concatenate, substring, length, ...
sets of objects with union, intersection, size, ...
points in the plane with x-coordinate, distance, ...
allows us to define further types tailored to applications’ needs
independent of programming language
also applicable to procedural programming languages
independent of data representation and operator implementation
Use the principle of information hiding
coined by David Parnas in 1972
“Every module [should be] characterized by its knowledge of a design decision which it hides from all others.”
particularly important to hide decisions that are likely to change (when they are found to be wrong or the environment has changed)
benefits software maintenance and reuse
collection of n objects indexed from 1 to n
1, i2, i3, … , in>
can create an empty list
can get the number of items
can access element at an arbitrary index of List s
can insert new elements
can remove elements
s.remove(index) or s.removeAll()
special check for empty List
s.isEmpty() (s.size() == 0)
Assertions in programs
An assertion is:
a logical claim about the state of a program
located at a specific point in the program
assumed true whenever that point is reached
Example: 0 i < a.length
precise, concise, and convincing documentation
can be used to
guide the creation of a program (design)
reason formally about a program and verify its correctness (theory)
drive formulation of test cases and debugging strategy (experiment)
Properties of assertions
snapshots of what is claimed to be true during execution at some specific point in the code
noteworthy static statements
not descriptions of action or change
Specification by assertions
preconditions: assertions that must be true when the method is invoked
p Specify the syntax and semantics of each method: