Introduction to C++ Programming I
Ian Aitchison and Peter King August 1997

Contents
1 The Computer 1.1 Central Processing Unit . . . . . . . . . . . . . . . . . . . 1.2 Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Main memory . . . . . . . . . . . . . . . . . . . . . 1.2.2 External Memory . . . . . . . . . . . . . . . . . . . 1.3 Input/Output Devices . . . . . . . . . . . . . . . . . . . . 1.4 The system bus . . . . . . . . . . . . . . . . . . . . . . . . 1.5 More about memory and information representation . . . 1.5.1 Representation of information in external memory 1.6 The execution cycle . . . . . . . . . . . . . . . . . . . . . 1.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.8 Multiple Choice Questions . . . . . . . . . . . . . . . . . . 1.9 Review Questions . . . . . . . . . . . . . . . . . . . . . . . 2 Programming Languages 2.1 Assembly Language . . . 2.2 High level Languages . . . 2.3 Summary . . . . . . . . . 2.4 Multiple Choice Questions 11 13 13 14 14 15 16 16 17 17 18 19 19 20 21 22 23 23

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

3 Operating Systems 25 3.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2 Multiple Choice Questions . . . . . . . . . . . . . . . . . . . . 27 4 Preparing a Computer Program 29 4.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.2 Multiple Choice Questions . . . . . . . . . . . . . . . . . . . . 31 4.3 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . 31 5 Algorithms 5.1 Describing an Algorithm . . . . . . . . . . . 5.2 Statements required to describe algorithms 5.3 Verifying the correctness of the algorithm . 5.3.1 Desk-checking . . . . . . . . . . . . . 1 32 33 35 37 38

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

5.4 5.5 5.6 5.7 5.8

Series Minimum and Maximum Algorithm Summary . . . . . . . . . . . . . . . . . . Multiple Choice Questions . . . . . . . . . Review Questions . . . . . . . . . . . . . . Exercises . . . . . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

38 41 42 42 43 45 47 48 49 51 52 52 55 55 56 57 58 59 61 62 62 62 63 64 64 65 66 67 67 68 69 71 72 73 74 75 75 77 77 77

6 A simple C++ program 6.1 Variables . . . . . . . . . . . . . . . . . . . 6.1.1 Reserved words . . . . . . . . . . . . 6.2 Declaration of variables . . . . . . . . . . . 6.3 Constants and the declaration of constants 6.4 General form of a C++ Program . . . . . . 6.5 Input and Output . . . . . . . . . . . . . . 6.6 Programming Style . . . . . . . . . . . . . . 6.7 Summary . . . . . . . . . . . . . . . . . . . 6.8 Multiple Choice Questions . . . . . . . . . . 6.9 Review questions . . . . . . . . . . . . . . . 6.10 Exercises . . . . . . . . . . . . . . . . . . . 7 The 7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 7.9

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

Assignment statement Priority of Operators . . . . . . . . . . . . . . . Examples of Arithmetic Expressions . . . . . . Type Conversions . . . . . . . . . . . . . . . . . Example Program: Temperature Conversion . . Example Program: Pence to Pounds and Pence Summary . . . . . . . . . . . . . . . . . . . . . Multiple Choice Questions . . . . . . . . . . . . Review questions . . . . . . . . . . . . . . . . . Exercises . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

8 Further Assignment Statements & Control of Output 8.1 Increment and Decrement Operators . . . . . . . . . . . 8.2 Specialised Assignment Statements . . . . . . . . . . . . 8.3 Formatting of output . . . . . . . . . . . . . . . . . . . . 8.4 Example Program: Tabulation of sin function . . . . . . 8.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . 8.6 Multiple Choice Questions . . . . . . . . . . . . . . . . . 8.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Introduction to structured design 9.1 Conditional Control Structures . 9.2 Summary . . . . . . . . . . . . . 9.3 Review Questions . . . . . . . . . 9.4 Exercises . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

2

10 Conditions 10.1 Relational Expressions . . . . . . . . 10.2 Examples using Relational Operators 10.3 Logical Expressions . . . . . . . . . . 10.4 Examples using logical operators . . 10.5 Summary . . . . . . . . . . . . . . . 10.6 Multiple Choice Questions . . . . . . 10.7 Review Questions . . . . . . . . . . . 11 The 11.1 11.2 11.3 11.4 12 The 12.1 12.2 12.3 12.4 12.5 12.6 12.7 12.8 if statement Examples of if statements Summary . . . . . . . . . . Multiple Choice Questions . Exercises . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

79 79 79 80 81 82 82 83 85 85 86 87 88 89 90 90 91 93 94 94 95 95

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

if-else Statement Examples of if-else statements . . . . . . . . . . . Example Program: Wages Calculation . . . . . . . . Example Program: Pythagorean Triples . . . . . . . Example Program: Area and Perimeter of Rectangle Summary . . . . . . . . . . . . . . . . . . . . . . . . Multiple Choice Questions . . . . . . . . . . . . . . . Review Questions . . . . . . . . . . . . . . . . . . . . Exercises . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

13 Nested if and if-else statements 13.1 Summary . . . . . . . . . . . . . 13.2 Multiple Choice Questions . . . . 13.3 Review Questions . . . . . . . . . 13.4 Exercises . . . . . . . . . . . . . 14 The 14.1 14.2 14.3 14.4 14.5 switch statement Examples of switch statements Summary . . . . . . . . . . . . Multiple Choice Questions . . . Review Questions . . . . . . . . Exercises . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

97 . 99 . 99 . 99 . 100 101 . 102 . 104 . 104 . 104 . 105 106 . 106 . 106 . 109 . 110 . 112

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

15 Further Structured Design 15.1 Repetition Control Structures . . . . . . . . . 15.2 Example One: Using a while loop . . . . . . 15.3 Example Two: Using a while loop . . . . . . 15.4 Other forms of Repetition Control Structures 15.5 Summary . . . . . . . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

3

