Holt Software Books [Graphical Version] | [Printer Friendly Version]
![[Cover of Book]](img/intro_to_cs.gif) |
Introduction to Computer Science using the Turing Programming Language
|
| Title: |
Introduction to Computer Science using the Turing Programming
Language (Second Edition) |
| Authors: |
J.N.P. Hume and R.C. Holt |
| ISBN: |
0-921598-06-8 |
| Publisher: |
Holt Software Associates Inc. |
| Binding: |
Softcover |
| Pages: |
388 pgs |
| Price: |
Bookstores & Schools: $34.65 Retail: $43.30 |
| Ordering Information: |
For bookstores and schools, click here for
ordering information.
For individuals click
here for ordering information. |
| Program Examples: |
Not Available |
| Solutions Manual: |
Not Available |
Used by Computer Science majors as well as students of science,
engineering and mathematics. After a concise but thorough introduction
to the basic programming concepts of general purpose programming
languages, the book concentrates on giving the student a solid
understanding of essential Computer Science concepts, including chapters
on Program Design, Correctness, Graphics, Searching and Sorting, Analysis
of Algorithms, Data Structures, Modules and Abstract Data Types.
Preface to Introduction to Computer Science (2nd edition)
The six years since the publication of the first edition have seen a number
of significant changes of emphasis in computer science. These changes are
reflected in this new edition. The preface to the first edition says:
No serious study of computer science is viable without a solid
underpinning in programming, in algorithms, and in basic data structures
... Programming and algorithms are taught most effectively in terms of
good notation, namely an appropriate programming language... The Turing
Language is well suited for teaching programming ... it is a more general
language than Pascal, yet its basic features have an expressiveness
characteristic of a more modest language such as Basic.
Turing's unobtrusive syntax provides the ideal vehicle for the illustration
of concepts. In this edition the presentation of the basic topics of the
structure of programs and data has been streamlined. As well, emphasis has
shifted to such topics as correctness of programs, analysis of algorithms,
and abstract data types.
Turing itself has recently been enhanced and two chapters have been added on
graphics, both character and pixel.
This is primarily a book for computer science students at the introductory
university level.
Turing was designed in 1982 by R.C. Holt and J.R. Cordy of the Computer
Systems Research Institute at the University of Toronto. The language has a
no frills syntax that is very easy to learn. It is defined by a watertight
mathematical specification, so Turing programs work the same way on all
computers.
It was named after Alan Turing (1912-1954) the British scientist-mathematician
who made fundamental contributions to the development of modern computers and
computer science.
It is one of the easiest programming languages for beginners to learn; at the
same time it is powerful enough to be used by professional programmers as a
real-world language for the construction of computer software. It is used
extensively to teach computer programming in high schools, colleges, and
universities.
Compiler-interpreters are available for both IBM compatible microcomputers
and Macintosh computers, as well as for SUNs and Vaxes.
The Turing language has a set of extensions that make it into Turing Plus
which is a systems programming language. Compilers for Turing Plus are at
present only available for larger computers. Any Turing program will run
under a Turing Plus system. As more and more students are educated using
the Turing Language, Turing will be used more and more as a professional
language beyond the university research environment where it now enjoys
considerable popularity.
Turing is an ideal first programming language because it is so much easier
to write good programs in Turing. Afterwards it is straightforward to learn
languages like Pascal, FORTRAN, or C. In the appendix to the book a comparison
shows how much simpler Turing programs are than those in Pascal and C.
Turing has all the features of Pascal plus: modules, complete string handling
facilities, type-safe variant records, and dynamic array parameters. Turing
Plus has all the features of C, but encourages a safe, readable style of
programming.
This all adds up to the fact that Turing is an ideal language for illustrating
concepts in computer science. It was designed to support the development of
reliable, efficient programs. It incorporates features that decrease the cost
of program maintenance, and that support formal verification.
J.N.P. Hume
R.C. Holt
University of Toronto
Table of Contents of Introduction to Computer Science (2nd edition)
1. INTRODUCTION 1
What are Computers? 1
Computer Science Concepts 2
What Is Programming? 3
What Is Structured Programming? 4
What Is Turing? 4
Correctness of Programs 5
The Operating System 6
Summary 7
2. BASIC CONCEPTS OF PROGRAMMING 11
Basic Symbols 11
Numbers 12
Character Strings 13
Expressions 14
Examples of Arithmetic Expressions 15
Output 16
The Program 18
Comments 19
Variables 19
Declarations 20
Assignment Statements 21
Tracing Execution 23
Input 24
Predefined Functions 27
String Expressions 27
Constants 29
Labelling of Output 31
Avoiding Errors in Programming 33
Summary 35
Exercises 39
3. THE STRUCTURE OF PROGRAMS 43
Counted Loops 43
Conditions 45
Boolean Variables 46
Conditional Loops 46
Reading Input 48
Selection 50
Paragraphing the Program 54
Control Structure and Flow Charts 54
Nested Loops 58
A Selection Nested in a Loop 60
Loops with Compound Conditions 60
Counted Loops with Conditional Exits 61
If Statements with Compound Conditions 62
Localizing Declarations 62
Summary 63
Exercises 67
4. STRUCTURED DATA TYPES 71
Arrays 71
Related Arrays 73
Two-dimensional Arrays 75
Subrange Types 78
Named Types 79
Arrays of Arrays 80
Initialization of Arrays 81
Dynamic Arrays 83
Records 84
Files 86
End of File Marker 87
Enumerated Type 89
Sets 90
Random Numbers 92
Unions 93
Summary 94
Exercises 98
5. DESIGN OF PROGRAMS 103
Step-by-step Refinement 103
Tree Structure to Program Development 104
Choosing Data Structures 104
Growing the Solution Tree 105
Developing an Algorithm 106
Assessing Efficiency 108
A Better Algorithm 108
Better Algorithms 109
Summary 110
Exercises 112
6. SUBPROGRAMS 115
Subprograms as Abstractions 115
Predefined Subprograms 116
Procedures 117
Parameters 118
Variable and Constant Parameters 119
Local Declarations 120
Global Declarations 120
Functions 121
Procedures Versus Functions 124
Pre Conditions and Post Conditions 124
An Example Function 125
Dynamic Array Parameters 126
Dynamic String Parameters 127
Matching Types of Actual and Formal Parameters 128
An Example Handling Matrices 130
Recursive Functions 133
Recursive Procedures 137
Mutual Recursion 139
Summary 141
Exercises 144
7. CHARACTER GRAPHICS 149
Character Locations on the Screen 149
Creating a Graphical Pattern 150
Interactive Graphics 150
Diagonal Lines and Patterns 151
Drawing in Color 152
Background Color 154
Hiding the Cursor 155
Animation with Graphics 155
Controlling the Speed of Animation 156
Highly Interactive Graphics 156
Summary 160
Exercises 161
8. PIXEL GRAPHICS 163
Pixel Positions on the Screen 163
Plotting dots on the Screen 163
Graphics Systems other than CGA 165
Drawing Lines and Boxes 166
Drawing Circles and Ellipses 168
Animation 169
Drawing Arcs 169
Plotting a Mathematical Function 170
Using Text with Pixel Graphics 171
Background Color 172
Sound with Graphics 172
Current Values of Graphics Parameters 173
Drawing a Tilted Box 173
Repeating a Pattern 174
Animation Using a Buffer 177
Bar Charts 178
Pie Charts 180
Graphing Mathematical Equations 182
Summary 185
Exercises 186
9. CORRECTNESS OF PROGRAMS 189
Path Testing 189
Correctness and Specifications 190
Specifications 191
Proof by Induction 192
Proof of Correctness for Loops 193
An Example of Proving a Loop Correct 194
Another Loop Example A Sort Procedure 196
Invariants and Proofs 198
Problems We Have Not Solved 198
Summary 199
Exercises 200
10. SEARCHING AND SORTING 201
Linear Search 201
Time Taken for Search 204
Binary Search 204
Searching by Address Calculation 207
Random Access to Records on Disk 208
Sorting 212
Sorting by Merging 212
Quicksort 215
Summary 218
Exercises 219
11. ANALYSIS OF ALGORITHMS 221
Big O Notation 221
Comparison of Sorting Algorithms 222
Best, Worst, and Average Case Performance 223
Performance of Address Calculation Sort 224
Performance of Searching Algorithms 224
Search for Better Algorithms 225
Infeasible Problems 226
Summary 227
Exercises 228
12. DATA STRUCTURES 231
Data Structures Defined by Turing 231
Definition of Data Structure 231
Queues 232
Stacks 233
Stacks and Recursive Subprograms 235
Linked List 236
Collections Compared to Arrays 237
Creating and Deleting Elements of Collections 237
Using Pointers in Linked Lists 238
Trees 240
Entering Data into the Tree 242
Outputting the Lines in the Tree 243
N-ary Trees 244
Heaps 245
Implementation of Pointers and Collections 248
Problems with Pointers 249
Summary 250
Exercises 253
13. MODULES AND ABSTRACT DATA TYPES 255
Use of Subprograms 255
A Module for a Stack 256
A Module for a Ledger 258
Details about Modules 261
Aliasing and Modules 263
Black Boxes and Information Hiding 264
A More Realistic Program 264
Summary 269
Exercises 270
14. SCIENTIFIC CALCULATIONS 271
Evaluating Formulas 271
Representation of Numbers 273
Cancellation Errors 275
Root Finding 276
Square Root Function 279
Evaluation of a Polynomial 281
Approximating Infinite Series 282
Computing Areas 285
Numerical Integration 286
Solving Linear Equations 287
Linear Equations Using Arrays 288
Graphing a Function 289
Fitting a Curve to a Set of Points 292
Least Squares Approximation 293
Mathematical Software 294
Summary 295
Exercises 298
15. ASSEMBLY LANGUAGE AND MACHINE LANGUAGE 301
Machine Instructions 301
Instructions for a Very Simple Computer 303
Translation of a Turing Program 304
Mnemonic Names and Machine Language 304
Storing Machine Instructions in Words 306
A Complete Machine Language Program 307
Simulating a Computer 309
Uses of Simulators 311
Summary 312
Exercises 313
Appendices
A. TURING ON THE PC 315
The Turing Environment 315
Entering Data or Programs 317
Editing Data or Programs 317
Storing Programs on Disk 318
The Line Editor 320
Moving the Cursor Rapidly 321
Searching and Replacing Text 322
Data Files on Disk 322
Multiple Directories on Disk 324
Command Summary 325
Window Commands 325
Left Side Line Commands 325
Long Commands 326
B. TURING ON THE MAC 327
Features of the Macintosh 327
The Mouse 327
Startup Procedure 328
Selecting a Menu Command 328
Using the Turing System 328
Printing or Saving the Program or Input/Output 329
Running a Turing Program 330
Starting a New Program 331
Menu of Commands 332
Editing the Program 333
Searching and Replacing Text 333
Data Files on Disk 334
Adding One File to Another 336
C. PREDEFINED SUBPROGRAMS 339
Predefined Functions 339
Mathematical Functions 340
Type Transfer Functions 341
Predefined Procedures 344
Graphic Procedures 344
Attributes 347
D. RESERVED WORDS IN TURING 349
Keywords 349
Predefined Identifiers 349
E. ASCII CODE FOR CHARACTERS 351
F. SYNTAX OF TURING 353
Programs and Declaractions 354
Types 355
Subprograms 356
Statements and Input/Output 358
References and Expressions 362
Identifiers and Explicit Constants 364
G. MUSIC 365
Playing Musical Notes 365
Resting 366
Playing a Series of Notes 366
Using the Keyboard to Make Music 367
Animation with Music 368
H. PROGRAMMING IN PASCAL AND C 373
INDEX 379
[ Holt Software Home ] *
[ Books (Graphical) ] *
[ Books (Text) ] *
[ Top of Page ] *
[ Feedback ]
