INTRODUCTION TO Fortran 90/95, ALGORITHMS, AND STRUCTURED PROGRAMMING,

by R. A. Vowels, emphasizes fundamentals of structured programming through study of Fortran 90 (Fortran 95). It is designed for a reader's first or second exposure to computer programming, and is intended to provide a sound grounding for the reader who desires to study Fortran 90/95 in greater depth. The book is organized into two parts. The first part (Chapters 0 to 9) is concerned with elements of Fortran 90. The second part (Chapters 10 to 21) introduces traditional and new algorithms.
First Part - Fortran 90/95 and Structured Programming

The first part emphasizes fundamentals of structured programming through study of a subset of Fortran 90/95. The subset is concise, well-defined, and is easy to learn.

The first chapter outlines some historical aspects of computing. The second introduces the concept of algorithms, flowcharts, and complete working programs illustrating basic elements including conditional statements. Subsequent chapters cover numeric data, expressions and assignments, free format input and output (READ and PRINT), formatted input and output (READ and WRITE), loops and conditional statements, statement grouping using simple DO-loops, structured loops including DO WHILE, declarations, arrays, debugging, string data concepts, subroutines, functions, and program structure (modules, interface blocks, contained and external procedures). In this flexible text, some later chapters can be covered earlier, or may be omitted at first reading. For example, the chapter on string handling may be covered earlier if it is desired to provide practice in this area before others. The sections on formatted input-output may be omitted, or covered later.

The importance of structured programming is stressed from the beginning. All of the example programs are enhanced by a uniformly-applied style of indenting both loops and conditionals.

The example programs can be run with Fortran 90 compilers including the Lahey ELF90 compiler.

Second Part - Algorithms and Fortran 90/95

The second part explores more Fortran 90/95 and contains a detailed exposition on important algorithms, some traditional, some new. For most of these topics, no prior or special knowledge is assumed. Popular sort algorithms are examined: the Bubble Sort, Shell Sort, Heap Sort, Quicksort, and Hash Sort. Various search algorithms are studied: linear, binary, hash, binary search tree. The chapter on recursion commences with some short examples, and culminates with Quicksort and algorithms for space-filling curves. Algorithms for solving linear equations including tri-diagonal and banded systems (Gauss, Gauss-Siedel), matrix inversion, roots of polynomials are covered in detail. Algorithms for performing Fourier Transforms are included. The significant string search algorithms studied include the Knuth-Morris-Pratt, Rabin-Karp, Boyer-Moore, and Baeza-Yates-Gonnet. Graphics algorithms for creating fractals and space-filling curves, for creating picture files (PCX and TIFF files), for reading a PCX file, and data compression and expansion, are provided. The adventurous will find that the large bibliography includes many works appropriate for further reading, study or research.

The second part is not just algorithms. Some additional Fortran 90/95 topics are included: separate theme chapters are devoted to complex arithmetic, file processing, list processing (the extensive chapter includes binary search trees), text processing including string searching, and recursion.

Chapters 10 to 21 can be studied in any order, as they are mostly independent. They can be selected at will according to the reader's interests.

The reader is expected to run as many of the exercises as possible on his/her computer (there are over 240 exercises) since practice is essential in developing programming expertise.

The book will be found helpful as a reference. Appendices contain a summary of Fortran 90/95 statements, the built-in procedures - many with detailed explanations and examples, and ASCII and EBCDIC reference tables. Comes with a floppy disc with the programs, subroutines, and functions from the book. ISBN 0-9596384-8-2

Contents

PART 1 - Introduction to Fortran