15.6 Review questions . . . . . . . . . . . . . . . . . . . . . . . . . 112 15.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 16 The 16.1 16.2 16.3 16.4 while statement 114 Example while loop: Printing integers . . . . . . . . . . . . . 115 Example while loop: Summing Arithmetic Progression . . . 115 Example while loop: Table of sine function . . . . . . . . . . 116 Example while loop: Average, Minimum and Maximum Calculation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 16.5 Example Program: Student mark processing . . . . . . . . . . 119 16.6 Example Program: Iterative evaluation of a square root . . . 122 16.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 16.8 Multiple Choice Questions . . . . . . . . . . . . . . . . . . . . 125 16.9 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . 126 16.10Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 do-while statement Example Program: Sum of Arithmetic Progression Example Program: Valid Input Checking . . . . . Example Program: Student Mark Processing (2) . Summary . . . . . . . . . . . . . . . . . . . . . . . Multiple Choice Questions . . . . . . . . . . . . . . Review Questions . . . . . . . . . . . . . . . . . . . Exercises . . . . . . . . . . . . . . . . . . . . . . . 129 130 130 131 132 132 133 134 135 136 136 137 138 140 140 141 142 144 144 145 146 148 149 149

17 The 17.1 17.2 17.3 17.4 17.5 17.6 17.7 18 The 18.1 18.2 18.3 18.4 18.5 18.6 18.7 18.8

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

for statement Example for statement: Print 10 integers . . . . . . . Example for statement: Print table of sine function . Example Program: Student Mark Processing (3) . . . Example Program: Generation of Pythagorean Triples Summary . . . . . . . . . . . . . . . . . . . . . . . . . Multiple Choice Questions . . . . . . . . . . . . . . . . Review Questions . . . . . . . . . . . . . . . . . . . . . Exercises . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

19 Streams and External Files 19.1 Streams . . . . . . . . . . . . . . . . . 19.2 Connecting Streams to External Files 19.3 Testing for end-of-file . . . . . . . . . . 19.4 Summary . . . . . . . . . . . . . . . . 19.5 Review Questions . . . . . . . . . . . . 19.6 Exercises . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

4

20 Top-down design using Functions 20.1 The need for functions . . . . . . . . 20.2 The mathematical function library in 20.3 Summary . . . . . . . . . . . . . . . 20.4 Review Questions . . . . . . . . . . . 20.5 Exercises . . . . . . . . . . . . . . .

. . . . C++ . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

150 151 152 153 154 154 155 156 158 160 162 162 163 164 164 166 167 167 169 173 174 174 176 177 177 178 180 180 182 184 186 187 187 189 190 191

21 Introduction to User-defined functions in C++ 21.1 Functions with no parameters . . . . . . . . . . . 21.2 Functions with parameters and no return value . 21.3 Functions that return values . . . . . . . . . . . . 21.4 Example function: sum of squares of integers . . 21.5 Example Function: Raising to the power . . . . . 21.6 Call-by-value parameters . . . . . . . . . . . . . . 21.7 Summary . . . . . . . . . . . . . . . . . . . . . . 21.8 Review Questions . . . . . . . . . . . . . . . . . . 21.9 Exercises . . . . . . . . . . . . . . . . . . . . . . 22 Further User-defined functions in C++ 22.1 Call-by-reference parameters . . . . . . 22.2 Example Program: Invoice Processing . 22.3 Summary . . . . . . . . . . . . . . . . . 22.4 Review Questions . . . . . . . . . . . . . 22.5 Exercises . . . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

23 Arrays 23.1 Arrays in C++ . . . . . . . . . . . . . . . . . 23.1.1 Declaration of Arrays . . . . . . . . . 23.1.2 Accessing Array Elements . . . . . . . 23.1.3 Initialisation of arrays . . . . . . . . . 23.2 Example Program: Printing Outliers in Data 23.3 Example Program: Test of Random Numbers 23.4 Arrays as parameters of functions . . . . . . . 23.5 Strings in C++ . . . . . . . . . . . . . . . . . 23.5.1 String Output . . . . . . . . . . . . . 23.5.2 String Input . . . . . . . . . . . . . . . 23.6 Summary . . . . . . . . . . . . . . . . . . . . 23.7 Review Questions . . . . . . . . . . . . . . . . 23.8 Exercises . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

5

About the course
Welcome to Heriot-Watt University Introduction to Computing I course. This course is being provided for students taking the Certificate in Science of Aberdeen and Heriot-Watt Universities. It is being delivered by way of the World Wide Web, however all students will also receive the entire course in a printed format. The course is arranged in a series of Lessons. As well as new material to learn, each Lesson contains review questions, multiple choice questions, and programming exercises. The review questions are designed to get you to think about the contents of the Lesson. These review questions should be straightforward; if the answer is not obvious, reread the Lesson. The multiple choice questions can be answered on-line when you are using the World Wide Web; feedback is given if you choose the wrong answers. The programming exercises are an essential part of the course. Computer programming is a practical subject, without practice no progress will be made. There will be some assessed coursework, this may be submitted by electronic mail. Electronic mail will also be used to provide help with problems.

Course contents
This course is intended as a first introduction to programming computers using the C++ programming language. It is not assumed that the student has done any programming before hence this course is not comprehensive and does not cover all of C++. In particular it does not cover any of the object-oriented features of C++, these are introduced in the following course (Introduction to Computing II). Because this is a first programming course emphasis is placed on the design of programs in a language-independent fashion. A brief introduction to computers is also given. The lessons of the course may be split into groups as follows: 1. About the computer and computer systems. • Lesson 1 - The Computer. Covers the Central processor, memory, information representation and the operation cycle of the computer. 6

• Lesson 2 - Programming Languages. Covers the various levels of Programming Languages. • Lesson 3 - Operating Systems. Covers the purpose of Operating systems and the major types. • Lesson 4 - Preparing a Computer Program. Covers the steps that are carried out in going from a problem specification to having a well-tested and reliable program to solve the problem. 2. About the design of programs. • Lesson 5 - Algorithms. The basic constructs used in designing programs. Sequence, selection and repetition. • Lesson 9 - Introduction to Structured Design. Top-down design of algorithms using sequence and selection only. • Lesson 15 - Further Structured Design. Top-down design of algorithms using repetition. • Lesson 20 - Top-down design using Functions. An introduction to problem-solving by splitting the problem into sub-problems whose solutions are implemented as functions. 3. About C++ • Lesson 6 - A simple C++ program. Looks at a simple C++ program and identifies features. Covers simple ideas about variables and their declaration and input and output. • Lesson 7 - The Assignment statement. How values are assigned to variables. • Lesson 8 - Further Assignment Statements & Control of Output. More forms of assignment statement and simple formatting of output. • Lesson 10 - Conditions. How expressions that can be true or false are written in C++. • Lesson 11 - The if statement. How conditional execution of a statement is carried out. • Lesson 12 - The if-else statement. How a choice can be made between which of two statements to execute. • Lesson 13 - Nested if and if-else statements. How multi-choice decisions can be made. • Lesson 14 - The switch statement. An alternative way to implement multi-choice conditions. • Lesson 16 - The while statement. The basic way to carry out repetition. 7

