Programming: The Derivation of Algorithms (Prentice-hall International Series in Computer Science)

✍ Scribed by A. Kaldewaij

• Publisher: Prentice Hall
• Year: 1990
• Tongue: English
• Leaves: 231
• Category: Library

✦ Synopsis

An introductory textbook for students of computer science. The book looks at the art of changing efficient algorithms that meets their specifications and discusses the calculational style of programing.

✦ Table of Contents

Front Cover
Contents
Preface
0 Introduction
1 Predicate Calculus
2 The Guarded Command Language
2.0 Introduction
2.1 Skip
2.2 Assignment
2.3 Catenation
2.4 Selection
2.5 Repetition
2.6 Constants, Inner Blocks, and Arrays
2.7 Summary
3 Quantifications
4 General Programming Techniques
4.0 Introduction
4.1 Taking conjuncts as invariant
4.2 Replacing constants by variables
4.3 Strengthening invariants
4.4 Tail invanants
4.5 Summary
5 Deriving Efficient Programs
5.0 Introduction
5.1 Integer division
5.2 Fibonacci
6 Searching
6.0 Introduction
6.1 Linear Search
6.2 Bounded Linear Search
6.3 Binary Search
6.4 Searching by Elimination
7 Segment Problems
7.0 Introduction
7.1 Longest segments
7.1.0 All zeros
7.1.1 Left-minimal segments
7.1.2 At most ten zeros
7.1.3 All elements different
7.2 Shortest segments
8 Slope Search
8.0 Introduction
8.1 The basic principle
8.1.0 Searching
8.1.1 Decomposition in a sum of two squares
8.1.2 Minimal distance
8.2 Longest and shortest segments
8.2.0 Longest segments
8.2.1 Shortest segments
8.2.2 At least two zeros revisited
9 Mixed Problems
10 Array Manipulations
10.0 Introduction
10.1 Array assignments
10.2 Swaps
10.2.0 The Dutch National Flag
10.2.1 Rotation
11 Sorting
11.0 Introduction
11.1 Quadratic sorting algorithms
11.1.0 Insertion Sort
11.1.1 Selection Sort
11.1.2 Bubble Sort
11.2 Advanced sorting algorithms
11.2.0 Quicksort
11.2.1 Mergesort
11.2.2 Heapsort
12 Auxiliary Arrays
12.0 At most K zeros
12.1 Largest square under a histogram
12.2 The length of a longest common subsequence
12.3 A shortest segment problem
Index
Back Cover