Preface 0 Introduction The Mechanical Era The evolution of calculators Early calculating machines The first mechanical pre-computers The first mechanical computer The Electronic Era Speed, Complexity, Miniaturization The Software Era The compiler Technological Advances What is a computer? 1 Algorithms and Programs Algorithms, flowcharts, basic machine concepts, machine instructions, Fortran programs, loops and control statements 2 Data Representation 2.1 Character Sets 2.2 Numbers 2.3 Data Types: Fixed-point constants, floating-point constants 2.4 Names 2.5 Integer and Floating-point 2.6 Some Basic Definitions 2.7 Introduction to computer peripherals and media Exercises 3 Expressions and Assignments 3.1 Arithmetic Expressions Operators and Operands, Evaluation, Priority of operators, parentheses, prefix operators Exercises 3.2 Priority of Operators Evaluation and priority, Expressions with same priority operators, Parenthesized expressions Exercises 3.3 Assignment Statement Exercises 3.4 Built-in Functions Exercises 3.5 Comments 3.6 Logical Expressions Exercises 4 Input-Output 4.1 Supplying Data, Getting Results 4.2 Layout of printed results 4.3 Control over Layout Exercises 4.4 Long Statements 4.5 Complete Fortran programs 4.6 Presentation Exercises 4.7 Formatted Input and Output 4.8 The WRITE Statement Integer output, fixed-point output, Edit descriptors, floating-point output, character data output, control edit descriptors 4.9 Iteration Factor 4.10 Printing on the Same Line 4.11 Edit Descriptors - Summary 4.12 The Formatted READ statement Reading Character Data 4.13 Summary of Edit Descriptors 4.14 Summary of READ, PRINT, and WRITE statements Exercises 5 Control Statements 5.1 The DO Statement The GO TO statement 5.2 The Block IF Statement Compound Comparisons Exercises 5.3 Value Loops 5.4 A Count Loop Labels 5.5 Program Genesis 5.6 Loop with an END= Option Exercises 6 DO Statements, Arrays 6.1 Iterative Statements and the Loop 6.2 DO statement for a Count Loop 6.3 Generalized DO Statement 6.4 DO Statement for a Value Loop (DO . . . WHILE) 6.5 DO Statement for a Hybrid Loop Exercises 6.6 Arrays Subscripted Variables & Declarations, Fish Survey example, Declarations - main points Exercises 6.7 Sorting Case Study Exercises 6.8 Searching 6.9 Leaving Footprints A Note on Floating-point Structured Programming - a perspective Exercises 7 Declarations 7.1 Type Specification Statements Default types, Types of declarations, Long declarations, Special points Exercises 8 Character Data Processing 8.1 Introduction 8.2 Character Data and Constants Coded values 8.3 Declarations, Character Names, and Assignments Padding and Truncation 8.4 Input and Output of Strings 8.5 Character Operations Exercises 8.6 Building, Extracting, and Searching Strings Building: String Catenation, Extraction: the Substring Operation, Searching: the Built-in Functions, INDEX, SCAN Exercises 8.7 Graph Plotting 8.8 The Binary Search 8.9 Algebraic Expression Case Study 8.10 Summary of Character Operations Exercises 9 Subroutines, Procedures, Program Structure 9.1 Introduction 9.2 Fundamentals 9.3 How to call a Subroutine 9.4 How to Write a Subroutine Exercises 9.5 Subroutines with Dummy Arguments INTENT of dummy arguments 9.6 Scope of Declarations 9.7 The Effect of Scope at Execution Time Modular Programs Exercises 9.8 Generalizing a Program Exercises 9.9 The INCLUDE Statement Exercises 9.10 Functions Exercises 9.11 Program Units Activation, Nested program units, Control transfer 9.12 Packaging Subroutines and Functions Interface Blocks, Modules, COMMON Blocks, Adjustable Dimensions 9.13 Plotting a Graph Epilog Summary of program unit structures Exercises PART 2 - Algorithms and Fortran 10 Sorting 10.1 Cocktail-Shaker Sort 10.2 Double-Bubble Sort 10.3 Shell Sort 10.4 Heap Sort 10.5 Indirect Addressing 10.6 Hash Sort 10.7 Hash Sort (Version 2) 10.8 Sorting Structures 10.9 Sorting Structures, on Two Fields 11 Recursion 11.1 Factorial 11.2 Fibonacci Numbers 11.3 Multiplication 11.4 Greatest Common Divisor 11.5 Base Conversion 11.6 Quicksort 11.7 QuickSort Version 2 11.8 QuickSort Version 3 11.9 Sierpiski Curves 11.10 Hilbert Curves 11.11 Penrose Curves 11.12 Dragon Curves Exercises 12 Linked Lists and trees 12.1 Linked List 12.2 Creating a One-Way Linked List Appending to the Tail, Creating and Deleting Nodes 12.3 Circular Linked List - Josephus' Problem Exercises 12.4 Two-Way Linked List Exercises 12.5 Binary Tree 12.6 Binary Search Tree Searching, Traversal, Insertion 12.7 Sorting Using Red-Black Binary Trees Insertion, Left Rotation, Right Rotation, Rebalance the tree and re-color nodes, Red-Black Tree algorithm, Shortened version of the RE_BALANCE_TREE algorithm 12.8 Displaying a Tree Decorated with Nodes Normal and sideways 12.9 Deleting a Node from a Red-Black Tree Splicing out and re-structuring 12.10 Algebraic Expression and Trees Exercise 12.11 Indirect Sort of a Linked List Exercise 13 Complex Arithmetic 13.1 Complex Arithmetic Facilities 13.2 Exponentiation, taking roots 13.3 Complex Roots of a Quadratic Equation 13.4 Real and Complex Roots of a Cubic Equation 13.5 Real and Complex Roots of a Polynomial 13.6 Fractals The Mandelbrot Set 13.7 Making a Picture File (PCX format) 13.8 Complex Roots of Complex Linear Equations 13.9 Electrical Circuit 13.10 Impedance of an Electrical Circuit 13.11 Defining a COMPLEX type for Integers 14 Using Published Algorithms 14.1 Fast Fourier Transform 14.2 Fast Fourier Transforms of Real, Sine, and Cosine Functions 14.3 Matrix Multiplication 14.4 Directed Graphs - Transitive Closure 14.5 Integration with the IBM SSP 14.6 Matrix Inversion with the IBM SSP 14.7 Matrix Inversion with IMSL 15 Text Processing 15.1 A Simple Text Editor Exercises Example - Converting a plain text file to HTML format 15.2 String Searching 15.3 Classic String Search 15.4 The Knuth-Morris-Pratt String Search 15.5 The Boyer-Moore String Search 15.6 The Rabin-Karp String Search 15.7 The Baeza-Yates-Gonnet String Search 15.8 Approximate Searching 15.9 Approximate String Search 16 Files 16.1 Unformatted Input-Output 16.2 Sequential Record-Oriented File 16.3 Random-Access Files 16.4 Operations on Direct Access Files 16.5 Writing Unformatted Files 16.6 Internal Input-Output 17 Solving Simultaneous Equations 17.1 Solving Equations using Gauss Elimination Using Array Sections, Using Row and Column Interchanges Exercises 17.2 Gauss-Siedel Iteration 17.3 Tri-Diagonal System of Linear Equations 17.4 Banded System of Equations 17.5 Sparse matrices 17.6 Matrix Inversion Exercises 17.7 Printing Arrays 18 Graphics 18.1 Seashells 18.2 New Shapes 18.3 Uccello's Chalice 18.4 Making a Picture File (TIFF file) Color TIFF file 18.5 Reading and Displaying a Picture File (PCX File) Summary of SELECT CASE statement 19 Searching 19.1 Linear Search 19.2 Binary Search 19.3 Hash Search 19.4 Hash Table with Quadratic Searching Exercise 20 Numerical Methods 20.1 Integration - Rectangle Method 20.2 Trapezoidal Method 20.3 Simpson's Rule 20.4 Differentiation 20.5 Solving a Differential Equation - Euler's Method 20.6 Solving a Differential Equation - The Runge-Kutta Method 21 Whole Array Operations 21.1 One-Dimensional Arrays Initialization 21.2 Two-Dimensional Arrays Initialization and the RESHAPE Built-in Function 21.3 Printing Tables 21.4 Cross-Sections of Arrays 21.5 Parts of Arrays Extracting Sub-Matrices 21.6 MINVAL, MAXVAL 21.7 MINLOC, MAXLOC 21.8 The WHERE Construct 21.9 The FORALL Statement Appendixes A Built-in Functions B Character Sets ASCII, EBCDIC C Extended-Precision Constants D Useful Functions E ELF90 compiler output F Quick Reference to Fortran Statements G Fortran 90 Resources Bibliography Index

See a list of the main algorithms.

For further information, contact email: robin_v@bigpond.com

Copyright (c) 1997 by R. A. Vowels. All rights reserved.

Updated 25 December 1999