• Lesson 17 - The do-while statement. An alternative way to carry out repetition. • Lesson 18 - The for statement. Repetition a set number of times or as a control loop variable takes a set of values. • Lesson 19 - Streams and External Files. How to input and output data from and to external files. • Lesson 21 - An introduction to User-defined functions in C++. How to design your own functions. • Lesson 22 - Further User-defined functions. Returning information by parameters. • Lesson 23 - Arrays. How to work with large collections of indexed data. Note that there is also a document ‘The Computer Exercises’ which gives some help in using Windows and the Borland C++ compilers.

Suggested study timetable
It is suggested that you should cover the contents of the course in about 13/14 weeks. The lessons are not equal in size or in the difficulty of their content. The following timetable is suggested. Week 1 Try to cover most of the material in Lessons 1 to 4 during this first week. This is mainly background material for those who have not had much contact with computers before but some (or all) of it will probably be familiar to most people taking the course. During this first week try to familiarise yourself with the computer system you are going to use so that you are ready to start programming as soon as possible. Included with the course notes (The Computer Exercises) is a document about using the Borland C++ compilers, check over this and go through the suggested steps in compiling a small supplied C++ program. This activity may well expand into week 2. Week 2 Read Lesson 5 on Algorithms. Don’t worry if you find it difficult to make up your own algorithms at this stage, but do make an attempt. You’ll continue to get practice at this as long as you program! Also start looking at Lesson 6 on simple programs and their features. Implement your solutions to the exercises on the computer. Week 3 Cover Lessons 7 and 8 on assignment and implement the exercises on simple calculation type programs. Week 4 Now study Lesson 9 on Algorithms with simple selection. Read Lesson 10 on how conditional expressions are constructed in C++. 8

Week 5 Study Lessons 11 and 12 on if and if-else statements and implement the exercise on programs with simple selection. Week 6 Continue the study of selection mechanisms with Lessons 13 and 14 on nested if and if-else statements and the switch statement. The switch statement is not as fundamental as the others so spend less time on it than the other selection mechanisms. Week 7 Study Lesson 15 on repetition constructs and practice designing algorithms using repetition. Commence Lesson 16 on the while statement. Week 8 Continue Lesson 16 on the while statement. Also cover Lesson 17 on the do-while statement this week. Do not spend so much time on it as on the more fundamental while statement. Week 9 Cover Lesson 18 on the for statement. This statement is used frequently and so is an important statement. Have a look at Lesson 19 on Streams and Files so that you can use an External file in the last assignment. Week 10 Study Lesson 20 on structured design using functions. This is a very important Lesson. If you have time start on Lesson 21 on how to construct C++ functions. Week 11 Carry on with Lesson 21 on user-defined functions. Continue on to Lesson 22. In carrying out the exercises in these Lessons you will also get further practice on using the conditional and repetition control structures. Week 12 Study Lesson 23 which introduces the concept of arrays. Again this is an important concept in programming. The exercises for this chapter will provide you with more practice in the use of control structures and functions. Week 13 Finish off the course and start revision.

Assessment
There will be two class assignments to carry out. One will be given out which requires that you know the material up to and including Lesson 12. The other will require that you know the material up to and including Lesson 20 (19 is not needed for the assignment). The first assignment will be worth 10% in the final assessment and the second assignment will be worth 15% in the final assessment. The remaining 75% will come from the class examination. Further information will be available on the World Wide Web version of the course. 9

Accessing the course on the World Wide Web
The course, and its successor Introduction to Computing II, are available on the World Wide Web (WWW). You are assumed to know how to connect to WWW. The course has been developed using Netscape as the browser, but it should be possible to access it equally well with Microsoft’s Internet Navigator, or with Mosaic. To access the course, use your browser to open the URL http://www.cee.hw.ac.uk/ This will present you with a page about the Department of Computing and Electrical Engineering at Heriot-Watt University. Follow the link labelled Distance Learning Courses The page loaded will give general information about the courses. There will also be reminders about approaching deadlines for coursework, and notification of any corrections to parts of the course. (Any corrections will have been made in the WWW version of the course, but this will enable you to annotate your printed version of the notes.) You are advised to always enter the course in this fashion. Saving bookmarks with your browser may cause problems if any corrections cause extra sections or questions to be added to the course. Coursework should be submitted using electronic mail. Send any files requested to pjbk@cee.hw.ac.uk, with clear indications of which assignment is being submitted within the file.

Getting Help
Although the notes are intended to be comprehensive, there will undoubtedly be times when you need help. There are two mechanisms for this. An electronic mailing list has been set up at Heriot-Watt University which copies messages submitted to it to all members of the course. The course organisers and teachers receive all messages sent to this list. All students should join this mailing list, and use it to replace the discussion that would normally take place in a classroom. In order to join the mailing list, send an electronic mail message to majordomo@cee.hw.ac.uk with the following contents: subscribe pathways Once you have joined the list, messages to the list are sent as ordinary electronic mail addressed to pathways@cee.hw.ac.uk If your problems are of a more individual nature, you may prefer to send them to the course teacher only, in which case an email message should be addressed to pjbk@cee.hw.ac.uk 10

Lesson 1

The Computer
Before considering the programming of a computer a brief overview of the basic structure of a Computer in terms of its main components is given. Every Computer has the following general structure:

11

12

1.1

Central Processing Unit

The Central Processing Unit (CPU) performs the actual processing of data. The data it processes is obtained, via the system bus, from the main memory. Results from the CPU are then sent back to main memory via the system bus. In addition to computation the CPU controls and co-ordinates the operation of the other major components. The CPU has two main components, namely: 1. The Control Unit — controls the fetching of instructions from the main memory and the subsequent execution of these instructions. Among other tasks carried out are the control of input and output devices and the passing of data to the Arithmetic/Logical Unit for computation. 2. The Arithmetic/Logical Unit (ALU) — carries out arithmetic operations on integer (whole number) and real (with a decimal point) operands. It can also perform simple logical tests for equality and greater than and less than between operands. It is worth noting here that the only operations that the CPU can carry out are simple arithmetic operations, comparisons between the result of a calculation and other values, and the selection of the next instruction for processing. All the rest of the apparently limitless things a computer can do are built on this very primitive base by programming! Modern CPUs are very fast. At the time of writing, the CPU of a typical PC is capable of executing many tens of millions of instructions per second.

