INTRODUCTION TO PL/I, ALGORITHMS, AND STRUCTURED PROGRAMMING

3rd Edition 1997 by R. A. Vowels, emphasizes fundamentals of structured programming through study of PL/I. 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 PL/I in greater depth.

The book is organized into two parts. The first part (Chapters 0 to 9) is concerned with elements of PL/I. The second part (Chapters 10 to 26) introduces traditional and new algorithms.

First Part - PL/I and Structured Programming

The first part emphasizes fundamentals of structured programming through study of a subset of PL/I. 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 (GET LIST and PUT LIST), formatted input and output including picture formats (GET EDIT and PUT EDIT), loops and conditional statements, statement grouping using simple DO-groups, structured loops including DO WHILE, declarations, arrays, debugging, string data concepts, subroutines, functions, and program structure. 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 section on EDIT-directed 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.

Second Part - Algorithms and PL/I

The second part explores more PL/I 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-fillling curves, reading and creating picture files (PCX and TIFF files), and data compression, 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 PL/I topics are included: separate theme chapters are devoted to decimal and complex arithmetic, file processing, list processing (including binary search trees and the new strongly typed facilities of IBM PL/I for OS/2, VisualAge PL/I for Windows, AIX, and Enterprise PL/I for z/OS), text processing including string searching, recursion, and the macro processor.
The most important area of exception handling is included for its three benefits: to enable errors to be detected, to enable error recovery to be performed, and to provide debugging facilities.

Chapters 10 to 26 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 PL/I statements, a list of built-in functions, and algorithms for many of the new built-in functions. Comes with a floppy disc with the programs, subroutines, and functions from the book. ISBN 0-9596384-9-0

Contents

PART 1 - Introduction to PL/I

Preface ix 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, PL/I 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 Tab settings 4.3 Control over Layout Exercises 4.4 Catenation 4.5 Long Statements 4.6 Complete PL/I programs 4.7 Presentation Exercises 4.8 Edit-Directed Input and Output 4.9 The PUT EDIT Statement Integer output, fixed-point output, Data format items, floating-point output, character string output, control format items 4.10 Iteration Factor 4.11 General PUT EDIT statement 4.12 Picture Format 4.13 The GET EDIT statement Reading Strings 4.14 Summary of Format Items 4.15 Summary of GET and PUT statements Exercises 5 Control Statement 5.1 The DO FOREVER Statement The GO TO statement, Labels 5.2 The IF Statement Compound Comparisons Exercises 5.3 Value Loops 5.4 A Count Loop 5.5 Program Genesis 5.6 Loop with an ON Statement 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 DECLARE Statements and Attributes Default data attributes, the DEFINE ALIAS statement, Types of declarations, Long declarations, Special Points. 7.2 Factoring Exercises 8 String 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 Catenation, the Built-in Functions SUBSTR, INDEX, SEARCH, SEARCHR, and REVERSE 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 Parameters 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 9.10 The Preprocessor 9.11 Function Procedures Exercises 9.12 Blocks 9.13 Plotting a Graph Epilog Exercises Syntax Diagrams for Part 1
PART 2 - Algorithms and PL/I

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 Tree 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 Expressions 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 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 14.8 Transposing without Transposing 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 Exercise 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 Searching (Unrestricted) 15.10 Approximate String Search 16 Files 16.1 Record-Oriented Input-Output 16.2 Sequential Record-Oriented File 16.3 Random-Access Files 16.4 Operations on Direct Access Files 16.5 Varying-Length Records 16.6 Self-Defining (Varying-Length) Records 16.7 PICTURE Data 16.8 Stream Files 16.9 EDIT Input and Output 16.10 PICTURE Data 17 Solving Simultaneous Equations 17.1 Solving Equations using Gauss Elimination 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 17.7 Printing Arrays 18 Decimal Facilities 18.1 Introduction 18.2 Declarations 18.3 Care Required 18.4 Restrict Accuracy 18.5 The Intermediate Steps 18.6 Addition and Subtraction 18.7 Multiplication 18.8 Division 18.9 Precision Exercise 18.10 Large Decimal Numbers 18.11 TIME and DATE 18.12 DAYS and DAYSTODATE 18.13 DAYS, and the UNION attribute 18.14 PICTURE Formats 19 Graphics 19.1 Seashells 19.2 New Shapes 19.3 Uccello's Chalice 19.4 Making a Picture File (TIFF File) Color TIFF File 19.5 Reading and Displaying a Picture File (PCX File) Summary of SELECT Statement 20 Searching 20.1 Linear Search 20.2 Binary Search 20.3 Hash Search 20.4 Hash Table with Quadratic Searching Exercise 21 Numerical Methods 21.1 Integration - Rectangle Method 21.2 Trapezoidal Method 21.3 Simpson's Rule 21.4 Differentiation 21.5 Solving a Differential Equation: Euler's Method 21.6 Solving a Differential Equation: The Runge-Kutta Method 22 Debugging: Detecting & Intercepting Errors 22.1 Introduction 22.2 What kinds of error may occur? 22.3 Checking for errors 22.4 Intercepting Errors 22.5 Execute an ON statement first 22.6 Substring errors 22.7 Errors in Procedures 22.8 Production Run Monitor 22.9 Stuck in a Loop? 22.10 Long-Running Program? 22.11 Recovering after an Error 22.12 Using conditions to validate input data 22.13 Extended Exponent Range 22.14 Summary 23 Whole Array Operations 23.1 One-Dimensional Arrays 23.2 Two-Dimensional Arrays 23.3 Printing Tables 23.4 Cross-Sections of Arrays 24 The Macro Processor 24.1 The Macro Processor 24.2 Text Replacement 24.3 Text Generation 24.4 Expression Evaluation 24.5 Generating a Frequently-needed Expression 25 IBM PL/I for OS/2 25.1 DO Statements 25.2 New Data Types 25.3 Building Blocks 25.4 Multi-threading 26 What's next? - Visual PL/I Appendices A Built-in Functions A.1 Built-in Functions A.2 Division A.3 Macro Built-in Functions B Character Sets - ASCII and EBCDIC C IBM PL/I for OS/2 and the PC D Graphics Codes E Quick Reference to PL/I Statements F %INCLUDE Files G Pre-processor Procedures H PL/I Resources I Sample Compilation J Graphics Displays Bibliography Index

See a list of the main algorithms.

Details: Introduction to PL/I, Algorithms, and Structured Programming by R. A. Vowels, 3rd Edition, 1997, ISBN 0-9596384-9-0, 731 pages, A4 size.

For further information, contact r|o|b|i|n|5|1 at dodo dot com dot au
[remove the vertical bars, and translate the other words accordingly.]

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

Updated 10th January 2005.