1.2

Memory

The memory of a computer can hold program instructions, data values, and the intermediate results of calculations. All the information in memory is encoded in fixed size cells called bytes. A byte can hold a small amount of information, such as a single character or a numeric value between 0 and 255. The CPU will perform its operations on groups of one, two, four, or eight bytes, depending on the interpretation being placed on the data, and the operations required. There are two main categories of memory, characterised by the time it takes to access the information stored there, the number of bytes which are accessed by a single operation, and the total number of bytes which can be stored. Main Memory is the working memory of the CPU, with fast access and limited numbers of bytes being transferred. External memory 13

is for the long term storage of information. Data from external memory will be transferred to the main memory before the CPU can operate on it. Access to the external memory is much slower, and usually involves groups of several hundred bytes.

1.2.1

Main memory

The main memory of the computer is also known as RAM, standing for Random Access Memory. It is constructed from integrated circuits and needs to have electrical power in order to maintain its information. When power is lost, the information is lost too! It can be directly accessed by the CPU. The access time to read or write any particular byte are independent of whereabouts in the memory that byte is, and currently is approximately 50 nanoseconds (a thousand millionth of a second). This is broadly comparable with the speed at which the CPU will need to access data. Main memory is expensive compared to external memory so it has limited capacity. The capacity available for a given price is increasing all the time. For example many home Personal Computers now have a capacity of 16 megabytes (million bytes), while 64 megabytes is commonplace on commercial workstations. The CPU will normally transfer data to and from the main memory in groups of two, four or eight bytes, even if the operation it is undertaking only requires a single byte.

1.2.2

External Memory

External memory which is sometimes called backing store or secondary memory, allows the permanent storage of large quantities of data. Some method of magnetic recording on magnetic disks or tapes is most commonly used. More recently optical methods which rely upon marks etched by a laser beam on the surface of a disc (CD-ROM) have become popular, although they remain more expensive than magnetic media. The capacity of external memory is high, usually measured in hundreds of megabytes or even in gigabytes (thousand million bytes) at present. External memory has the important property that the information stored is not lost when the computer is switched off. The most common form of external memory is a hard disc which is permanently installed in the computer and will typically have a capacity of hundreds of megabytes. A hard disc is a flat, circular oxide-coated disc which rotates continuously. Information is recorded on the disc by magnetising spots of the oxide coating on concentric circular tracks. An access arm in the disc drive positions a read/write head over the appropriate track to read and write data from and to the track. This means that before accessing or modifying data the read/write head must be positioned over the correct track. This time is called the seek time and is measured in milliseconds.

14

There is also a small delay waiting for the appropriate section of the track to rotate under the head. This latency is much smaller than the seek time. Once the correct section of the track is under the head, successive bytes of information can be transferred to the main memory at rates of several megabytes per second. This discrepancy between the speed of access to the first byte required, and subsequent bytes on the same track means that it is not economic to transfer small numbers of bytes. Transfers are usually of blocks of several hundred bytes or even more. Notice that the access time to data stored in secondary storage will depend on its location. The hard disc will hold all the software that is required to run the computer, from the operating system to packages like word-processing and spreadsheet programs. All the user’s data and programs will also be stored on the hard disc. In addition most computers have some form of removable storage device which can be used to save copies of important files etc. The most common device for this purpose is a floppy disc which has a very limited capacity. Various magnetic tape devices can be used for storing larger quantities of data and more recently removable optical discs have been used. It is important to note that the CPU can only directly access data that is in main memory. To process data that resides in external memory the CPU must first transfer it to main memory. Accessing external memory to find the appropriate data is slow (milliseconds) in relation to CPU speeds but the rate of transfer of data to main memory is reasonably fast once it has been located.

1.3

Input/Output Devices

When using a computer the text of programs, commands to the computer and data for processing have to be entered. Also information has to be returned from the computer to the user. This interaction requires the use of input and output devices. The most common input devices used by the computer are the keyboard and the mouse. The keyboard allows the entry of textual information while the mouse allows the selection of a point on the screen by moving a screen cursor to the point and pressing a mouse button. Using the mouse in this way allows the selection from menus on the screen etc. and is the basic method of communicating with many current computing systems. Alternative devices to the mouse are tracker balls, light pens and touch sensitive screens. The most common output device is a monitor which is usually a Cathode Ray Tube device which can display text and graphics. If hard-copy output is required then some form of printer is used.

15

1.4

The system bus

All communication between the individual major components is via the system bus. The bus is merely a cable which is capable of carrying signals representing data from one place to another. The bus within a particular individual computer may be specific to that computer or may (increasingly) be an industry-standard bus. If it is an industry standard bus then there are advantages in that it may be easy to upgrade the computer by buying a component from an independent manufacturer which can plug directly into the system bus. For example most modern Personal Computers use the PCI bus. When data must be sent from memory to a printer then it will be sent via the system bus. The control signals that are necessary to access memory and to activate the printer are also sent by the CPU via the system bus.

1.5

More about memory and information representation

All information inside the computer and on external storage devices is represented in a form related to the Binary number system. Binary is a number system which uses the base 2 instead of the base 10 decimal system that is used in normal life. In the decimal system a positional number system is used which allows all numbers to be expressed using only the digits 0–9. Successive digits from the right represent the number of the corresponding power of 10. Thus 123 in decimal is 1 × 102 + 2 × 101 + 3 × 100 that is, one hundred, plus two tens, plus three units. Similarly the binary number system builds all numbers from the bits 0 and 1, and powers of 2. 101 in the binary number system represents the number with value 1 × 22 + 0 × 21 + 1 × 20 which is of course the decimal number 5. Using the binary system allows all computation inside the computer to take place using cheap two-state electronic devices. Modern computers organise information into small units called bytes which hold eight bits, each bit representing a 0 or a 1. Each byte may hold a single character of text or a small integer. Larger numbers, computer instructions and character strings occupy several bytes. The main memory can be thought of as a series of bytes numbered from 0, 1, 2, 3, . . . upwards, each byte containing a pattern of eight bits which can be accessed by the CPU when it supplies the number, or Address, of 16

the byte required. For example consider the section of memory illustrated below: Address 3168 3167 3166 Contents 10110111 01000111 01010101

The byte with the address 3167 contains the binary pattern 01000111. Depending on circumstances the CPU may interpret this as an instruction, as a number (or part of a number) or as a character. This pattern can represent the character G in the ASCII character code that is used almost universally now or it could represent the decimal number 71. It is important to keep a clear distinction in your mind of the difference between the address of a memory location and the contents of that memory location.

1.5.1

Representation of information in external memory

Information on external memory is organised into files, each file containing some related information. For example a file could hold the text of a document, a computer program, a set of experimental results etc. Just as in main memory the information in a file is represented as a collection of bytes.

1.6

The execution cycle

When a computer obeys the instructions in a computer program it is said to be running or executing the program. Before a computer can execute a computer program the program must be resident in memory. The program must occupy a set of consecutive bytes in memory and must be written in the internal machine language for the computer. Each CPU has its own machine language which means that before a program can be executed on another CPU it has to be re-written in the internal machine language of the other CPU. The concept that the program to be executed is stored in the computer memory is an important one. This is what makes the computer such a general-purpose problem-solving machine — merely by changing the program stored in memory the computer can be used to carry out an entirely different task. Once the program is loaded into memory then the following sequence is carried out: set instruction address to the address of 17

the first instruction while program not finished { fetch instruction from current instruction address update current instruction address execute the fetched instruction } This sequence is usually called the fetch-execute cycle.

1.7

Summary

• A computer consists of a Central Processing Unit(CPU), memory and various devices which can be categorised as Input/Output Devices. Information is communicated between these separate units by the Systems Bus. • The Central Processing Unit (CPU) consists of a Control Unit and an Arithmetic/Logic Unit (ALU). The control unit controls the operation of the peripheral devices and the transfer of information between the units that make up the computer. The Arithmetic/Logic Unit performs calculation. • The memory of the computer is split into main memory and external memory. • Main memory is fast and limited in capacity. The CPU can only directly access information in main memory. Main memory cannot retain information when the computer is switched of. Main memory consists of a series of numbered locations called bytes, each byte being eight bits. The number associated with a byte is the address of the byte. • Secondary memory is slow and virtually unlimited in capacity. It retains information when the computer is switched off. Information on external memory can only be accessed by the CPU if it is first transferred to main memory. • The internal representation of information in the computer and on external memory is in terms of the Binary system using only the basic symbols 0 and 1. • Programs to be executed by the computer are placed in main memory and the CPU fetches each instruction in turn from memory and executes it.

18

• Each type of CPU has its own machine language, the set of instructions it can obey.

1.8

Multiple Choice Questions
(a) (b) (c) (d) CPU, CD-rom, mouse, keyboard, sound card Memory, Video Card, Monitor, Software, Hardware. Modem, Keyboard, Word Processor, Printer, Screen. CPU, memory, system bus, input, output

1. What are the five main components of a computer system?

2. How do the main components of the computer communicate with each other? (a) (b) (c) (d) system bus memory keyboard monitor

1.9

Review Questions

1. What are the tasks carried out by the Central Processing Unit 2. What are the major differences between main memory and external memory? 3. What is stored in main memory? What is stored in external memory? 4. How is information represented inside computer systems? 5. In the following diagram of memory what are the contents of the memory location with the address 98? What is the address of the memory location whose contents are 10100101? What could these contents represent? 100 99 98 00010010 10100101 11011101

6. What has to be done before a program can be executed in a computer? How is the program executed by the CPU? 7. What benefit derives from the ‘stored program concept’ ?

19

Lesson 2

Programming Languages
As noted in section 1.6 all computers have an internal machine language which they execute directly. This language is coded in a binary representation and is very tedious to write. Most instructions will consist of an operation code part and an address part. The operation code indicates which operation is to be carried out while the address part of the instruction indicates which memory location is to be used as the operand of the instruction. For example in a hypothetical computer successive bytes of a program may contain: operation code 00010101 00010111 00010110 address 10100001 10100010 10100011 meaning load c(129) into accumulator add c(130) to accumulator store c(accumulator) in location 131

where c( ) means ‘the contents of’ and the accumulator is a special register in the CPU. This sequence of code then adds the contents of location 130 to the contents of the accumulator, which has been previously loaded with the contents of location 129, and then stores the result in location 131. Most computers have no way of deciding whether a particular bit pattern is supposed to represent data or an instruction. Programmers using machine language have to keep careful track of which locations they are using to store data, and which locations are to form the executable program. Programming errors which lead to instructions being overwritten with data, or erroneous programs which try to execute part of their data are very difficult to correct. However the ability to interpret the same bit pattern as both an instruction and as data is a very powerful feature; it allows programs to generate other programs and have them executed.

20

2.1

Assembly Language

The bookkeeping involved in machine language programming is very tedious. If a programmer is modifying a program and decides to insert an extra data item, the addresses of other data items may be changed. The programmer will have to carefully examine the whole program deciding which bit patterns represent the addresses which have changed, and modify them. Human beings are notoriously bad at simple repetitive tasks; computers thrive on them. Assembly languages are a more human friendly form of machine language. Machine language commands are replaced by mnemonic commands on a one-to-one basis. The assembler program takes care of converting from the mnemonic to the corresponding machine language code. The programmer can also use symbolic addresses for data items. The assembler will assign machine addresses and ensure that distinct data items do not overlap in storage, a depressingly common occurrence in machine language programs. For example the short section of program above might be written in assembly language as: operation code LOAD ADD STORE address A B C

Obviously this leaves less scope for error but since the computer does not directly understand assembly language this has to be translated into machine language by a program called an assembler. The assembler replaces the mnemonic operation codes such as ADD with the corresponding binary codes and allocates memory addresses for all the symbolic variables the programmer uses. It is responsible for associating the symbol A, B, and C with an addresses, and ensuring that they are all distinct. Thus by making the process of programming easier for the human being another level of processing for the computer has been introduced. Assembly languages are still used in some time-critical programs since they give the programmer very precise control of what exactly happens inside the computer. Assembly languages still require that the programmer should have a good knowledge of the internal structure of the computer. For example, different ADD instructions will be needed for different types of data item. Assembly languages are still machine specific and hence the program will have to be re-written if it is to be implemented on another type of computer.

21

2.2

High level Languages

Very early in the development of computers attempts were made to make programming easier by reducing the amount of knowledge of the internal workings of the computer that was needed to write programs. If programs could be presented in a language that was more familiar to the person solving the problem, then fewer mistakes would be made. High-level programming languages allow the specification of a problem solution in terms closer to those used by human beings. These languages were designed to make programming far easier, less error-prone and to remove the programmer from having to know the details of the internal structure of a particular computer. These high-level languages were much closer to human language. One of the first of these languages was Fortran II which was introduced in about 1958. In Fortran II our program above would be written as: C = A + B which is obviously much more readable, quicker to write and less error-prone. As with assembly languages the computer does not understand these highlevel languages directly and hence they have to be processed by passing them through a program called a compiler which translates them into internal machine language before they can be executed. Another advantage accrues from the use of high-level languages if the languages are standardised by some international body. Then each manufacturer produces a compiler to compile programs that conform to the standard into their own internal machine language. Then it should be easy to take a program which conforms to the standard and implement it on many different computers merely by re-compiling it on the appropriate computer. This great advantage of portability of programs has been achieved for several high-level languages and it is now possible to move programs from one computer to another without too much difficulty. Unfortunately many compiler writers add new features of their own which means that if a programmer uses these features then their program becomes non-portable. It is well worth becoming familiar with the standard and writing programs which obey it, so that your programs are more likely to be portable. As with assembly language human time is saved at the expense of the compilation time required to translate the program to internal machine language. The compilation time used in the computer is trivial compared with the human time saved, typically seconds as compared with weeks. Many high level languages have appeared since Fortran II (and many have also disappeared!), among the most widely used have been:

22

COBOL FORTRAN PASCAL C & C++ PROLOG JAVA

Business applications Engineering & Scientific Applications General use and as a teaching tool General Purpose - currently most popular Artificial Intelligence General Purpose, gaining popularity rapidly,

All these languages are available on a large variety of computers.

2.3

Summary

• Each CPU has its own internal machine language. Programming at this internal machine level is usually carried out in Assembly language which is machine specific and relates on an instruction to instruction basis to the internal machine language. • High-level languages are translated by a compiler program into internal machine language. The compiled code is linked with any system libraries required and the final program loaded into memory before execution of the program can take place. • If an agreed standard is produced for a high-level language then any program which conforms to the standard should be able to run on any computer after compiling it with a machine-specific compiler. This gives the advantage of portability of programs.

2.4

Multiple Choice Questions

1. What is the only language that a computer understands directly? (a) English, as spoken in Boston, Mass. (b) BASIC, the Beginners’ All-purpose Symbolic Instruction Code (c) machine language, different for every type of CPU 2. What are the three main types of computer programming languages? (a) machine language, assembly language, high level language (b) imperative language, functional language, declarative language (c) COBOL, Fortran-77, C++ 3. From the point of view of the programmer what are the major advantages of using a high-level language rather than internal machine code or assembler language? 23

(a) Program portability (b) Easy development (c) Efficiency

24

Lesson 3

Operating Systems
The Operating System of a computer is a large program which manages the overall operation of the computer system. On a simple one-user computer the Operating System will: 1. Provide an interface to allow the user to communicate with the computer. This interface may be a text-oriented interface where the user types commands in response to a prompt from the computer or may be a mouse-driven Windows operating system. 2. Control the various peripherals e.g. Keyboard, Video Display Unit (VDU), Printer etc. using special programs called Device Drivers. 3. Manage the user’s files, keeping track of their positions on disk, updating them after user makes changes to them etc. An important facility that the Operating System must supply in this respect is an Editor which allows users to edit their files. 4. Provide system facilities, e.g. Compilers to translate from high-level programming languages used by the user to the internal machine language the computer uses. Because of the disparity in speed between input/output devices (and the human entering data) and the CPU most modern operating systems will allow Multi-tasking to take place. Thus while the Computer is held up waiting for input from one program the operating system will transfer control to another program which can execute until it, in turn, is held up. Multi-tasking may take place in a stand-alone computer (for example using an operating system such as Windows 95 on a PC) and allow the user to simultaneously use several different programs simultaneously. For example a user may be running a large computational task in the background while using a word-processor package to write a report. It is now common for computers to be linked together in networks. The network may consist of many dumb terminals, Personal Computers 25

and workstations linked together with perhaps several larger, more powerful computers which provide a large amount of computer power and file storage facilities to the network. This allows many people access to computing facilities and access to common data-bases, electronic mail facilities etc. Networks may be local to a building or a small area (Local Area Network (LAN)) or connect individual networks across the country or world (Wide Area Network (WAN)). A particular form of network operating system is a Timesharing operating system. Many large modern computers are set up to serve many simultaneous users by means of a time-sharing system. Each user has a direct connection to a powerful central computer, normally using a Visual Display Unit (VDU) which has a keyboard (and often a mouse) for user input and a screen for feedback from the computer to the user. There may be several hundred simultaneous users of a large computing system. Computing is Interactive in that the time from a user entering a command until a response is obtained will typically be a few seconds or less. The Operating System will cycle in turn through each connected terminal and if the terminal is awaiting computation will give it a Time-slice of dedicated CPU time. This process is continuous thus each program receives as many time-slices as it requires until it terminates and is removed from the list of programs awaiting completion. In a system with multiple users the operating system must also carry out other tasks such as: 1. Validating the user’s rights to use the system 2. Allocating memory and processor time to individual programs 3. Maintaining the security of each user’s files and program execution In a time-sharing system the processing power is contained in a central machine. Users access this central machine from a non-intelligent terminal that can do no processing itself. The advent of cheap powerful workstations has lead to the distribution of computer power around the network. A distributed computer system consists of a central processor with a large amount of disk storage and powerful input/output facilities connected to a network of machines, each with its own main memory and processor. The central processor (or Server) provides storage for all system files and user files. Each computing node in the network downloads any files and system facilities it requires from the server and then carries out all computation internally. Any changes to files or new files generated have to be sent by the network to the server. To make it easier to find a particular file it is usual to collect all related files into a separate directory. Each user will be allocated a certain amount of space on the external memory, this space will be set up as a single directory called the user’s home directory. 26

The user can further split this space into various other directories. For example a lecturer writing a course may well set up a directory to contain all the files relevant to the course. Within this directory it is best to organise the files into groups by setting up various sub-directories, a sub-directory to hold course notes, another to hold tutorials, another to hold laboratory sheets etc. Within one of these directories, say the tutorials directory, will be held the relevant files — tutorial1, tutorial2 etc. This hierarchical file storage structure is analogous to the storage of related files in a filing system. A filing cabinet could hold everything relevant to the course, each drawer could hold a different sub-division, such as notes, and each folder within the drawer would be a particular lecture. Space will also be allocated on the server for system files. These also will be allocated to directories to facilitate access by the operating system.

3.1

Summary

• The operating system provides an interface between the user and the computer and controls the internal operation of the computer and its peripherals. It also manages the users’ files and system utilities such as compilers, editors, application packages etc. • Computer networks allow many users to simultaneously access computer facilities, to access common data-bases and to use facilities such as electronic mail. • Files are stored in external storage in a hierarchical structure of directories. Each user will have their own home directory and the operating system facilities will be allocated to system directories.

3.2

Multiple Choice Questions

1. The Operating System is responsible for (a) Controlling peripheral devices such as monitor, printers, disk drives (b) Detecting errors in users’ programs (c) Make the coffee (d) Provide an interface that allows users to choose programs to run and to manipulate files (e) Manage users’ files on disk 2. Which of the following does an operating system do in a stand-alone computer system? 27

(a) Manages the user’s files. (b) Provides the system facilities. (c) Provides the interface to allow the user to communicate with the computer. (d) Controls the various peripherals 3. Which is the following is TRUE about a terminal on a Time-sharing computer system? (a) Has its own CPU and some memory. (b) Has no memory or CPU of its own. 4. Which is the following is TRUE about a terminal on a Distributed computer system? (a) Has its own CPU and some memory. (b) Has no memory or CPU of its own.

28

Lesson 4

Preparing a Computer Program
There are various steps involved in producing a computer program for a particular application. These steps are independent of which computer or programming language that is used and require the existence of certain facilities upon the computer. The steps are: 1. Study the requirement specification for the application. It is important that the requirements of the application should be well specified. Before starting to design a program for the application it is necessary that the requirement specification is complete and consistent. For example a requirement specification that says ‘write a program to solve equations’ is obviously incomplete and you would have to ask for more information on ‘what type of equations?’, ‘how many equations?’, ‘to what accuracy?’ etc. 2. Analyse the problem and decide how to solve it. At this stage one has to decide on a method whereby the problem can be solved, such a method of solution is often called an Algorithm. 3. Translate the algorithm produced at the previous step into a suitable high-level language. This written form of the program is often called the source program or source code. At this stage the program should be read to check that it is reasonable and a desk-check carried out to verify its correctness. A programmer carries out a desk-check by entering a simple set of input values and checking that the correct result is produced by going through the program and executing each instruction themselves. Once satisfied that the program is reasonable it is entered into the computer by using an Editor. 4. Compile the program into machine-language. The machine language program produced is called the object code. At this stage the com29

piler may find Syntax errors in the program. A syntax error is a mistake in the grammar of a language, for example C++ requires that each statement should be terminated by a semi-colon. If you miss this semi-colon out then the compiler will signal a syntax error. Before proceeding any syntax errors are corrected and compilation is repeated until the compiler produces an executable program free from syntax errors. 5. The object code produced by the compiler will then be linked with various function libraries that are provided by the system. This takes place in a program called a linker and the linked object code is then loaded into memory by a program called a loader. 6. Run the compiled, linked and loaded program with test data. This may show up the existence of Logical errors in the program. Logical errors are errors that are caused by errors in the method of solution, thus while the incorrect statement is syntactically correct it is asking the computer to do something which is incorrect in the context of the application. It may be something as simple as subtracting two numbers instead of adding them. A particular form of logical error that may occur is a run-time error. A run-time error will cause the program to halt during execution because it cannot carry out an instruction. Typical situations which lead to run-time errors are attempting to divide by a quantity which has the value zero or attempting to access data from a non-existent file. The program must now be re-checked and when the error is found it is corrected using the Editor as in (3) and steps (4) and (5) are repeated until the results are satisfactory. 7. The program can now be put into general use - though unless the testing was very comprehensive it is possible that at some future date more logical errors may become apparent. It is at this stage that good documentation produced while designing the program and writing the program will be most valuable, especially if there has been a considerable time lapse since the program was written.

4.1

Summary

• Before a computer program can be written the requirements of the application must be investigated and defined comprehensively and unambiguously . This leads to the production of the requirements specification. • A precise set of instructions to solve a problem is called an algorithm.

30

The first step in writing a computer program is to produce an algorithm. • Once the algorithm is designed it must be translated into a suitable high-level programming language. This program is then compiled to machine code, linked with any system libraries required and loaded into memory. At the compilation stage syntactic errors in the program may be found and have to be corrected before any further progress can be made. • Once the program has been compiled, linked and loaded it can be tested with realistic test data. Testing may show up the presence of logical errors in the program. These may lead to the production of wrong results or cause the program to halt on a run-time error.

4.2

Multiple Choice Questions

1. A compiler produces an error in compiling a program because a closing round bracket has been missed out in the source code. What type of error is this? (a) Syntax Error (b) Logical Error (c) Linker Error

4.3

Review Questions

1. What are the steps involved in going from the specification of a problem to producing an executable program which will solve the problem? 2. What types of error can occur in computing and at what stages of the processes of producing a program do they occur? 3. When the program is running it produces a number that is too large to fit into the space allocated for it in memory. What type of error is this? 4. A program runs without any errors being reported but outputs results that are wrong, what type of error is likely to have caused this?

31

Lesson 5

Algorithms
Informally, an algorithm is a series of instructions which if performed in order will solve a problem. For an algorithm to be suitable for computer use it must possess various properties: 1. Finiteness: The algorithm must terminate after a finite number of steps. For example the algorithm: produce first digit of 1/7. while there are more digits of 1/7 do produce next digit. never terminates because 1/7 cannot be expressed in a finite number of decimal places. 2. Non-ambiguity: Each step must be precisely defined. For example the statement set k to the remainder when m is divided by n. is not precise because there is no generally accepted definition for what the remainder is when m is divided by n when m and n are negative. Different programming languages may well interpret this differently. 3. Effectiveness: This basically means that all the operations performed in the algorithm can actually be carried out, and in a finite time. Thus statements like ‘if there are 5 successive 5’s in the expansion of π then . . . ’ may not be able to be answered. Even if an algorithm satisfies the above criteria it may not be a practical way of solving a problem. While an algorithm may execute in a finite time it is not much use if that finite time is so large as to make solution completely impractical. Thus there is a lot of interest in finding ‘good’ algorithms which generate correct solutions in a short time compared with other algorithms.

32

In sorting 10,000 numbers into ascending order a ‘good’ algorithm executing on a PC took less than a second while a ‘poor’ algorithm took over 10 minutes.

5.1

Describing an Algorithm

A simple example is used to look at the problem of designing an algorithm in a suitable form for implementation on a computer. The simple computational problem considered is: Write a program to input some numbers and output their average. This is a very informal specification and is not complete enough to define exactly what the program should do. For example where are the numbers going to come from—entered by the user from the keyboard or perhaps read from a file? Obviously to find the average of a series of numbers one adds them together to find their sum and then divides by the number of numbers in the series. So how is the number of numbers entered known? For example it could be input as part of the data of the program or the program could count the numbers as they are entered. This supposes that the program has some way of knowing when the user has stopped entering numbers or when the end of the file has been reached. Another important question is ‘what should the program do if no data is entered?’. It would then be nonsensical to print out an average value! Keeping these questions in mind leads to the following more specific requirement specification: Write a program which inputs a series of numbers and outputs their average. The numbers are supplied in a data file and are terminated by an end-of-file marker. In the event that the file is empty a message to that effect should be output. An algorithm is now required to solve this problem. Obviously the algorithm could be described by ‘read in the numbers from the file, add them up and divide by the number of numbers to get the average’. In practice this algorithmic description is not sufficiently detailed to describe a computer algorithm. The computer can only carry out simple instructions like ‘read a number’, ‘add a number to another number’, etc. Thus an algorithm must be described in such simple terms. Consider the following first version of a solution:

33

1 2 3 4 5 6 7 8

carry out any initialisations required. while not reached end of file do { read in next number. add the number to the accumulated sum. increment the count of numbers input. } evaluate the average.

Note that the line numbers are not required, they are merely for reference. It is commonplace in computer algorithms that certain initialisations have to be carried out before processing begins. Hence as a reminder that this might be necessary a phrase is inserted to indicate that initialisation may be required at the beginning of every algorithm description as in line 1. Once the rest of the algorithm has been developed this initialisation step can be expanded to carry out any initialisations that are necessary. At line 2 a statement is used which describes a loop. This loop executes the statements contained between the brackets in lines 3–7 continuously as long as the condition ‘not reached end of file’ remains true. The brackets are used to show that the statements in lines 4, 5 and 6 are associated together and are executed as if they were one statement. Without the brackets only statement 4 would be executed each time round the loop. This is not the only repetition statement that may be used, others are possible and will be seen later. In the body of the loop, lines 4–6, each instruction is a simple executable instruction. Once the end of the file is reached then control transfers from the loop to the next instruction after the loop, evaluating the average at line 8. This requires more expansion, since, if there are no numbers input then the average cannot be evaluated. Hence line 8 is expanded to: 8a 8b 8c 8d 8e 8f 8g if no numbers input then print message ‘no input’ otherwise { set average equal to the accumulated sum divided by the number of numbers. print the average. }

Here a conditional statement has been used with the condition ‘no numbers input’, if this is true then the statement after the then is executed, while if it is not true the statement after the otherwise is executed. This process is often called a ‘Selection’ process. On studying the above algorithm it is obvious that the process carried out is what a human being might do if given a sheet of paper with many numbers on it and asked to find the average. Thus a person might run their 34

finger down the numbers adding them as they go to an accumulated total until there were no more and then counting the number of numbers and dividing the total by this number to get the average. When this is done it is implicit in their reasoning that the total and the count will both start of at zero before starting to process the numbers. This is not obvious to the computer at all, hence it must be remembered in describing computer algorithms to initialise all sum accumulation variables and counters suitably before commencing processing. Also it must be ensured that processing starts at the beginning of the file. Hence the initialisation (line 1) can be expanded as follows: 1a 1b 1c set accumulated sum to zero. set number count to zero. open file ready to read first data item.

Note that if there were no data items in the file then the first element in the file would be the end-of-file marker. Thus the ‘while-loop’ condition would be false initially so the loop would not be executed and the number of numbers would remain at zero. This would ensure that the condition at line 8a was true hence the appropriate message would be output. The whole algorithm is now: set accumulated total to zero. set number count to zero. open file ready to read first item. while not at end of file do { read next number from file. add number to accumulated total. increment number count. } if number count is zero then print message ‘no input’ otherwise { set average to accumulated total divided by the number count. print average. }

5.2

Statements required to describe algorithms

Very few statement types have been used in describing the above algorithm. In fact these few statement types are sufficient to describe all computer algorithms. In practice other forms of loop may be introduced but they can

35

all be implemented using the while loop used in the previous section. The following basic concepts are required: 1. The idea that statements are executed in the order they are written. Sequence. 2. A construct that allows the grouping of several statements together so that they can be handled as if they were one statement by enclosing them in brackets. Compound Statement. 3. A construct that allows the repetition of a statement or compound statement several times. Repetition. 4. A construct that allows the selection of the next statement to execute depending on the value of a condition. Selection. 5. The ability to assign a value to a quantity. Assignment. All high-level programming languages have equivalents of such constructions and hence it would be very easy to translate the above algorithm into a computer program. In fact each statement of this algorithm can be written as a statement in the language C++. If you compare the following program written in C++ with the algorithm you should be able to spot the similarities. Note that the program as written is not complete, it would require further declarations and definitions to be added before the compiler would accept it as syntactically correct. What is listed here are the executable statements of the program.

36

ins.open(infile); total = 0; count = 0; while (!ins.eof()) { ins >> number; total = total + number; count = count + 1; } if (count == 0) { cout > value >> n; the user could enter 23 -65.1 3

to assign 23 to count, -65.1 to value and 3 to n. There is no indication in the data of which value is to be associated with which variable; the order of the data items must correspond to the order of the variables in the input list. The data items on input should be separated by spaces or new lines. Any number of these will be skipped over before or between data items. Thus the input above could equally well have been entered as: 23 -65.1 3

The following statement outputs the current value of the variable count to the output stream cout, which is usually associated with the monitor. The value will be printed on the current line of output starting immediately after any previous output. 53

cout n : "; cin >> m >> n; // now validate m and n if (m > n) { t1 = m*m-n*n; t2 = 2*m*n; t3 = m*m+n*n; cout